You are given an n x n grid where we place some 1 x 1 x 1 cubes that are axis-aligned with the x, y, and z axes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of the cell (i, j).
We view the projection of these cubes onto the xy, yz, and zx planes.
A projection is like a shadow, that maps our 3-dimensional figure to a 2-dimensional plane. We are viewing the "shadow" when looking at the cubes from the top, the front, and the side.
Return the total area of all three projections.
Example 1:
Input: grid = [[1,2],[3,4]]
Output: 17
Explanation: Here are the three projections ("shadows") of the shape made with each axis-aligned plane.
Example 2:
Input: grid = [[2]] Output: 5
Example 3:
Input: grid = [[1,0],[0,2]] Output: 8
Constraints:
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] <= 50In #883 Projection Area of 3D Shapes, you are given an n x n grid where each cell represents the height of stacked cubes. The task is to compute the total projection area when the 3D structure is viewed from the top, front, and side.
A clean way to approach this problem is to treat each projection independently. For the top view, every grid cell with a value greater than 0 contributes one unit of area. For the front view, the visible area is determined by the maximum value in each row. Similarly, the side view depends on the maximum value in each column. Summing these three components yields the final projection area.
You can compute all three projections efficiently by scanning the grid and tracking row and column maxima. This approach runs in O(n²) time since every cell is processed once, while using only O(1) extra space aside from a few variables.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row and Column Maximum Tracking | O(n^2) | O(1) |
NeetCode
In this approach, we calculate each plane's projection separately, then sum them up for the total projection area. For the XY-plane projection, we count every cell with a positive value. For the YZ-plane, we determine the maximum value in each row (representing the view from the side). For the ZX-plane, we find the maximum value in each column (representing the view from the front).
Time Complexity: O(n^2) since we traverse each grid element once.
Space Complexity: O(1) since we use no additional space proportional to the input size.
1var projectionArea = function(grid) {
2 let xy = 0, yz = 0, zx = 0;
3 const n = grid.length;
This JavaScript function computes the projection areas using nested loops, checking each element for contribution to the respective plane projections and tallying the results.
This approach improves upon the earlier method by precomputing the maximum values in each row and column before calculating the projections. By storing these values in separate arrays, it helps avoid repeatedly calculating max values within nested loops for each axis projection.
Time Complexity: O(n^2) to fill the grid, row, and column arrays.
Space Complexity: O(n) to store column maximums.
1
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
This exact problem may not always appear in FAANG interviews, but similar matrix and simulation problems are common. It helps candidates practice grid traversal, reasoning about projections, and combining multiple observations into a single solution.
A 2D array (matrix) is the primary data structure used in this problem. Since the grid already represents the heights of cubes, you only need simple variables to track row and column maxima while iterating through the matrix.
The optimal approach computes the projection areas separately for the top, front, and side views. Count all non‑zero cells for the top view, find the maximum value in each row for the front view, and the maximum in each column for the side view. Adding these values gives the final projection area in O(n^2) time.
Row and column maximums represent the tallest stack visible from the front and side views. From these perspectives, shorter stacks behind taller ones are hidden, so only the maximum height in that direction contributes to the projection area.
This C solution uses arrays to store the maximums of rows and columns, improving efficiency slightly from not recalculating these values repeatedly.