# Surface Area of 3D Shapes
**Difficulty:** EASY
[External](https://leetcode.com/problems/surface-area-of-3d-shapes)
Canonical: https://scaleengineer.com/dsa/problems/surface-area-of-3d-shapes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array, Matrix
---
## Problem
You are given an `n x n` `grid` where you have placed some `1 x 1 x 1` cubes. Each value `v = grid[i][j]` represents a tower of `v` cubes placed on top of cell `(i, j)`.

After placing these cubes, you have decided to glue any directly adjacent cubes to each other, forming several irregular 3D shapes.

Return _the total surface area of the resulting shapes_.

**Note:** The bottom face of each shape counts toward its surface area.

**Example 1:**

![](https://assets.glich.co/dsa/surface-area-of-3d-shapes/image0.jpg) 

**Input:** grid = [[1,2],[3,4]]
**Output:** 34

**Example 2:**

![](https://assets.glich.co/dsa/surface-area-of-3d-shapes/image1.jpg) 

**Input:** grid = [[1,1,1],[1,0,1],[1,1,1]]
**Output:** 32

**Example 3:**

![](https://assets.glich.co/dsa/surface-area-of-3d-shapes/image2.jpg) 

**Input:** grid = [[2,2,2],[2,1,2],[2,2,2]]
**Output:** 46

**Constraints:**

* `n == grid.length == grid[i].length`
* `1 <= n <= 50`
* `0 <= grid[i][j] <= 50`

# Approaches
## Brute-Force 3D Grid Simulation
This approach directly simulates the 3D structure described in the problem. It constructs a 3D grid to represent every possible 1x1x1 cube's location. After building this representation, it iterates through each cube that is part of the structure. For each cube, it checks its six adjacent positions. If an adjacent position is empty (i.e., not occupied by another cube), that face is exposed to the air and contributes 1 unit to the total surface area. This method is straightforward and mirrors the physical reality but is inefficient for large grids or tall towers.
**Time:** O(N * N * H), where N is the grid dimension and H is the maximum height. We iterate through the entire 3D grid to check for exposed faces. · **Space:** O(N * N * H), where N is the grid dimension and H is the maximum height of a tower. This is for storing the 3D `shape` array.
**Pros:** Conceptually simple and directly models the physical problem.; Guaranteed to be correct if implemented properly.
**Cons:** High time complexity, as it depends on the maximum height of the towers, not just the grid size.; High space complexity, requiring a 3D array that can be large.
### Explanation
The algorithm begins by creating a 3D boolean grid that is large enough to contain the entire shape. The dimensions will be `n x n x max_height`. We then iterate through the input `grid` to populate our 3D `shape` grid, marking the locations of all the 1x1x1 cubes.

Once the 3D model is built, we calculate the surface area by examining each individual cube. We iterate from `(0,0,0)` to `(n-1, n-1, max_height-1)`. If we find a cube at `(i, j, k)`, we look at its six neighbors. A face is part of the total surface area if it's not adjacent to another cube. This occurs when a neighbor is outside the grid boundaries or when the neighboring cell in our 3D model is marked as empty. By summing up all such exposed faces, we get the total surface area.

```java
class Solution {
    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int maxH = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxH = Math.max(maxH, grid[i][j]);
            }
        }
        if (maxH == 0) return 0;

        boolean[][][] shape = new boolean[n][n][maxH];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < grid[i][j]; k++) {
                    shape[i][j][k] = true;
                }
            }
        }

        int surfaceArea = 0;
        int[] dr = {0, 0, 0, 0, 1, -1};
        int[] dc = {0, 0, 1, -1, 0, 0};
        int[] dh = {1, -1, 0, 0, 0, 0};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < maxH; k++) {
                    if (shape[i][j][k]) {
                        for (int d = 0; d < 6; d++) {
                            int ni = i + dr[d];
                            int nj = j + dc[d];
                            int nk = k + dh[d];

                            if (ni < 0 || ni >= n || nj < 0 || nj >= n || nk < 0 || nk >= maxH || !shape[ni][nj][nk]) {
                                surfaceArea++;
                            }
                        }
                    }
                }
            }
        }
        return surfaceArea;
    }
}
```
### Algorithm
1. Determine the dimensions of the 3D space required. This will be `N x N x H`, where `N` is the side length of the input `grid` and `H` is the maximum height of any tower.
2. Create a 3D boolean array, let's call it `shape[N][N][H]`, to represent the space. Initialize all its values to `false`.
3. Populate the `shape` array. For each cell `(i, j)` in the input `grid` with value `v`, set `shape[i][j][k]` to `true` for all `k` from `0` to `v-1`.
4. Initialize a counter `surfaceArea` to `0`.
5. Iterate through every position `(i, j, k)` in the `shape` array.
6. If `shape[i][j][k]` is `true` (meaning a cube exists at this position), check its six neighbors (up, down, left, right, front, back).
7. For each of the six directions, if the neighboring position is outside the bounds of the `shape` array or if the neighbor is `false` (meaning it's air), it represents an exposed face. Increment `surfaceArea` by 1.
8. After checking all positions, the value of `surfaceArea` is the result.

## Iterative Calculation of Exposed Faces
Instead of simulating every cube, this approach operates on the grid level. It calculates the total surface area by summing up the contributions of each tower. The contribution of a tower consists of its top and bottom faces, plus its four side faces. The area of the side faces depends on the height of the adjacent towers. The key insight is that the exposed vertical surface area between two adjacent towers is simply the absolute difference in their heights.
**Time:** O(N*N), as we iterate through the 2D grid a constant number of times. · **Space:** O(1), as we only use a few variables to keep track of the total area.
**Pros:** Efficient `O(N^2)` time complexity.; Optimal `O(1)` space complexity.; Avoids creating a large 3D array.
**Cons:** The logic is slightly more complex than the single-pass subtraction method, involving separate steps for inner and boundary faces.
### Explanation
We can iterate through the grid and for each tower, calculate the area of its exposed faces. The total area is the sum of:
1.  The top and bottom faces of all towers.
2.  The side faces on the perimeter of the entire 3D shape.
3.  The side faces in the 'valleys' between adjacent towers of different heights.

This can be calculated in a single pass. For each cell `(i, j)` with height `v`, we add contributions from its top/bottom, front/back, and left/right faces. We handle boundaries by considering the height of a non-existent tower outside the grid as 0.

```java
class Solution {
    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int totalArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int v = grid[i][j];
                if (v > 0) {
                    // Top and bottom faces
                    totalArea += 2;
                }

                // Exposed faces between current and upper cell
                int up = (i > 0) ? grid[i - 1][j] : 0;
                totalArea += Math.abs(v - up);

                // Exposed faces between current and left cell
                int left = (j > 0) ? grid[i][j - 1] : 0;
                totalArea += Math.abs(v - left);
            }
        }

        // Add the rightmost and bottommost faces which were not covered
        for (int i = 0; i < n; i++) {
            totalArea += grid[i][n - 1]; // Rightmost column faces
            totalArea += grid[n - 1][i]; // Bottommost row faces
        }

        return totalArea;
    }
}
```
### Algorithm
1. Initialize `totalArea = 0`.
2. Iterate through each cell `(i, j)` of the `n x n` grid.
3. For each cell, get the height `v = grid[i][j]`.
4. **Top and Bottom Faces:** If `v > 0`, it means there's a tower, so add `2` to `totalArea` for its top and bottom faces.
5. **Side Faces (Front/Back):** Calculate the exposed vertical area between the current tower at `(i, j)` and the one above it at `(i-1, j)`. This is the absolute difference in their heights. Add `abs(v - grid[i-1][j])` to `totalArea`. If `i` is `0`, the tower is at the edge, so the entire front face is exposed; add `v`.
6. **Side Faces (Left/Right):** Similarly, calculate the exposed vertical area between the current tower at `(i, j)` and the one to its left at `(i, j-1)`. Add `abs(v - grid[i][j-1])` to `totalArea`. If `j` is `0`, add `v`.
7. The main loop only considers overlaps with `up` and `left` neighbors. After the loop, the faces on the rightmost and bottommost boundaries of the grid are not yet counted. 
8. Add the areas of the rightmost faces: iterate through each row `i` and add `grid[i][n-1]` to `totalArea`.
9. Add the areas of the bottommost faces: iterate through each column `j` and add `grid[n-1][j]` to `totalArea`.
10. Return `totalArea`.

## Single-Pass Calculation by Subtracting Overlaps
This approach is the most streamlined and efficient. It relies on a simple mathematical formula applied in a single pass over the grid. The core idea is to calculate the total surface area by first assuming all towers are separate and then subtracting the areas of the faces that become hidden when the towers are placed next to each other.
**Time:** O(N*N). The algorithm consists of a single pass through the `n x n` grid. · **Space:** O(1). No extra space proportional to the input size is needed.
**Pros:** Optimal `O(N^2)` time complexity.; Optimal `O(1)` space complexity.; Extremely elegant and concise implementation within a single loop.
**Cons:** The logic of adding a gross amount and then subtracting might be slightly less direct to visualize than summing up exposed faces, but it leads to a very clean implementation.
### Explanation
We iterate through each cell of the grid. For each cell `(i, j)` containing a tower of height `v = grid[i][j]`, we start by adding the full surface area of that tower as if it stood alone (`4*v + 2`). Then, we account for the fact that it's adjacent to other towers. As we process the grid in a standard row-by-row, column-by-column fashion, the tower at `(i, j)` can only be adjacent to previously processed towers at `(i-1, j)` (above) and `(i, j-1)` (to the left). 

For each of these adjacencies, a certain area is covered up. The area of the shared face between two towers of height `v1` and `v2` is `min(v1, v2)`. Since this face is covered for both towers, the total reduction in surface area is `2 * min(v1, v2)`. By subtracting these overlapping areas as we go, we maintain a running total that correctly reflects the surface area of the shape formed by all towers processed so far. This results in a very concise and efficient single-loop solution.

```java
class Solution {
    public int surfaceArea(int[][] grid) {
        int n = grid.length;
        int surfaceArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int v = grid[i][j];

                if (v > 0) {
                    // Add surface area of an isolated tower of height v
                    surfaceArea += (v * 4) + 2;

                    // Subtract shared face with the tower above
                    if (i > 0) {
                        surfaceArea -= Math.min(v, grid[i - 1][j]) * 2;
                    }

                    // Subtract shared face with the tower to the left
                    if (j > 0) {
                        surfaceArea -= Math.min(v, grid[i][j - 1]) * 2;
                    }
                }
            }
        }
        return surfaceArea;
    }
}
```
### Algorithm
1. Initialize `surfaceArea = 0`.
2. Iterate through each cell `(i, j)` of the `n x n` grid.
3. Let `v = grid[i][j]` be the height of the tower at the current cell.
4. If `v > 0`, there is a tower. First, add the total surface area of this tower as if it were isolated. An isolated tower of `v` cubes has a surface area of `4 * v` (for the sides) + `2` (for the top and bottom). So, `surfaceArea += (4 * v + 2)`.
5. Now, subtract the area of the faces that are hidden because of adjacent towers. Since we are iterating from top-left to bottom-right, we only need to check for overlaps with the towers that have already been processed: the one above `(i-1, j)` and the one to the left `(i, j-1)`.
6. **Vertical Overlap:** If `i > 0`, there is a tower above. The two towers at `(i, j)` and `(i-1, j)` hide a portion of their sides from each other. The area of this shared face is `min(v, grid[i-1][j])`. Since this face is hidden for both towers, we subtract `2 * min(v, grid[i-1][j])` from the total area.
7. **Horizontal Overlap:** If `j > 0`, there is a tower to the left. Similarly, the shared area is `min(v, grid[i][j-1])`. We subtract `2 * min(v, grid[i][j-1])` from the total area.
8. After iterating through all cells, `surfaceArea` will hold the correct total.

# Solutions
### Java

```java
class Solution { public int surfaceArea ( int [][] grid ) { int n = grid . length ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( grid [ i ][ j ] > 0 ) { ans += 2 + grid [ i ][ j ] * 4 ; if ( i > 0 ) { ans -= Math . min ( grid [ i ][ j ], grid [ i - 1 ][ j ]) * 2 ; } if ( j > 0 ) { ans -= Math . min ( grid [ i ][ j ], grid [ i ][ j - 1 ]) * 2 ; } } } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int surfaceArea ( vector < vector < int >>& grid ) { int n = grid . size (); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( grid [ i ][ j ]) { ans += 2 + grid [ i ][ j ] * 4 ; if ( i ) ans -= min ( grid [ i ][ j ], grid [ i - 1 ][ j ]) * 2 ; if ( j ) ans -= min ( grid [ i ][ j ], grid [ i ][ j - 1 ]) * 2 ; } } } return ans ; } };
```

### Python

```python
class Solution : def surfaceArea ( self , grid : List [ List [ int ]]) -> int : ans = 0 for i , row in enumerate ( grid ): for j , v in enumerate ( row ): if v : ans += 2 + v * 4 if i : ans -= min ( v , grid [ i - 1 ][ j ]) * 2 if j : ans -= min ( v , grid [ i ][ j - 1 ]) * 2 return ans
```