Difficulty: Easy | Acceptance: 76.00% | Paid: No Topics: Array, Math, Geometry, Matrix
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 “shadow” when looking at the cubes from the top, the front, and the side.
Return the total area of all three projections.
- Examples
- Constraints
- Direct Calculation
- Single Pass Optimization
Examples
Example 1
Input: grid = [[1,2],[3,4]]
Output: 17
Explanation:
Here are the three projections ("shadow") of the shape made with each axis-aligned plane.
Example 2
Input: grid = [[2]]
Output: 5
Explanation:
The top view has area 1, the front view has area 2, and the side view has area 2.
Example 3
Input: grid = [[1,0],[0,2]]
Output: 8
Constraints
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] <= 50
Direct Calculation
Intuition The projection area is the sum of three separate projections: top view (xy plane), front view (xz plane), and side view (yz plane). We calculate each independently and sum them.
Steps
- Calculate xy projection by counting all non-zero cells
- Calculate yz projection by finding the maximum value in each row and summing them
- Calculate xz projection by finding the maximum value in each column and summing them
- Return the sum of all three projections
class Solution:
def projectionArea(self, grid: list[list[int]]) -> int:
n = len(grid)
xy = 0 # Top view: count of non-zero cells
yz = 0 # Side view: sum of max in each row
xz = 0 # Front view: sum of max in each column
for i in range(n):
row_max = 0
for j in range(n):
if grid[i][j] > 0:
xy += 1
row_max = max(row_max, grid[i][j])
yz += row_max
for j in range(n):
col_max = 0
for i in range(n):
col_max = max(col_max, grid[i][j])
xz += col_max
return xy + yz + xz
Complexity
- Time: O(n²)
- Space: O(1)
- Notes: We iterate through the grid twice, once for rows and once for columns.
Single Pass Optimization
Intuition We can calculate all three projections in a single pass through the grid by maintaining arrays for row maximums and column maximums.
Steps
- Initialize arrays to track maximum values for each row and column
- Iterate through the grid once, updating row maxes, column maxes, and counting non-zero cells
- Sum up the xy projection (non-zero count), yz projection (sum of row maxes), and xz projection (sum of column maxes)
class Solution:
def projectionArea(self, grid: list[list[int]]) -> int:
n = len(grid)
row_max = [0] * n
col_max = [0] * n
xy = 0
for i in range(n):
for j in range(n):
if grid[i][j] > 0:
xy += 1
row_max[i] = max(row_max[i], grid[i][j])
col_max[j] = max(col_max[j], grid[i][j])
return xy + sum(row_max) + sum(col_max)
Complexity
- Time: O(n²)
- Space: O(n)
- Notes: Uses O(n) extra space for row and column maximum arrays, but only requires one pass through the grid.