# LeetCode 883: Projection Area of 3D Shapes

## Problem Restatement

We are given an `n x n` grid.

Each cell:

```text
grid[r][c]
```

contains a vertical stack of cubes.

We want the total projection area of the 3D shape onto three planes:

| Projection | Meaning |
|---|---|
| Top view | Looking down from above |
| Front view | Looking from the front |
| Side view | Looking from the side |

Return the sum of these three projection areas. The official problem defines each cube as a `1 x 1 x 1` cube aligned to the axes. ([leetcode.com](https://leetcode.com/problems/projection-area-of-3d-shapes/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `grid`, an `n x n` matrix |
| Output | Total projection area |
| Cell value | Number of stacked cubes |
| Cube size | `1 x 1 x 1` |

Function shape:

```python
def projectionArea(self, grid: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```text
Input: grid = [[1,2],[3,4]]
Output: 17
```

Top projection:

```text
Every nonzero cell contributes 1.
```

There are 4 nonzero cells:

```text
top = 4
```

Front projection uses the largest value in each row:

| Row | Maximum |
|---|---:|
| `[1,2]` | 2 |
| `[3,4]` | 4 |

```text
front = 2 + 4 = 6
```

Side projection uses the largest value in each column:

| Column | Maximum |
|---|---:|
| `[1,3]` | 3 |
| `[2,4]` | 4 |

```text
side = 3 + 4 = 7
```

Total:

```text
4 + 6 + 7 = 17
```

Example 2:

```text
Input: grid = [[2]]
Output: 5
```

Top projection:

```text
1
```

Front projection:

```text
2
```

Side projection:

```text
2
```

Total:

```text
1 + 2 + 2 = 5
```

## First Thought: Simulate Every Cube

We could imagine building the entire 3D structure cube by cube.

Then for each viewing direction, determine which cubes are visible.

This works conceptually, but it is unnecessary.

The projections follow simple patterns that can be computed directly from the grid values.

## Key Insight

Each projection can be computed independently.

### Top Projection

Looking from above, a cell contributes area `1` if it contains at least one cube.

So the top projection equals:

```text
number of nonzero cells
```

### Front Projection

Looking from the front, each row contributes the height of its tallest stack.

So the front projection equals:

```text
sum of row maximums
```

### Side Projection

Looking from the side, each column contributes the height of its tallest stack.

So the side projection equals:

```text
sum of column maximums
```

The total answer is:

```text
top + front + side
```

## Algorithm

Initialize:

```python
answer = 0
```

For each row:

1. Count nonzero cells for the top projection.
2. Add the row maximum for the front projection.

For each column:

1. Add the column maximum for the side projection.

Return the total.

## Walkthrough

Use:

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

### Top Projection

Every nonzero cell contributes `1`.

| Cell | Contributes |
|---|---|
| `1` | Yes |
| `2` | Yes |
| `3` | Yes |
| `4` | Yes |

Total:

```text
4
```

### Front Projection

Take the maximum of each row:

| Row | Max |
|---|---:|
| `[1,2]` | 2 |
| `[3,4]` | 4 |

Total:

```text
6
```

### Side Projection

Take the maximum of each column:

| Column | Max |
|---|---:|
| `[1,3]` | 3 |
| `[2,4]` | 4 |

Total:

```text
7
```

Final answer:

```text
4 + 6 + 7 = 17
```

## Correctness

The top projection shows whether at least one cube exists in each grid position. A stack of height `1` and a stack of height `100` both cover exactly one square in the top view. Therefore, every nonzero cell contributes exactly `1` area to the top projection.

The front projection looks across each row. In a row, shorter stacks are hidden behind the tallest stack. Therefore, the visible height contributed by a row is exactly the maximum value in that row. Summing row maximums gives the full front projection area.

The side projection works similarly for columns. In each column, only the tallest stack determines the visible height from the side. Therefore, summing column maximums gives the side projection area.

The three projections are independent and non-overlapping measurements. Adding them together gives the total projection area required by the problem.

Thus, the algorithm computes the correct total projection area.

## Complexity

Let:

```text
n = len(grid)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan all cells |
| Space | `O(1)` | Only a few counters are used |

## Implementation

```python
class Solution:
    def projectionArea(self, grid: list[list[int]]) -> int:
        n = len(grid)

        top = 0
        front = 0
        side = 0

        for row in grid:
            front += max(row)

            for value in row:
                if value > 0:
                    top += 1

        for col in range(n):
            column_max = 0

            for row in range(n):
                column_max = max(column_max, grid[row][col])

            side += column_max

        return top + front + side
```

## Code Explanation

We track the three projection areas separately:

```python
top = 0
front = 0
side = 0
```

For each row:

```python
for row in grid:
```

the front projection gains the tallest stack:

```python
front += max(row)
```

Every nonzero cell contributes to the top projection:

```python
if value > 0:
    top += 1
```

Then we process columns:

```python
for col in range(n):
```

We find the tallest stack in each column:

```python
column_max = max(column_max, grid[row][col])
```

and add it to the side projection:

```python
side += column_max
```

Finally, return the sum of all three projections:

```python
return top + front + side
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.projectionArea([[1, 2], [3, 4]]) == 17
    assert s.projectionArea([[2]]) == 5
    assert s.projectionArea([[1, 0], [0, 2]]) == 8
    assert s.projectionArea([[0]]) == 0
    assert s.projectionArea([[1, 1, 1]]) == 5
    assert s.projectionArea([[1], [2], [3]]) == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[1,2],[3,4]]` | Standard example |
| `[[2]]` | Single stack |
| Sparse nonzero cells | Checks top projection logic |
| `[[0]]` | Empty shape |
| Single row | Front projection dominates |
| Single column | Side projection dominates |