Skip to content

883. Projection Area of 3D Shapes

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

Solutions

Solution 1: Mathematics

Thinking

The three projections are the number of nonzero cells, the sum of row maxima, and the sum of column maxima. \(n\le 50\), so one pass computes all three.

Count \(v>0\) for the top view, take \(\max\) per row and per column for the other two views, and add them.

We can calculate the area of the three projections separately.

  • Projection area on the xy plane: Each non-zero value will be projected onto the xy plane, so the projection area on the xy plane is the count of non-zero values.
  • Projection area on the yz plane: The maximum value in each row.
  • Projection area on the zx plane: The maximum value in each column.

Finally, add up the three areas.

The time complexity is \(O(n^2)\), where \(n\) is the side length of the grid grid. The space complexity is \(O(1)\).

1
2
3
4
5
6
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int xy = 0, yz = 0, zx = 0;
        for (int i = 0, n = grid.size(); i < n; ++i) {
            int maxYz = 0, maxZx = 0;
            for (int j = 0; j < n; ++j) {
                xy += grid[i][j] > 0;
                maxYz = max(maxYz, grid[i][j]);
                maxZx = max(maxZx, grid[j][i]);
            }
            yz += maxYz;
            zx += maxZx;
        }
        return xy + yz + zx;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func projectionArea(grid [][]int) int {
    xy, yz, zx := 0, 0, 0
    for i, row := range grid {
        maxYz, maxZx := 0, 0
        for j, v := range row {
            if v > 0 {
                xy++
            }
            maxYz = max(maxYz, v)
            maxZx = max(maxZx, grid[j][i])
        }
        yz += maxYz
        zx += maxZx
    }
    return xy + yz + zx
}

1
2
3
4
5
6
7
8
function projectionArea(grid: number[][]): number {
    const xy: number = grid.flat().filter(v => v > 0).length;
    const yz: number = grid.reduce((acc, row) => acc + Math.max(...row), 0);
    const zx: number = grid[0]
        .map((_, i) => Math.max(...grid.map(row => row[i])))
        .reduce((acc, val) => acc + val, 0);
    return xy + yz + zx;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn projection_area(grid: Vec<Vec<i32>>) -> i32 {
        let xy: i32 = grid
            .iter()
            .map(|row| row.iter().filter(|&&v| v > 0).count() as i32)
            .sum();
        let yz: i32 = grid.iter().map(|row| *row.iter().max().unwrap_or(&0)).sum();
        let zx: i32 = (0..grid[0].len())
            .map(|i| grid.iter().map(|row| row[i]).max().unwrap_or(0))
            .sum();
        xy + yz + zx
    }
}

Comments