Projection Area of 3D Shapes
EasyPrompt
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: 5Example 3:
Input: grid = [[1,0],[0,2]]
Output: 8
Constraints:
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
This approach calculates the total projection area by first iterating through the grid once to compute the top-down projection area (xy-plane) and simultaneously finding the maximum height in each row and column. These maximums are stored in auxiliary arrays. Finally, the areas from the front (yz-plane) and side (zx-plane) projections are calculated by summing the values in these auxiliary arrays.
Algorithm
- Get the dimension
nof the grid. - Initialize
xyArea = 0. - Initialize two integer arrays,
rowMaxesandcolMaxes, of sizento all zeros. - Iterate
ifrom0ton-1:- Iterate
jfrom0ton-1:- If
grid[i][j] > 0, incrementxyArea. - Update
rowMaxes[i] = max(rowMaxes[i], grid[i][j]). - Update
colMaxes[j] = max(colMaxes[j], grid[i][j]).
- If
- Iterate
- Initialize
totalArea = xyArea. - Iterate
kfrom0ton-1:- Add
rowMaxes[k]tototalArea. - Add
colMaxes[k]tototalArea.
- Add
- Return
totalArea.
Walkthrough
The total projection area is the sum of three individual projection areas:
- Top-down (xy-plane): The area is the number of cells in the grid with a height greater than 0.
- Side (zx-plane): The area is the sum of the maximum heights in each row.
- Front (yz-plane): The area is the sum of the maximum heights in each column.
We can calculate all of these with an initial pass over the grid. We use two arrays, rowMaxes and colMaxes, of size n to store the maximum height for each row and column, respectively. We iterate through each cell grid[i][j], increment the top-down projection area if the cell is non-zero, and update the maximums for its corresponding row and column. After iterating through the entire grid, we sum up all values in rowMaxes and colMaxes and add them to the top-down area to get the final result.
class Solution { public int projectionArea(int[][] grid) { int n = grid.length; int xyArea = 0; int[] rowMaxes = new int[n]; int[] colMaxes = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] > 0) { xyArea++; } rowMaxes[i] = Math.max(rowMaxes[i], grid[i][j]); colMaxes[j] = Math.max(colMaxes[j], grid[i][j]); } } int totalArea = xyArea; for (int i = 0; i < n; i++) { totalArea += rowMaxes[i]; totalArea += colMaxes[i]; } return totalArea; }}Complexity
Time
O(n^2). We iterate through the `n x n` grid once, which takes O(n^2) time. Then we iterate through the two auxiliary arrays of size `n`, which takes O(n) time. The total time complexity is O(n^2 + n) = O(n^2).
Space
O(n). We use two arrays, `rowMaxes` and `colMaxes`, each of size `n`, to store the maximums. This results in O(n) auxiliary space.
Trade-offs
Pros
The logic is straightforward, separating the collection of maximums from the final summation.
It processes the grid in a single pass.
Cons
Requires extra space proportional to the grid dimension
n, which is less efficient than O(1) space solutions.
This approach calculates the total projection area by breaking the problem down into three distinct parts, one for each plane of projection. It iterates through the grid or its dimensions three times, once for each projection, and accumulates the area in a running total.
Algorithm
- Get the dimension
nof the grid. - Initialize
totalArea = 0. - Calculate xy-plane area:
- Iterate
ifrom0ton-1. - Iterate
jfrom0ton-1. - If
grid[i][j] > 0, incrementtotalArea.
- Iterate
- Calculate zx-plane area (row maxes):
- Iterate
ifrom0ton-1. - Find the maximum value
rowMaxingrid[i]. - Add
rowMaxtototalArea.
- Iterate
- Calculate yz-plane area (column maxes):
- Iterate
jfrom0ton-1. - Find the maximum value
colMaxin thej-th column. - Add
colMaxtototalArea.
- Iterate
- Return
totalArea.
Walkthrough
The total area is the sum of the areas of the three projections. This method calculates each one sequentially.
- Top-down (xy-plane) Projection: Iterate through every cell
(i, j)of the grid. Ifgrid[i][j] > 0, it means there's a tower of cubes at this position, which casts a1x1shadow on thexyplane. Add 1 to the total area for each such cell. - Side (zx-plane) Projection: For each row
i, the area of the projection is determined by the tallest tower in that row. Iterate through each row, find the maximum value, and add it to the total area. - Front (yz-plane) Projection: Similarly, for each column
j, the area of the projection is the height of the tallest tower in that column. Iterate through each column, find the maximum value, and add it to the total area.
class Solution { public int projectionArea(int[][] grid) { int n = grid.length; int totalArea = 0; // 1. Top-down (xy-plane) projection area for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] > 0) { totalArea++; } } } // 2. Side (zx-plane) projection area for (int i = 0; i < n; i++) { int rowMax = 0; for (int j = 0; j < n; j++) { rowMax = Math.max(rowMax, grid[i][j]); } totalArea += rowMax; } // 3. Front (yz-plane) projection area for (int j = 0; j < n; j++) { int colMax = 0; for (int i = 0; i < n; i++) { colMax = Math.max(colMax, grid[i][j]); } totalArea += colMax; } return totalArea; }}Complexity
Time
O(n^2). Each of the three parts involves iterating through the `n x n` grid or its equivalent. The first part is O(n^2), the second is O(n^2), and the third is O(n^2). The total time complexity is O(n^2 + n^2 + n^2) = O(n^2).
Space
O(1). This approach only uses a few variables to store the running total and temporary maximums, not requiring any extra space that scales with the input size.
Trade-offs
Pros
Very space-efficient, using only constant extra space.
The logic is clear and easy to follow as it handles each projection independently.
Cons
It iterates over the grid data multiple times, which can be less efficient in terms of cache performance and total operations compared to a single-pass solution.
This is the most efficient approach. It calculates the total area of all three projections in a single pass through the grid's dimensions. By cleverly structuring the loops, it computes the top-down area, the sum of row maximums, and the sum of column maximums simultaneously.
Algorithm
- Get the dimension
nof the grid. - Initialize
xyArea = 0,yzArea = 0,zxArea = 0. - Iterate
ifrom0ton-1:- Initialize
rowMax = 0(for the max of rowi). - Initialize
colMax = 0(for the max of columni). - Iterate
jfrom0ton-1:- If
grid[i][j] > 0, incrementxyArea. - Update
rowMax = max(rowMax, grid[i][j]). - Update
colMax = max(colMax, grid[j][i]).
- If
- Add
rowMaxtozxArea. - Add
colMaxtoyzArea.
- Initialize
- Return
xyArea + yzArea + zxArea.
Walkthrough
This approach is the most efficient, calculating the total projection area in a single, consolidated pass. It cleverly combines the calculation for all three projections (xy, yz, zx) into one nested loop structure.
The main idea is to iterate from i = 0 to n-1. In each iteration i, we find the maximum of row i and the maximum of column i. The top-down projection area is calculated by iterating through all cells and counting the non-zero ones. All these calculations are performed within a single O(n^2) loop structure.
class Solution { public int projectionArea(int[][] grid) { int n = grid.length; int xyArea = 0; // Top-down projection int yzArea = 0; // Front projection int zxArea = 0; // Side projection for (int i = 0; i < n; i++) { int rowMax = 0; // Max height in current row i int colMax = 0; // Max height in current column i for (int j = 0; j < n; j++) { // Top-down projection: add 1 for any non-zero cube if (grid[i][j] > 0) { xyArea++; } // Side projection: find max in row i rowMax = Math.max(rowMax, grid[i][j]); // Front projection: find max in column i // We use grid[j][i] to traverse column i while the outer loop is on row i colMax = Math.max(colMax, grid[j][i]); } zxArea += rowMax; yzArea += colMax; } return xyArea + yzArea + zxArea; }}Complexity
Time
O(n^2). We have a single nested loop structure that iterates through `n*n` elements. Accessing `grid[i][j]` and `grid[j][i]` are both O(1) operations. Thus, the total time complexity is dominated by the nested loops, resulting in O(n^2).
Space
O(1). We only use a few variables (`xyArea`, `yzArea`, `zxArea`, `rowMax`, `colMax`) to store intermediate results. The space required does not scale with the input size `n`.
Trade-offs
Pros
Optimal time complexity, as we must look at every element at least once.
Optimal space complexity, using only a constant amount of extra memory.
High performance due to a single pass over the data, which leads to good cache locality.
Cons
The logic of calculating column maxes using
grid[j][i]while iterating by rows might be slightly less intuitive at first glance compared to separate passes.
Solutions
Solution
class Solution {public int projectionArea(int[][] grid) { int xy = 0, yz = 0, zx = 0; for (int i = 0, n = grid.length; i < n; ++i) { int maxYz = 0; int maxZx = 0; for (int j = 0; j < n; ++j) { if (grid[i][j] > 0) { ++xy; } maxYz = Math.max(maxYz, grid[i][j]); maxZx = Math.max(maxZx, grid[j][i]); } yz += maxYz; zx += maxZx; } return xy + yz + zx; }}class Solution { public: int projectionArea ( vector < vector < int >>& grid ) { int xy = 0 , yz = 0 , zx = 0 ; for ( int i = 0 , n = grid . size (); i < n ; ++ i ) { int maxYz = 0 , maxZx = 0 ; for ( int j = 0 ; j < n ; ++ j ) { xy += grid [ i ][ j ] > 0 ; maxYz = max ( maxYz , grid [ i ][ j ]); maxZx = max ( maxZx , grid [ j ][ i ]); } yz += maxYz ; zx += maxZx ; } return xy + yz + zx ; } };class Solution: def projectionArea(self, grid: List[List[int]]) -> int: xy = sum(v > 0 for row in grid for v in row) yz = sum(max(row) for row in grid) zx = sum(max(col) for col in zip(* grid)) return xy + yz + zxVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.