LeetCode 883: Projection Area of 3D Shapes

Problem Restatement

We are given an n x n grid.

Each cell:

grid[r][c]

contains a vertical stack of cubes.

We want the total projection area of the 3D shape onto three planes:

Return the sum of these three projection areas. The official problem defines each cube as a 1 x 1 x 1 cube aligned to the axes. (leetcode.com)

Input and Output

Function shape:

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

Examples

Example 1:

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

Top projection:

Every nonzero cell contributes 1.

There are 4 nonzero cells:

top = 4

Front projection uses the largest value in each row:

front = 2 + 4 = 6

Side projection uses the largest value in each column:

side = 3 + 4 = 7

Total:

4 + 6 + 7 = 17

Example 2:

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

Top projection:

1

Front projection:

2

Side projection:

2

Total:

1 + 2 + 2 = 5

First Thought: Simulate Every Cube

We could imagine building the entire 3D structure cube by cube.

Then for each viewing direction, determine which cubes are visible.

This works conceptually, but it is unnecessary.

The projections follow simple patterns that can be computed directly from the grid values.

Key Insight

Each projection can be computed independently.

Top Projection

Looking from above, a cell contributes area 1 if it contains at least one cube.

So the top projection equals:

number of nonzero cells

Front Projection

Looking from the front, each row contributes the height of its tallest stack.

So the front projection equals:

sum of row maximums

Side Projection

Looking from the side, each column contributes the height of its tallest stack.

So the side projection equals:

sum of column maximums

The total answer is:

top + front + side

Algorithm

Initialize:

answer = 0

For each row:

1. Count nonzero cells for the top projection.
2. Add the row maximum for the front projection.

For each column:

1. Add the column maximum for the side projection.

Return the total.

Walkthrough

Use:

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

Top Projection

Every nonzero cell contributes 1.

Total:

4

Front Projection

Take the maximum of each row:

Total:

6

Side Projection

Take the maximum of each column:

Total:

7

Final answer:

4 + 6 + 7 = 17

Correctness

The top projection shows whether at least one cube exists in each grid position. A stack of height 1 and a stack of height 100 both cover exactly one square in the top view. Therefore, every nonzero cell contributes exactly 1 area to the top projection.

The front projection looks across each row. In a row, shorter stacks are hidden behind the tallest stack. Therefore, the visible height contributed by a row is exactly the maximum value in that row. Summing row maximums gives the full front projection area.

The side projection works similarly for columns. In each column, only the tallest stack determines the visible height from the side. Therefore, summing column maximums gives the side projection area.

The three projections are independent and non-overlapping measurements. Adding them together gives the total projection area required by the problem.

Thus, the algorithm computes the correct total projection area.

Complexity

Let:

n = len(grid)

Implementation

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

        top = 0
        front = 0
        side = 0

        for row in grid:
            front += max(row)

            for value in row:
                if value > 0:
                    top += 1

        for col in range(n):
            column_max = 0

            for row in range(n):
                column_max = max(column_max, grid[row][col])

            side += column_max

        return top + front + side

Code Explanation

We track the three projection areas separately:

top = 0
front = 0
side = 0

For each row:

for row in grid:

the front projection gains the tallest stack:

front += max(row)

Every nonzero cell contributes to the top projection:

if value > 0:
    top += 1

Then we process columns:

for col in range(n):

We find the tallest stack in each column:

column_max = max(column_max, grid[row][col])

and add it to the side projection:

side += column_max

Finally, return the sum of all three projections:

return top + front + side

Testing

def run_tests():
    s = Solution()

    assert s.projectionArea([[1, 2], [3, 4]]) == 17
    assert s.projectionArea([[2]]) == 5
    assert s.projectionArea([[1, 0], [0, 2]]) == 8
    assert s.projectionArea([[0]]) == 0
    assert s.projectionArea([[1, 1, 1]]) == 5
    assert s.projectionArea([[1], [2], [3]]) == 10

    print("all tests passed")

run_tests()

Test meaning: