883. Projection Area of 3D Shapes
Problem Description
In this problem, we are given an n x n
grid where each cell in the grid contains a non-negative integer value representing the height of a tower of cubes placed in that cell. The task is to calculate the total surface area of all three orthogonal projections (top-down, front, and side) of the arrangement of the cubes.
To understand this better, imagine looking at the cubes from three different viewpoints: from directly above (the xy-plane), from the front (the yz-plane), and from the side (the zx-plane). The area of the projection is simply the shadow of these cubes on the respective planes. The top-down view counts all the cubes that are visible from above, the front view counts the tallest tower in each row, and the side view counts the tallest tower in each column.
Intuition
For the solution, we can tackle each projection separately and sum up their areas:
-
xy-plane (Top-Down View): To compute the area of the projection on the xy-plane, we count the number of cubes that are visible from the top. Each cube contributes to the area if its height is greater than zero. We simply iterate over the grid and count the number of cells with a value greater than zero.
-
yz-plane (Front View): For the yz-plane, we are looking at the grid from the front, so we need to consider the tallest tower in each row since only the tallest tower is visible from this viewpoint. We iterate through each row and take the maximum value of the row, representing the height of the tallest tower.
-
zx-plane (Side View): Similarly, for the zx-plane projection, which represents the view from the side, we need to find the tallest tower in each column. We can achieve this by zipping the columns together and finding the maximum height of each column.
The final area of all projections is the sum of the three calculated areas: the top-down, the front, and the side projection areas.
Learn more about Math patterns.
Solution Approach
The implementation of the solution uses simple yet effective techniques to calculate the projection areas on all three planes. The choice of data structures is straightforward - since the input is a grid (a list of lists in Python), we use this same structure to operate on the data. Here's how the solution is structured:
-
xy-plane (Top-Down View): The
xy
variable is calculated by using a nested list comprehension. The outer loop iterates over each row, and the inner loop iterates over each value in the row, checking ifv > 0
. This check effectively counts the number of cells with cubes visible from the top view, contributing to thexy
area. The use of list comprehension makes this part compact and efficient.xy = sum(v > 0 for row in grid for v in row)
-
yz-plane (Front View): The
yz
projection is calculated by iterating over each row in the grid and selecting the maximum value found in that row using themax
function. This represents the highest tower when looking from the front, and the sum of these maximum values across all rows gives theyz
area.yz = sum(max(row) for row in grid)
-
zx-plane (Side View): To find the
zx
projection, we need the tallest tower in each column. Python'szip
function is used here, which effectively transposes the grid, grouping all elements at similar column indices together. By iterating over these transposed columns and selecting the maximum value found in each, we compute thezx
area.zx = sum(max(col) for col in zip(*grid))
After computing the areas individually, we sum them to get the total area of all three projections, which is returned as the final result. The algorithm's complexity is linear in the number of cells in the grid, making it O(n^2), where n
is the dimension of the grid. The solution is not only intuitive but also showcases the power and readability of Python's list comprehensions and built-in functions.
No complex patterns or algorithms are necessary for this problem, as it's more about understanding what each projection looks like and selecting the appropriate elements from the grid to count. The solution, therefore, combines basic iteration and aggregation methods to achieve an efficient and understandable result.
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 + zx
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach using a 3 x 3
grid as an example:
Suppose we have the following grid representing the heights of the towers of cubes:
grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
We will walk through the solution by calculating the area of each orthogonal projection.
Top-Down View (xy-plane):
First, we look at how many cubes contribute to the top view. Since all cubes are visible from the top, we count all cells with a height greater than zero.
1 2 3 4 5 6 7 8 9
From this, we can see that all 9 cells contribute to the top view (as all heights are non-zero). Thus, the xy
area is 9
.
Front View (yz-plane):
Now, we look at each row to find the tallest tower, as this would be visible from the front.
1 2 3 <- Tallest in 1st row is 3 4 5 6 <- Tallest in 2nd row is 6 7 8 9 <- Tallest in 3rd row is 9
The heights of the tallest towers are 3
, 6
, and 9
, and the yz
area is the sum of these which is 3 + 6 + 9 = 18
.
Side View (zx-plane):
For the side view, we need the tallest tower in each column. By looking at each column:
1 4 7 <- Tallest in 1st column is 7 2 5 8 <- Tallest in 2nd column is 8 3 6 9 <- Tallest in 3rd column is 9
The tallest towers from each column have heights 7
, 8
, and 9
. Thus, the zx
area is the sum of these which is 7 + 8 + 9 = 24
.
Finally, add up all the areas to get the total surface area of all projections:
xy + yz + zx = 9 + 18 + 24 = 51
So according to our solution, the final result for the given 3 x 3
grid is 51
.
Solution Implementation
1class Solution:
2 def projectionArea(self, grid: List[List[int]]) -> int:
3 # Calculate the XY projection area by counting all non-zero values in the grid
4 xy_projection = sum(value > 0 for row in grid for value in row)
5
6 # Calculate the YZ projection area by summing up the tallest building in each row
7 yz_projection = sum(max(row) for row in grid)
8
9 # Calculate the ZX projection area by summing up the tallest building in each column.
10 # zip(*grid) creates an iterator that aggregates elements from each row into columns.
11 zx_projection = sum(max(column) for column in zip(*grid))
12
13 # Return the sum of the three projection areas.
14 return xy_projection + yz_projection + zx_projection
15
1class Solution {
2
3 // Method to calculate projection area of a 3D shape
4 // represented by a grid onto the xy, yz, and zx planes.
5 public int projectionArea(int[][] grid) {
6 int areaXY = 0; // Area projection onto the XY plane
7 int areaYZ = 0; // Area projection onto the YZ plane
8 int areaZX = 0; // Area projection onto the ZX plane
9
10 // We assume grid is a square (n x n matrix), so we use grid.length to get 'n'.
11 for (int i = 0, n = grid.length; i < n; ++i) {
12 int maxYForYZ = 0; // Max height in y-direction for YZ projection
13 int maxXForZX = 0; // Max height in x-direction for ZX projection
14
15 // Iterate over each row and column to calculate heights
16 for (int j = 0; j < n; ++j) {
17
18 // Increment area counter for XY plane if height > 0
19 if (grid[i][j] > 0) {
20 areaXY++;
21 }
22
23 // Determine the tallest point in the current row for YZ projection
24 maxYForYZ = Math.max(maxYForYZ, grid[i][j]);
25
26 // Determine the tallest point in the current column for ZX projection
27 maxXForZX = Math.max(maxXForZX, grid[j][i]);
28 }
29
30 // Accumulate the maximum height of the grid for YZ and ZX projections
31 areaYZ += maxYForYZ;
32 areaZX += maxXForZX;
33 }
34
35 // The total projection area is the sum of all three individual areas
36 return areaXY + areaYZ + areaZX;
37 }
38}
39
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int projectionArea(vector<vector<int>>& grid) {
8 int areaXY = 0; // Initialize the area of the projection onto the XY plane
9 int areaYZ = 0; // Initialize the area of the projection onto the YZ plane
10 int areaZX = 0; // Initialize the area of the projection onto the ZX plane
11
12 // Iterate over the grid to calculate the areas of the projections
13 for (int i = 0, n = grid.size(); i < n; ++i) {
14 int maxRowValue = 0; // The maximum value in the current row for YZ projection
15 int maxColValue = 0; // The maximum value in the current column for ZX projection
16
17 for (int j = 0; j < n; ++j) {
18 // Count the number of cells with a value greater than 0 for the XY projection
19 areaXY += grid[i][j] > 0 ? 1 : 0;
20
21 // Find the maximum value in the i-th row for YZ projection
22 maxRowValue = max(maxRowValue, grid[i][j]);
23
24 // Find the maximum value in the j-th column for ZX projection
25 maxColValue = max(maxColValue, grid[j][i]);
26 }
27
28 // Add the maximum row value to the YZ projection's area
29 areaYZ += maxRowValue;
30
31 // Add the maximum column value to the ZX projection's area
32 areaZX += maxColValue;
33 }
34
35 // Return the total projection area by summing up the individual projections
36 return areaXY + areaYZ + areaZX;
37 }
38};
39
1function projectionArea(grid: number[][]): number {
2 // Get the size of the grid.
3 const size = grid.length;
4 // Calculate the top-view projection area, counting the cells that are non-zero.
5 let totalArea = grid.reduce((total, row) => total + row.reduce((count, cell) => count + (cell > 0 ? 1 : 0), 0), 0);
6
7 // Iterate over each row and each column to find the maximum heights
8 // and calculate the side-view projection areas.
9 for (let i = 0; i < size; i++) {
10 let maxRowHeight = 0; // Max height in the current row.
11 let maxColHeight = 0; // Max height in the current column.
12 for (let j = 0; j < size; j++) {
13 // Find the maximum height of the current row by comparing heights of the cells.
14 maxRowHeight = Math.max(maxRowHeight, grid[i][j]);
15 // Find the maximum height of the current column by comparing heights of the cells.
16 maxColHeight = Math.max(maxColHeight, grid[j][i]);
17 }
18 // Add the maximum heights to the total projection area.
19 totalArea += maxRowHeight + maxColHeight;
20 }
21
22 // Return the total projection area.
23 return totalArea;
24}
25
Time and Space Complexity
The time complexity of the given code is O(N^2)
where N
is the number of rows (or columns, assuming the grid is square). This is due to the three separate loops that iterate over all N*N elements of the grid or its transposition. The first loop iterates over all elements for the xy
shadow, the second loop iterates over each row to find the maximum for yz
shadow, and the third loop iterates over each transposed column to find the maximum for the zx
shadow.
The space complexity of the code is O(N)
because of the space required for the transposition of the grid (zip(*grid)
). This creates a list of tuples where each tuple is a column from the original grid. The space is linear with the number of columns N.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!