{x}
blog image

Projection Area of 3D Shapes

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].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] <= 50

Solution Explanation for 883. Projection Area of 3D Shapes

This problem involves calculating the total projected area of a 3D shape formed by stacking cubes on a grid. The solution leverages a mathematical approach to efficiently compute the area of projections onto the xy, yz, and zx planes.

Approach

The core idea is to calculate the projection area for each plane independently and then sum them up.

  1. xy-plane projection: This projection represents the top view. The area is simply the number of cubes present in the grid (i.e., the count of cells with a value greater than 0).

  2. yz-plane projection: This projection is the front view. The area for each row is determined by the tallest stack of cubes in that row (the maximum value in the row). The total yz-plane area is the sum of the maximum values for each row.

  3. zx-plane projection: This projection is the side view. Similar to the yz-plane, the area for each column is determined by the tallest stack in that column (the maximum value in the column). The total zx-plane area is the sum of the maximum values for each column.

The total projected area is the sum of the areas calculated for each plane.

Time and Space Complexity

  • Time Complexity: O(n2). We iterate through the n x n grid once to calculate the xy-plane projection. We iterate through each row and column once to calculate yz and zx projections, respectively. Therefore, the overall time complexity is dominated by the iterations, resulting in O(n2).

  • Space Complexity: O(1). The solution uses a constant amount of extra space regardless of the input size. We store only a few variables to keep track of the area calculations for each plane.

Code Implementation (Python)

class Solution:
    def projectionArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        xy_area = 0
        yz_area = 0
        zx_area = 0
 
        # xy-plane projection
        for i in range(n):
            for j in range(n):
                if grid[i][j] > 0:
                    xy_area += 1
 
        # yz-plane projection
        for i in range(n):
            yz_area += max(grid[i])
 
        # zx-plane projection
        for j in range(n):
            col_max = 0
            for i in range(n):
                col_max = max(col_max, grid[i][j])
            zx_area += col_max
 
        return xy_area + yz_area + zx_area

This Python code clearly implements the steps described in the approach section. Other language implementations follow a similar structure, adapting the syntax and data structures accordingly. The key is the efficient calculation of the maximum values in rows and columns and the counting of non-zero elements.