Projection Area of 3D Shapes

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Projection Area of 3D Shapes. Click on different approaches to view the approach and algorithm in detail.

Single Pass with Auxiliary Arrays

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 n of the grid.
Initialize xyArea = 0.
Initialize two integer arrays, rowMaxes and colMaxes, of size n to all zeros.
Iterate i from 0 to n-1:
- Iterate j from 0 to n-1:
  - If grid[i][j] > 0, increment xyArea.
  - Update rowMaxes[i] = max(rowMaxes[i], grid[i][j]).
  - Update colMaxes[j] = max(colMaxes[j], grid[i][j]).
Initialize totalArea = xyArea.
Iterate k from 0 to n-1:
- Add rowMaxes[k] to totalArea.
- Add colMaxes[k] to totalArea.
Return totalArea.

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 Analysis

Time Complexity: 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 Complexity: O(n). We use two arrays, `rowMaxes` and `colMaxes`, each of size `n`, to store the maximums. This results in O(n) auxiliary space.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Projection Area of 3D Shapes. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Projection Area of 3D Shapes

Patterns:

MathGeometry

Data Structures:

ArrayMatrix