Problem Description

You are given an n x n grid grid where grid[i][j] represents the height of a stack of cubes located at cell (i, j). Imagine placing stacks of cubes on a 2D grid, where each stack’s height is given by the value in the grid. Your task is to compute the total area of the projections of these cubes onto the three principal planes:

• Top view (xy-plane): The number of grid cells with a value greater than 0.
• Front view (yz-plane): For each row, the maximum value in that row (the tallest stack in that row).
• Side view (zx-plane): For each column, the maximum value in that column (the tallest stack in that column).

Return the sum of the areas of these three projections.

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] <= 50

Thought Process

The problem asks for the sum of three projection areas. Let's break down what each projection means:

• Top view: Every grid cell with at least one cube (i.e., grid[i][j] > 0) contributes 1 to the area.
• Front view: From the front, for each row, the tallest stack is visible. So for each row, we take the maximum value.
• Side view: From the side, for each column, the tallest stack is visible. So for each column, we take the maximum value.

A brute-force approach would be to scan the grid multiple times: once for the top view, once for each row (front), and once for each column (side). However, we can optimize by collecting all these values in a single pass through the grid.

The key insight is that we can compute all three projections efficiently by iterating through the grid once, keeping track of the required maxima for rows and columns as we go.

Solution Approach

Let's outline the steps to solve this problem efficiently:

1. Initialize three counters:
   • top for the top view area
   • front_max as a list to keep track of the maximum value in each row (front view)
   • side_max as a list to keep track of the maximum value in each column (side view)
2. Iterate through each cell grid[i][j]:
   • If grid[i][j] > 0, increment top
   • Update front_max[i] if grid[i][j] is greater than the current value
   • Update side_max[j] if grid[i][j] is greater than the current value
3. Sum up the projections:
   • The total area is top + sum(front_max) + sum(side_max)

This approach ensures we only traverse the grid once, collecting all necessary information efficiently.

Example Walkthrough

Let's use the following example input:

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

Step-by-step:

• Top view: All cells are > 0, so area = 4.
• Front view (row maxima):
  • Row 0: max(1, 2) = 2
  • Row 1: max(3, 4) = 4
  • Sum = 2 + 4 = 6
• Side view (column maxima):
  • Column 0: max(1, 3) = 3
  • Column 1: max(2, 4) = 4
  • Sum = 3 + 4 = 7
• Total area: 4 (top) + 6 (front) + 7 (side) = 17

At each iteration, we update the row and column maxima and count nonzero cells for the top view.

Code Implementation

class Solution:
    def projectionArea(self, grid):
        n = len(grid)
        top = 0
        front = 0
        side = 0
        
        for i in range(n):
            row_max = 0
            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
      

class Solution {
public:
    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 row_max = 0, col_max = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) top++;
                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;
    }
};
      

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

var projectionArea = function(grid) {
    let 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;
};
      

Time and Space Complexity

• Brute-force approach:
  • Three separate passes over the grid: O(n²) for each, total O(3n²) = O(n²).
  • Space: O(n) for storing row and column maxima.
• Optimized approach (as above):
  • Single pass, still O(n²), but more efficient in practice.
  • Space: O(1) extra (just a few variables), or O(n) if you keep arrays for row/col maxima separately.

Since n ≤ 50, this solution is efficient and well within constraints.

Summary

The Projection Area of 3D Shapes problem is elegantly solved by recognizing that each projection corresponds to simple properties of the grid: nonzero cells, row maxima, and column maxima. By iterating through the grid once and updating these values on the fly, we obtain an efficient and clear solution. The key insight is to treat each projection as a separate area calculation and combine them at the end.