# Projection Area of 3D Shapes
**Difficulty:** EASY
[External](https://leetcode.com/problems/projection-area-of-3d-shapes)
Canonical: https://scaleengineer.com/dsa/problems/projection-area-of-3d-shapes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/projection-area-of-3d-shapes/image0.png) 

**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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
The total projection area is the sum of three individual projection areas:
1.  **Top-down (xy-plane):** The area is the number of cells in the grid with a height greater than 0.
2.  **Side (zx-plane):** The area is the sum of the maximum heights in each row.
3.  **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.

```java
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;
    }
}
```
### Algorithm
1. Get the dimension `n` of the grid.
2. Initialize `xyArea = 0`.
3. Initialize two integer arrays, `rowMaxes` and `colMaxes`, of size `n` to all zeros.
4. 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])`.
5. Initialize `totalArea = xyArea`.
6. Iterate `k` from `0` to `n-1`:
    - Add `rowMaxes[k]` to `totalArea`.
    - Add `colMaxes[k]` to `totalArea`.
7. Return `totalArea`.

## Three Separate Passes
This approach calculates the total projection area by breaking the problem down into three distinct parts, one for each plane of projection. It iterates through the grid or its dimensions three times, once for each projection, and accumulates the area in a running total.
**Time:** O(n^2). Each of the three parts involves iterating through the `n x n` grid or its equivalent. The first part is O(n^2), the second is O(n^2), and the third is O(n^2). The total time complexity is O(n^2 + n^2 + n^2) = O(n^2). · **Space:** O(1). This approach only uses a few variables to store the running total and temporary maximums, not requiring any extra space that scales with the input size.
**Pros:** Very space-efficient, using only constant extra space.; The logic is clear and easy to follow as it handles each projection independently.
**Cons:** It iterates over the grid data multiple times, which can be less efficient in terms of cache performance and total operations compared to a single-pass solution.
### Explanation
The total area is the sum of the areas of the three projections. This method calculates each one sequentially.
1.  **Top-down (xy-plane) Projection:** Iterate through every cell `(i, j)` of the grid. If `grid[i][j] > 0`, it means there's a tower of cubes at this position, which casts a `1x1` shadow on the `xy` plane. Add 1 to the total area for each such cell.
2.  **Side (zx-plane) Projection:** For each row `i`, the area of the projection is determined by the tallest tower in that row. Iterate through each row, find the maximum value, and add it to the total area.
3.  **Front (yz-plane) Projection:** Similarly, for each column `j`, the area of the projection is the height of the tallest tower in that column. Iterate through each column, find the maximum value, and add it to the total area.

```java
class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int totalArea = 0;

        // 1. Top-down (xy-plane) projection area
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    totalArea++;
                }
            }
        }

        // 2. Side (zx-plane) projection area
        for (int i = 0; i < n; i++) {
            int rowMax = 0;
            for (int j = 0; j < n; j++) {
                rowMax = Math.max(rowMax, grid[i][j]);
            }
            totalArea += rowMax;
        }

        // 3. Front (yz-plane) projection area
        for (int j = 0; j < n; j++) {
            int colMax = 0;
            for (int i = 0; i < n; i++) {
                colMax = Math.max(colMax, grid[i][j]);
            }
            totalArea += colMax;
        }

        return totalArea;
    }
}
```
### Algorithm
1. Get the dimension `n` of the grid.
2. Initialize `totalArea = 0`.
3. **Calculate xy-plane area:**
   - Iterate `i` from `0` to `n-1`.
   - Iterate `j` from `0` to `n-1`.
   - If `grid[i][j] > 0`, increment `totalArea`.
4. **Calculate zx-plane area (row maxes):**
   - Iterate `i` from `0` to `n-1`.
   - Find the maximum value `rowMax` in `grid[i]`.
   - Add `rowMax` to `totalArea`.
5. **Calculate yz-plane area (column maxes):**
   - Iterate `j` from `0` to `n-1`.
   - Find the maximum value `colMax` in the `j`-th column.
   - Add `colMax` to `totalArea`.
6. Return `totalArea`.

## Optimized Single Pass with O(1) Space
This is the most efficient approach. It calculates the total area of all three projections in a single pass through the grid's dimensions. By cleverly structuring the loops, it computes the top-down area, the sum of row maximums, and the sum of column maximums simultaneously.
**Time:** O(n^2). We have a single nested loop structure that iterates through `n*n` elements. Accessing `grid[i][j]` and `grid[j][i]` are both O(1) operations. Thus, the total time complexity is dominated by the nested loops, resulting in O(n^2). · **Space:** O(1). We only use a few variables (`xyArea`, `yzArea`, `zxArea`, `rowMax`, `colMax`) to store intermediate results. The space required does not scale with the input size `n`.
**Pros:** Optimal time complexity, as we must look at every element at least once.; Optimal space complexity, using only a constant amount of extra memory.; High performance due to a single pass over the data, which leads to good cache locality.
**Cons:** The logic of calculating column maxes using `grid[j][i]` while iterating by rows might be slightly less intuitive at first glance compared to separate passes.
### Explanation
This approach is the most efficient, calculating the total projection area in a single, consolidated pass. It cleverly combines the calculation for all three projections (`xy`, `yz`, `zx`) into one nested loop structure.

The main idea is to iterate from `i = 0` to `n-1`. In each iteration `i`, we find the maximum of row `i` and the maximum of column `i`. The top-down projection area is calculated by iterating through all cells and counting the non-zero ones. All these calculations are performed within a single `O(n^2)` loop structure.

```java
class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int xyArea = 0; // Top-down projection
        int yzArea = 0; // Front projection
        int zxArea = 0; // Side projection

        for (int i = 0; i < n; i++) {
            int rowMax = 0; // Max height in current row i
            int colMax = 0; // Max height in current column i
            for (int j = 0; j < n; j++) {
                // Top-down projection: add 1 for any non-zero cube
                if (grid[i][j] > 0) {
                    xyArea++;
                }
                // Side projection: find max in row i
                rowMax = Math.max(rowMax, grid[i][j]);
                // Front projection: find max in column i
                // We use grid[j][i] to traverse column i while the outer loop is on row i
                colMax = Math.max(colMax, grid[j][i]);
            }
            zxArea += rowMax;
            yzArea += colMax;
        }

        return xyArea + yzArea + zxArea;
    }
}
```
### Algorithm
1. Get the dimension `n` of the grid.
2. Initialize `xyArea = 0`, `yzArea = 0`, `zxArea = 0`.
3. Iterate `i` from `0` to `n-1`:
    - Initialize `rowMax = 0` (for the max of row `i`).
    - Initialize `colMax = 0` (for the max of column `i`).
    - Iterate `j` from `0` to `n-1`:
        - If `grid[i][j] > 0`, increment `xyArea`.
        - Update `rowMax = max(rowMax, grid[i][j])`.
        - Update `colMax = max(colMax, grid[j][i])`.
    - Add `rowMax` to `zxArea`.
    - Add `colMax` to `yzArea`.
4. Return `xyArea + yzArea + zxArea`.

# Solutions
### Java

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

```

### CPP

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

### Python

```python
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

```