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 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).
This C implementation uses nested loops to traverse the grid and calculate projection areas separately for each plane, accumulating the resulting areas for the total projection.
C++
Java
Python
C#
JavaScript
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.
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.
This C solution uses arrays to store the maximums of rows and columns, improving efficiency slightly from not recalculating these values repeatedly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) to fill the grid, row, and column arrays.
Space Complexity: O(n) to store column maximums.
| Approach | Complexity |
|---|---|
| Simulation of Projections | Time Complexity: O(n^2) since we traverse each grid element once. |
| Pre-compute Column and Row Maximums | Time Complexity: O(n^2) to fill the grid, row, and column arrays. |
How I Built a Leetcode Clone • NeetCode • 132,021 views views
Watch 9 more video solutions →Practice Projection Area of 3D Shapes with our built-in code editor and test cases.
Practice on FleetCode