LeetCode 883 - Projection Area of 3D Shapes

The problem gives us an n x n matrix called grid. Each cell grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j) on a flat surface.

leetcodeeasyarraymathgeometrymatrix

LeetCode Problem 883

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

Solution

Problem Understanding

The problem gives us an n x n matrix called grid. Each cell grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j) on a flat surface.

We must calculate the total area of the projections of this 3D structure onto three planes:

  • The xy plane, which is the top view
  • The yz plane, which is the front view
  • The zx plane, which is the side view

A projection is essentially the visible shadow of the structure when viewed from a specific direction.

To understand the projections clearly:

  • The xy projection looks from above. Any cell containing at least one cube contributes 1 unit of area because the stack occupies that position on the floor.
  • The yz projection looks from the side along rows. For each row, only the tallest stack matters because shorter stacks are hidden behind it.
  • The zx projection looks from the front along columns. For each column, only the tallest stack contributes to the visible area.

The final answer is the sum of these three projection areas.

The constraints are small:

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

This means the matrix is at most 50 x 50, which contains only 2500 cells. Because the input size is small, even less efficient solutions would work, but the problem has a very clean optimal approach that runs in linear time relative to the number of cells.

An important detail is that cells may contain 0, meaning no cubes are present at that position. Those cells contribute nothing to the top projection and do not affect row or column maximums unless every value in that row or column is zero.

Several edge cases are important:

  • A grid containing all zeros should return 0
  • A 1 x 1 grid must correctly combine all three projections from a single stack
  • Rows or columns with multiple equal maximum heights should only contribute that maximum once
  • Sparse grids with many zeros should still correctly compute row and column projections

Approaches

Brute Force Approach

A brute force way to think about the problem is to explicitly simulate the projections cube by cube.

For the top projection, we could iterate through every cell and count whether at least one cube exists.

For the side and front projections, we could imagine constructing full 3D representations of the stacks and then determining which cubes are visible from each direction. This could involve scanning every possible height level for every row and column.

Although this method would produce the correct answer, it performs unnecessary work because we do not actually need to model individual cubes. The projections depend only on whether a stack exists and on the maximum height in each row and column.

If the maximum stack height is H, this brute force simulation could require iterating across all height levels, producing a complexity closer to O(n² × H).

Since the problem constraints are small, this would still pass, but it is inefficient and conceptually more complicated than necessary.

Optimal Approach

The key observation is that each projection can be computed independently using simple properties of the grid:

  • The xy projection counts nonzero cells
  • The yz projection uses the maximum value in each row
  • The zx projection uses the maximum value in each column

This means we only need a single traversal of the matrix.

While iterating through the grid:

  • Count every nonzero cell for the top projection
  • Track the maximum value in each row
  • Track the maximum value in each column

At the end:

  • Sum all row maximums
  • Sum all column maximums
  • Add them together with the nonzero cell count

This avoids unnecessary cube-level simulation and gives an efficient and elegant solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² × H) O(1) Simulates cube visibility level by level
Optimal O(n²) O(1) Uses row maximums, column maximums, and nonzero counts

Algorithm Walkthrough

  1. Initialize three variables:
  • top_area for the xy projection
  • front_area for the yz projection
  • side_area for the zx projection
  1. Traverse each row in the grid.
  2. For every row:
  • Find the maximum value in that row
  • Add it to front_area

This works because the tallest stack in the row determines the visible height from the side view. 4. While processing each cell in the row:

  • If the value is greater than zero, increment top_area

This works because any nonzero stack occupies one square in the top projection. 5. After processing rows, process each column. 6. For every column:

  • Find the maximum value among all rows for that column
  • Add it to side_area

This works because the tallest stack in the column determines the visible height from the front view. 7. Return:

top_area + front_area + side_area

Why it works

The algorithm works because each projection depends only on visibility from one direction.

  • From above, every occupied cell contributes exactly one visible square
  • From the side, only the tallest stack in each row remains visible
  • From the front, only the tallest stack in each column remains visible

Since these projections are independent, summing their contributions produces the correct total projection area.

Python Solution

from typing import List

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

        top_area = 0
        front_area = 0
        side_area = 0

        # Process rows
        for row in grid:
            front_area += max(row)

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

        # Process columns
        for col in range(n):
            column_max = 0

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

            side_area += column_max

        return top_area + front_area + side_area

The implementation directly follows the algorithm described earlier.

The variable top_area counts how many cells contain at least one cube. Every nonzero cell contributes one visible square in the top projection.

The variable front_area accumulates the maximum stack height from each row. Using max(row) efficiently finds the visible contribution for the side view.

The column processing loop computes the tallest stack in each column. That maximum contributes to the front projection, and the result is added to side_area.

Finally, the method returns the sum of all three projection areas.

Go Solution

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

	topArea := 0
	frontArea := 0
	sideArea := 0

	// Process rows
	for _, row := range grid {
		rowMax := 0

		for _, value := range row {
			if value > 0 {
				topArea++
			}

			if value > rowMax {
				rowMax = value
			}
		}

		frontArea += rowMax
	}

	// Process columns
	for col := 0; col < n; col++ {
		colMax := 0

		for row := 0; row < n; row++ {
			if grid[row][col] > colMax {
				colMax = grid[row][col]
			}
		}

		sideArea += colMax
	}

	return topArea + frontArea + sideArea
}

The Go implementation mirrors the Python solution closely.

Because Go does not provide a built in max function for integers in the standard language syntax, we manually compare values when computing row and column maximums.

Slices are used naturally for the 2D grid representation. No additional memory allocation is required beyond a few integer variables, so the space complexity remains constant.

Integer overflow is not a concern because the maximum possible answer is small. The largest projection area occurs when every cell contains height 50, giving:

  • Top projection: 2500
  • Row projection: 2500
  • Column projection: 2500

The total is only 7500, well within Go's integer range.

Worked Examples

Example 1

Input:

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

Step 1, Compute Top and Row Projections

Row Row Max Nonzero Count Added
[1, 2] 2 2
[3, 4] 4 2

After processing rows:

  • top_area = 4
  • front_area = 6

Step 2, Compute Column Projections

Column 0:

max(1, 3) = 3

Column 1:

max(2, 4) = 4

So:

  • side_area = 7

Final Answer

4 + 6 + 7 = 17

Output:

17

Example 2

Input:

grid = [[2]]

Step 1, Top Projection

The single cell is nonzero:

top_area = 1

Step 2, Row Projection

Row maximum:

front_area = 2

Step 3, Column Projection

Column maximum:

side_area = 2

Final Answer

1 + 2 + 2 = 5

Output:

5

Example 3

Input:

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

Step 1, Top and Row Projections

Row Row Max Nonzero Count Added
[1, 0] 1 1
[0, 2] 2 1

After rows:

  • top_area = 2
  • front_area = 3

Step 2, Column Projections

Column 0:

max(1, 0) = 1

Column 1:

max(0, 2) = 2

So:

side_area = 3

Final Answer

2 + 3 + 3 = 8

Output:

8

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every cell is processed a constant number of times
Space O(1) Only a few integer variables are used

The algorithm performs one traversal for rows and one traversal for columns. Each traversal touches every grid cell once, so the total work is proportional to n².

No auxiliary data structures proportional to the input size are allocated. Only a few counters and temporary maximum variables are maintained, so the extra space usage is constant.

Test Cases

from typing import List

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

        top_area = 0
        front_area = 0
        side_area = 0

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

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

        for col in range(n):
            column_max = 0

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

            side_area += column_max

        return top_area + front_area + side_area

solution = Solution()

assert solution.projectionArea([[1, 2], [3, 4]]) == 17  # Provided example 1
assert solution.projectionArea([[2]]) == 5  # Provided example 2
assert solution.projectionArea([[1, 0], [0, 2]]) == 8  # Provided example 3

assert solution.projectionArea([[0]]) == 0  # Single empty cell
assert solution.projectionArea([[5]]) == 11  # Single tall stack

assert solution.projectionArea([
    [0, 0],
    [0, 0]
]) == 0  # Entire grid empty

assert solution.projectionArea([
    [1, 1],
    [1, 1]
]) == 8  # Uniform small heights

assert solution.projectionArea([
    [50, 50],
    [50, 50]
]) == 204  # Maximum heights

assert solution.projectionArea([
    [1, 2, 3],
    [4, 0, 6],
    [7, 8, 9]
]) == 53  # Mixed values with zero

assert solution.projectionArea([
    [0, 2, 0],
    [3, 0, 4],
    [0, 5, 0]
]) == 24  # Sparse grid
Test Why
[[1,2],[3,4]] Validates standard mixed heights
[[2]] Validates single cell behavior
[[1,0],[0,2]] Validates sparse diagonal structure
[[0]] Ensures empty structure returns zero
[[5]] Tests single tall tower
all zeros grid Ensures projections handle empty rows and columns
uniform grid Validates repeated equal heights
maximum heights Tests upper constraint values
mixed 3x3 grid Verifies general correctness
sparse grid Tests handling of many zeros

Edge Cases

One important edge case is a grid containing only zeros. In this scenario, there are no cubes anywhere in the structure. A naive implementation might accidentally count rows or columns incorrectly if maximums are initialized improperly. The implementation handles this safely because row and column maximums remain zero, and the top projection counts only values greater than zero.

Another important case is a single cell grid such as [[5]]. Here, the same stack contributes to all three projections simultaneously. The top view contributes 1, while the row and column projections each contribute 5. The implementation naturally handles this because it independently computes each projection.

A third important edge case is sparse grids with many zeros between tall stacks. For example:

[
    [0, 0, 10],
    [0, 0, 0],
    [5, 0, 0]
]

A buggy implementation might incorrectly ignore isolated stacks when computing row or column maximums. This solution correctly scans every row and column independently, ensuring all visible stacks contribute properly to the final answer.

A final edge case involves repeated maximum values in rows or columns. For example:

[
    [4, 4],
    [4, 4]
]

The row projection should count only one maximum per row, not both cells. The implementation uses max(row) and column maximum tracking, so each row and column contributes exactly once regardless of how many cells share the same maximum height.