# LeetCode 892: Surface Area of 3D Shapes

## Problem Restatement

We are given an `n x n` grid.

Each value:

```text
grid[i][j]
```

represents a tower of `grid[i][j]` unit cubes placed on cell `(i, j)`.

After placing the cubes, directly adjacent cubes are glued together. We need to return the total exposed surface area of the resulting 3D shape.

The bottom face counts as part of the surface area. LeetCode defines each cube as `1 x 1 x 1`, and adjacent cubes share faces that are no longer exposed.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `grid`, an `n x n` matrix |
| Output | Total exposed surface area |
| Cell value | Height of the cube tower at that cell |
| Cube size | `1 x 1 x 1` |
| Bottom face | Counts toward surface area |

Function shape:

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

## Examples

Example 1:

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

A tower of height `2` has:

| Part | Area |
|---|---:|
| Top | 1 |
| Bottom | 1 |
| Four sides | `4 * 2 = 8` |

Total:

```text
1 + 1 + 8 = 10
```

Example 2:

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

First, compute each tower as if it stood alone:

| Height | Surface area alone |
|---:|---:|
| 1 | `4 * 1 + 2 = 6` |
| 2 | `4 * 2 + 2 = 10` |
| 3 | `4 * 3 + 2 = 14` |
| 4 | `4 * 4 + 2 = 18` |

Initial total:

```text
6 + 10 + 14 + 18 = 48
```

Now subtract shared faces between adjacent towers.

Adjacent pairs:

| Pair | Shared height | Subtract |
|---|---:|---:|
| `1` and `2` | 1 | 2 |
| `1` and `3` | 1 | 2 |
| `2` and `4` | 2 | 4 |
| `3` and `4` | 3 | 6 |

Total subtraction:

```text
2 + 2 + 4 + 6 = 14
```

Final answer:

```text
48 - 14 = 34
```

## First Thought: Count Every Cube Face

A direct approach is to inspect every cube one by one.

Each cube starts with `6` faces. For each neighboring cube that touches it, one face becomes hidden.

This works, but it is more detailed than needed.

A tower of cubes has a simple formula, and neighboring towers have a simple overlap rule.

## Key Insight

A non-empty tower of height `h` contributes:

```text
4 * h + 2
```

Why?

| Face group | Area |
|---|---:|
| Top | 1 |
| Bottom | 1 |
| Four vertical sides | `4 * h` |

So an isolated tower contributes:

```text
4 * h + 2
```

When two adjacent towers have heights `a` and `b`, they touch along:

```text
min(a, b)
```

unit squares.

Each shared square hides one face from each tower, so we subtract:

```text
2 * min(a, b)
```

We only need to check each adjacent pair once. A convenient way is to check the top neighbor and the left neighbor for each cell.

## Algorithm

Initialize:

```python
answer = 0
```

For every cell `(i, j)`:

1. Let `height = grid[i][j]`.
2. If `height > 0`, add:

```python
4 * height + 2
```

3. If there is a tower above, subtract:

```python
2 * min(height, grid[i - 1][j])
```

4. If there is a tower to the left, subtract:

```python
2 * min(height, grid[i][j - 1])
```

Return `answer`.

## Walkthrough

Use:

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

Process each tower:

| Cell | Height | Add |
|---|---:|---:|
| `(0,0)` | 1 | 6 |
| `(0,1)` | 2 | 10 |
| `(1,0)` | 3 | 14 |
| `(1,1)` | 4 | 18 |

Total before shared faces:

```text
48
```

Subtract shared faces:

| Current cell | Neighbor | Shared height | Subtract |
|---|---|---:|---:|
| `(0,1)` | left `(0,0)` | 1 | 2 |
| `(1,0)` | above `(0,0)` | 1 | 2 |
| `(1,1)` | above `(0,1)` | 2 | 4 |
| `(1,1)` | left `(1,0)` | 3 | 6 |

Final:

```text
48 - 14 = 34
```

## Correctness

For every non-empty cell, the algorithm first adds the surface area of that tower as if it were isolated. A tower of height `h` has one top face, one bottom face, and four vertical sides of height `h`, so its isolated surface area is `4 * h + 2`.

This counts all exposed faces, but it also counts faces that are hidden because two neighboring towers touch.

For any two adjacent towers with heights `a` and `b`, exactly `min(a, b)` cube faces touch on one side. Since each contact hides one face from each tower, the isolated sum overcounts by `2 * min(a, b)`.

The algorithm subtracts this amount once for every adjacent pair by checking only the above and left neighbors. Therefore, every hidden shared face is removed exactly once, and no shared face is subtracted twice.

After all cells are processed, the remaining count is exactly the exposed surface area of the glued shape.

## Complexity

Let:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan every cell once |
| Space | `O(1)` | Only counters are used |

## Implementation

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

        for i in range(n):
            for j in range(n):
                height = grid[i][j]

                if height > 0:
                    answer += 4 * height + 2

                if i > 0:
                    answer -= 2 * min(height, grid[i - 1][j])

                if j > 0:
                    answer -= 2 * min(height, grid[i][j - 1])

        return answer
```

## Code Explanation

We scan every cell:

```python
for i in range(n):
    for j in range(n):
```

For each cell, `height` is the tower height:

```python
height = grid[i][j]
```

If the tower exists, we add its isolated surface area:

```python
if height > 0:
    answer += 4 * height + 2
```

Then we subtract shared area with the tower above:

```python
if i > 0:
    answer -= 2 * min(height, grid[i - 1][j])
```

and shared area with the tower to the left:

```python
if j > 0:
    answer -= 2 * min(height, grid[i][j - 1])
```

Checking only above and left counts each adjacent pair once.

## Testing

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

    assert s.surfaceArea([[2]]) == 10
    assert s.surfaceArea([[1, 2], [3, 4]]) == 34
    assert s.surfaceArea([[1, 0], [0, 2]]) == 16
    assert s.surfaceArea([[0]]) == 0
    assert s.surfaceArea([[1, 1], [1, 1]]) == 16
    assert s.surfaceArea([[3, 3, 3]]) == 26

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[2]]` | Single tower |
| `[[1,2],[3,4]]` | Multiple shared faces |
| `[[1,0],[0,2]]` | Separated towers |
| `[[0]]` | Empty grid |
| Uniform `2 x 2` height `1` | Flat square of cubes |
| Single row | Only horizontal sharing |