LeetCode 892: Surface Area of 3D Shapes

Problem Restatement

We are given an n x n grid.

Each value:

grid[i][j]

represents a tower of grid[i][j] unit cubes placed on cell (i, j).

After placing the cubes, directly adjacent cubes are glued together. We need to return the total exposed surface area of the resulting 3D shape.

The bottom face counts as part of the surface area. LeetCode defines each cube as 1 x 1 x 1, and adjacent cubes share faces that are no longer exposed.

Input and Output

Function shape:

def surfaceArea(self, grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

Input: grid = [[2]]
Output: 10

A tower of height 2 has:

Total:

1 + 1 + 8 = 10

Example 2:

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

First, compute each tower as if it stood alone:

Initial total:

6 + 10 + 14 + 18 = 48

Now subtract shared faces between adjacent towers.

Adjacent pairs:

Total subtraction:

2 + 2 + 4 + 6 = 14

Final answer:

48 - 14 = 34

First Thought: Count Every Cube Face

A direct approach is to inspect every cube one by one.

Each cube starts with 6 faces. For each neighboring cube that touches it, one face becomes hidden.

This works, but it is more detailed than needed.

A tower of cubes has a simple formula, and neighboring towers have a simple overlap rule.

Key Insight

A non-empty tower of height h contributes:

4 * h + 2

Why?

So an isolated tower contributes:

4 * h + 2

When two adjacent towers have heights a and b, they touch along:

min(a, b)

unit squares.

Each shared square hides one face from each tower, so we subtract:

2 * min(a, b)

We only need to check each adjacent pair once. A convenient way is to check the top neighbor and the left neighbor for each cell.

Algorithm

Initialize:

answer = 0

For every cell (i, j):

1. Let height = grid[i][j].
2. If height > 0, add:

4 * height + 2

3. If there is a tower above, subtract:

2 * min(height, grid[i - 1][j])

4. If there is a tower to the left, subtract:

2 * min(height, grid[i][j - 1])

Return answer.

Walkthrough

Use:

grid = [
    [1, 2],
    [3, 4]
]

Process each tower:

Total before shared faces:

48

Subtract shared faces:

Final:

48 - 14 = 34

Correctness

For every non-empty cell, the algorithm first adds the surface area of that tower as if it were isolated. A tower of height h has one top face, one bottom face, and four vertical sides of height h, so its isolated surface area is 4 * h + 2.

This counts all exposed faces, but it also counts faces that are hidden because two neighboring towers touch.

For any two adjacent towers with heights a and b, exactly min(a, b) cube faces touch on one side. Since each contact hides one face from each tower, the isolated sum overcounts by 2 * min(a, b).

The algorithm subtracts this amount once for every adjacent pair by checking only the above and left neighbors. Therefore, every hidden shared face is removed exactly once, and no shared face is subtracted twice.

After all cells are processed, the remaining count is exactly the exposed surface area of the glued shape.

Complexity

Let:

n = len(grid)

Implementation

class Solution:
    def surfaceArea(self, grid: list[list[int]]) -> int:
        n = len(grid)
        answer = 0

        for i in range(n):
            for j in range(n):
                height = grid[i][j]

                if height > 0:
                    answer += 4 * height + 2

                if i > 0:
                    answer -= 2 * min(height, grid[i - 1][j])

                if j > 0:
                    answer -= 2 * min(height, grid[i][j - 1])

        return answer

Code Explanation

We scan every cell:

for i in range(n):
    for j in range(n):

For each cell, height is the tower height:

height = grid[i][j]

If the tower exists, we add its isolated surface area:

if height > 0:
    answer += 4 * height + 2

Then we subtract shared area with the tower above:

if i > 0:
    answer -= 2 * min(height, grid[i - 1][j])

and shared area with the tower to the left:

if j > 0:
    answer -= 2 * min(height, grid[i][j - 1])

Checking only above and left counts each adjacent pair once.

Testing

def run_tests():
    s = Solution()

    assert s.surfaceArea([[2]]) == 10
    assert s.surfaceArea([[1, 2], [3, 4]]) == 34
    assert s.surfaceArea([[1, 0], [0, 2]]) == 16
    assert s.surfaceArea([[0]]) == 0
    assert s.surfaceArea([[1, 1], [1, 1]]) == 16
    assert s.surfaceArea([[3, 3, 3]]) == 26

    print("all tests passed")

run_tests()

Test meaning: