Projection Area of 3D Shapes

easy matrix math geometry

Problem

You are given an n × n grid where grid[i][j] is the height of a tower of unit cubes placed on cell (i, j). We view the shape from the top, the front, and the side, projecting onto the xy, xz, and yz planes. Return the total area of all three projections. The top projection counts every cell whose height is greater than 0. The front projection sums the maximum of each row, and the side projection sums the maximum of each column.

Inputgrid = [[1, 2], [3, 4]]

Output17

Top = 4 non-zero cells. Front (row maxes) = 2 + 4 = 6. Side (column maxes) = 3 + 4 = 7. Total = 4 + 6 + 7 = 17.

grid (rows separated by ';', values by ',')

def projection_area(grid):
    n = len(grid)
    top = front = side = 0
    for i in range(n):
        row_max = col_max = 0
        for j in range(n):
            if grid[i][j] > 0:
                top += 1
            row_max = max(row_max, grid[i][j])
            col_max = max(col_max, grid[j][i])
        front += row_max
        side += col_max
    return top + front + side

function projectionArea(grid) {
  const n = grid.length;
  let top = 0, front = 0, side = 0;
  for (let i = 0; i < n; i++) {
    let rowMax = 0, colMax = 0;
    for (let j = 0; j < n; j++) {
      if (grid[i][j] > 0) top++;
      rowMax = Math.max(rowMax, grid[i][j]);
      colMax = Math.max(colMax, grid[j][i]);
    }
    front += rowMax;
    side += colMax;
  }
  return top + front + side;
}

class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int top = 0, front = 0, side = 0;
        for (int i = 0; i < n; i++) {
            int rowMax = 0, colMax = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) top++;
                rowMax = Math.max(rowMax, grid[i][j]);
                colMax = Math.max(colMax, grid[j][i]);
            }
            front += rowMax;
            side += colMax;
        }
        return top + front + side;
    }
}

int projectionArea(vector<vector<int>>& grid) {
    int n = grid.size();
    int top = 0, front = 0, side = 0;
    for (int i = 0; i < n; i++) {
        int rowMax = 0, colMax = 0;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) top++;
            rowMax = max(rowMax, grid[i][j]);
            colMax = max(colMax, grid[j][i]);
        }
        front += rowMax;
        side += colMax;
    }
    return top + front + side;
}

Explanation

You never actually have to build the 3D shape. Each of the three shadows it casts can be measured straight from the grid of heights with simple counting.

The top view is just how many cells have a tower at all, so we add 1 to top for every cell whose height is greater than 0. The front view is the sum of the tallest tower in each row (its silhouette), and the side view is the sum of the tallest tower in each column.

The clever bit is one double loop does all three. As we scan row i, grid[i][j] updates the row max, and grid[j][i] (the transposed cell) updates the column max at the same time. After each row we add its row max to front and its column max to side.

The answer is simply top + front + side.

Example: grid = [[1,2],[3,4]]. Top = 4 non-zero cells. Row maxes 2 + 4 = 6 for front. Column maxes 3 + 4 = 7 for side. Total = 4 + 6 + 7 = 17.

Time: O(n²) Space: O(1)