LeetCode 892 - Surface Area of 3D Shapes

The problem gives us an n x n matrix called grid, where each cell contains a non-negative integer. The value grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j). Each cube contributes surface area through its exposed faces.

leetcodeeasyarraymathgeometrymatrix

LeetCode Problem 892

Difficulty: 🟢 Easy
Topics: Array, Math, Geometry, Matrix

Solution

Problem Understanding

The problem gives us an n x n matrix called grid, where each cell contains a non-negative integer. The value grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j).

Each cube contributes surface area through its exposed faces. A single cube has 6 faces, but when cubes touch each other, the touching faces become internal and no longer contribute to the total surface area.

The goal is to compute the total exposed surface area of the entire 3D structure formed by all stacks in the grid. Importantly, the bottom faces count toward the surface area, even though they rest on the ground.

For example, if a cell contains 3, that means three cubes are stacked vertically. Without any adjacent cubes, the stack contributes:

  • 2 faces for the top and bottom
  • 4 side faces for each layer

However, cubes inside the same vertical stack share faces with each other, and neighboring stacks also share faces horizontally.

The constraints are relatively small:

  • 1 <= n <= 50
  • 0 <= grid[i][j] <= 50

This means the grid can contain at most 2500 cells, and each stack can contain at most 50 cubes. Because the input size is modest, an O(n^2) solution is more than sufficient.

Several edge cases are important:

  • Cells with value 0 contain no cubes and contribute nothing.
  • A single isolated cube contributes all 6 faces.
  • Large neighboring stacks hide many faces from each other.
  • Uneven neighboring heights require subtracting only the overlapping portion.
  • Entire rows or columns of zeros should not affect the result.

A naive implementation can easily double count shared faces between adjacent stacks, which is the most common source of bugs in this problem.

Approaches

Brute Force Approach

A brute force solution would model every cube individually.

For each cell (i, j) with height h, we could imagine placing h separate cubes in 3D space. Each cube initially contributes 6 faces. Then, for every cube, we check all six directions to determine whether a neighboring cube exists. If a neighboring cube exists, that face is hidden and should not be counted.

This approach is correct because it directly simulates the actual geometry of the structure. Every exposed face is counted exactly once.

However, this solution is unnecessarily expensive because it treats every cube separately. In the worst case:

  • The grid contains 50 x 50 = 2500 cells
  • Each cell contains 50 cubes
  • Total cubes = 125000

Checking all neighbors for every cube becomes much more work than necessary.

Optimal Approach

The key observation is that we do not need to model individual cubes.

Instead, we can compute the contribution of each stack mathematically.

For any stack with height h > 0:

  • The top face contributes 1
  • The bottom face contributes 1
  • The four sides contribute 4 * h

So the initial contribution is:

$2 + 4h$

However, adjacent stacks hide faces from each other.

If two neighboring stacks have heights a and b, then the number of hidden faces between them is:

$2\min(a,b)$

This works because each overlapping layer hides one face from each stack.

Instead of checking all four neighbors and risking double counting, we only compare:

  • current cell with the cell above
  • current cell with the cell to the left

This ensures every shared boundary is processed exactly once.

The final algorithm processes each cell once and performs only constant work per cell.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * h) O(1) or O(n² * h) Simulates every individual cube and checks neighboring cubes
Optimal O(n²) O(1) Computes exposed area mathematically using stack heights

Algorithm Walkthrough

  1. Initialize a variable surface_area to 0.

This variable will accumulate the total exposed surface area of the entire structure. 2. Iterate through every cell (row, col) in the grid.

Each cell represents one vertical stack of cubes. 3. Read the height of the current stack.

Let:

height = grid[row][col]

If height == 0, skip the cell because no cubes exist there. 4. Add the standalone contribution of the stack.

Every non-empty stack contributes:

  • one top face
  • one bottom face
  • four vertical sides

So we add:

$2 + 4h$ 5. Remove hidden faces shared with the stack above.

If there is a row above the current cell, compute the overlap:

overlap = min(current_height, upper_height)

Every overlapping layer hides two faces, one from each stack.

So subtract:

$2\min(a,b)$ 6. Remove hidden faces shared with the stack to the left.

Use the same logic for the left neighbor.

Again, subtract twice the overlapping height. 7. Continue until all cells are processed. 8. Return surface_area.

Why it works

The algorithm works because every stack initially contributes all of its potentially visible faces. Whenever two stacks touch, the shared faces become internal and should not count toward the exterior surface area.

By subtracting twice the overlap between neighboring stacks, we remove exactly the faces that become hidden. Since we only compare each neighboring pair once, no shared surface is double counted or missed.

Python Solution

from typing import List

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

        for row in range(n):
            for col in range(n):
                height = grid[row][col]

                if height == 0:
                    continue

                # Top and bottom faces
                surface_area += 2

                # Four side faces
                surface_area += 4 * height

                # Remove shared faces with upper neighbor
                if row > 0:
                    surface_area -= 2 * min(
                        height,
                        grid[row - 1][col]
                    )

                # Remove shared faces with left neighbor
                if col > 0:
                    surface_area -= 2 * min(
                        height,
                        grid[row][col - 1]
                    )

        return surface_area

The implementation follows the mathematical observation directly.

The nested loops iterate through every cell in the grid. For each non-zero stack, we first add its full contribution as if it were isolated.

The code then checks only the upper and left neighbors. This is important because checking all four directions would double count shared surfaces.

The subtraction step removes hidden faces created by adjacent stacks. Using min(height, neighbor_height) correctly handles uneven stack heights because only the overlapping portion becomes hidden.

The algorithm uses only a few integer variables, so the space usage remains constant.

Go Solution

func surfaceArea(grid [][]int) int {
    n := len(grid)
    surfaceArea := 0

    for row := 0; row < n; row++ {
        for col := 0; col < n; col++ {
            height := grid[row][col]

            if height == 0 {
                continue
            }

            // Top and bottom faces
            surfaceArea += 2

            // Four side faces
            surfaceArea += 4 * height

            // Remove shared faces with upper neighbor
            if row > 0 {
                overlap := min(height, grid[row-1][col])
                surfaceArea -= 2 * overlap
            }

            // Remove shared faces with left neighbor
            if col > 0 {
                overlap := min(height, grid[row][col-1])
                surfaceArea -= 2 * overlap
            }
        }
    }

    return surfaceArea
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go implementation mirrors the Python logic closely.

Go does not provide a built-in min function for integers, so we define a helper function manually.

Slices are used naturally for the 2D grid representation. Since the constraints are small, integer overflow is not a concern because the maximum possible surface area easily fits within Go's int type.

Unlike Python, Go requires explicit variable declarations and type definitions, but the underlying algorithm remains identical.

Worked Examples

Example 1

Input:

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

We process each cell one by one.

Cell Height Initial Contribution Overlap Removed Running Total
(0,0) 1 2 + 4 = 6 0 6
(0,1) 2 2 + 8 = 10 left overlap = 2 14
(1,0) 3 2 + 12 = 14 upper overlap = 2 26
(1,1) 4 2 + 16 = 18 upper overlap = 4, left overlap = 6 34

Final answer:

34

Example 2

Input:

grid = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]

The center cell is empty, so it contributes nothing.

Cell Height Added Removed Running Total
(0,0) 1 6 0 6
(0,1) 1 6 2 10
(0,2) 1 6 2 14
(1,0) 1 6 2 18
(1,1) 0 0 0 18
(1,2) 1 6 2 22
(2,0) 1 6 2 26
(2,1) 1 6 2 30
(2,2) 1 6 4 32

Final answer:

32

Example 3

Input:

grid = [
    [2,2,2],
    [2,1,2],
    [2,2,2]
]

Every outer stack has height 2, while the center stack has height 1.

The repeated overlaps between neighboring stacks significantly reduce the visible surface area.

Cell Height Added Removed Running Total
(0,0) 2 10 0 10
(0,1) 2 10 4 16
(0,2) 2 10 4 22
(1,0) 2 10 4 28
(1,1) 1 6 4 30
(1,2) 2 10 6 34
(2,0) 2 10 4 40
(2,1) 2 10 6 44
(2,2) 2 10 8 46

Final answer:

46

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every grid cell is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs constant work per cell. Since the grid contains n² cells, the runtime is proportional to the number of cells.

No additional data structures are allocated that scale with input size, so the extra memory usage remains constant.

Test Cases

from typing import List

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

        for row in range(n):
            for col in range(n):
                height = grid[row][col]

                if height == 0:
                    continue

                surface_area += 2
                surface_area += 4 * height

                if row > 0:
                    surface_area -= 2 * min(
                        height,
                        grid[row - 1][col]
                    )

                if col > 0:
                    surface_area -= 2 * min(
                        height,
                        grid[row][col - 1]
                    )

        return surface_area

solution = Solution()

assert solution.surfaceArea([[1, 2], [3, 4]]) == 34
# Provided example with varying heights

assert solution.surfaceArea([[1,1,1],[1,0,1],[1,1,1]]) == 32
# Provided example with center hole

assert solution.surfaceArea([[2,2,2],[2,1,2],[2,2,2]]) == 46
# Provided example with uneven center

assert solution.surfaceArea([[1]]) == 6
# Single cube

assert solution.surfaceArea([[0]]) == 0
# Empty grid cell

assert solution.surfaceArea([[5]]) == 22
# Single tall stack

assert solution.surfaceArea([[1,1]]) == 10
# Two adjacent cubes sharing one face pair

assert solution.surfaceArea([[1],[1]]) == 10
# Vertical adjacency in grid

assert solution.surfaceArea([[2,2]]) == 16
# Equal neighboring towers

assert solution.surfaceArea([[1,3]]) == 18
# Uneven neighboring towers

assert solution.surfaceArea([[50]]) == 202
# Maximum tower height

assert solution.surfaceArea([[0,0],[0,0]]) == 0
# Entire grid empty
Test Why
[[1,2],[3,4]] Verifies general uneven stacks
[[1,1,1],[1,0,1],[1,1,1]] Tests handling of empty center cell
[[2,2,2],[2,1,2],[2,2,2]] Tests multiple overlaps
[[1]] Smallest non-empty input
[[0]] Completely empty structure
[[5]] Tall isolated tower
[[1,1]] Horizontal shared face
[[1],[1]] Vertical shared face
[[2,2]] Equal-height neighboring stacks
[[1,3]] Uneven overlap handling
[[50]] Maximum stack height
[[0,0],[0,0]] Entire grid contains no cubes

Edge Cases

One important edge case is a completely empty grid, such as [[0]] or a larger grid filled entirely with zeros. A naive implementation might still add top and bottom faces for each cell without checking whether cubes actually exist. The implementation avoids this by immediately skipping cells whose height is zero.

Another important edge case is uneven neighboring stacks, such as [[1,3]]. A buggy implementation might subtract too many shared faces by assuming the taller stack completely hides the shorter one. The correct logic subtracts only 2 * min(a, b), which removes exactly the overlapping hidden faces and preserves the exposed upper portion of the taller stack.

A third important edge case involves double counting adjacent overlaps. If the algorithm checked all four directions for every cell, each shared boundary would be processed twice. That would subtract too many faces and produce incorrect results. The implementation avoids this by checking only the upper and left neighbors, ensuring every shared boundary is handled exactly once.