# LeetCode 807: Max Increase to Keep City Skyline

## Problem Restatement

We are given an `n x n` grid. Each value `grid[r][c]` is the height of a building at row `r` and column `c`.

We may increase the height of any number of buildings by any amount. We cannot decrease heights.

After increasing buildings, the skyline from all four directions must stay the same as the original grid. The task is to return the maximum total increase possible. A height of `0` is also treated as a building height.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` integer matrix `grid` |
| Output | Maximum total height increase |
| Row skyline | Maximum height in each row |
| Column skyline | Maximum height in each column |
| Constraint | No row maximum or column maximum may change |

## Examples

Example:

```python
grid = [
    [3, 0, 8, 4],
    [2, 4, 5, 7],
    [9, 2, 6, 3],
    [0, 3, 1, 0],
]
```

The row skyline is:

```python
[8, 7, 9, 3]
```

The column skyline is:

```python
[9, 4, 8, 7]
```

One maximum valid final grid is:

```python
[
    [8, 4, 8, 7],
    [7, 4, 7, 7],
    [9, 4, 8, 7],
    [3, 3, 3, 3],
]
```

The total increase is:

```python
35
```

So the answer is:

```python
35
```

## First Thought: Brute Force

A brute force idea would try different increased heights for every building, then check whether the row and column skylines stay unchanged.

This is unnecessary. Each building can be considered independently once we know the maximum height allowed by its row and column.

## Key Insight

For a cell `(r, c)`, its final height cannot be greater than the maximum height in row `r`. Otherwise, the skyline from the left or right would change.

It also cannot be greater than the maximum height in column `c`. Otherwise, the skyline from the top or bottom would change.

So the largest valid height for `grid[r][c]` is:

```python
min(row_max[r], col_max[c])
```

The increase at that cell is:

```python
min(row_max[r], col_max[c]) - grid[r][c]
```

Summing this value over all cells gives the maximum total increase.

## Algorithm

Compute the maximum value in every row:

```python
row_max = [max(row) for row in grid]
```

Compute the maximum value in every column:

```python
col_max = [max(grid[r][c] for r in range(n)) for c in range(n)]
```

Then scan every cell.

For each cell `(r, c)`:

1. Compute the highest allowed new height:

```python
allowed = min(row_max[r], col_max[c])
```

2. Add the possible increase:

```python
answer += allowed - grid[r][c]
```

Return `answer`.

## Correctness

The original row skyline is determined by the maximum value in each row. If any building in row `r` becomes greater than `row_max[r]`, then the skyline from the left or right changes. Therefore, every building in row `r` must have final height at most `row_max[r]`.

The original column skyline is determined by the maximum value in each column. If any building in column `c` becomes greater than `col_max[c]`, then the skyline from the top or bottom changes. Therefore, every building in column `c` must have final height at most `col_max[c]`.

So the final height of cell `(r, c)` can never exceed `min(row_max[r], col_max[c])`.

The algorithm increases each cell exactly to this largest allowed height. This cannot change any row skyline or column skyline because no cell exceeds its original row or column maximum. It is also optimal because no individual cell can be increased further without violating at least one skyline constraint.

Therefore, summing all such increases gives the maximum total possible increase.

## Complexity

Let `n` be the grid size.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan the matrix to compute maxima and again to compute increases |
| Space | `O(n)` | We store one row maximum and one column maximum per index |

## Implementation

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

        row_max = [max(row) for row in grid]
        col_max = [max(grid[r][c] for r in range(n)) for c in range(n)]

        answer = 0

        for r in range(n):
            for c in range(n):
                allowed = min(row_max[r], col_max[c])
                answer += allowed - grid[r][c]

        return answer
```

## Code Explanation

The row maxima preserve the skyline from the left and right:

```python
row_max = [max(row) for row in grid]
```

The column maxima preserve the skyline from the top and bottom:

```python
col_max = [max(grid[r][c] for r in range(n)) for c in range(n)]
```

For every cell, we compute the largest height that satisfies both skyline constraints:

```python
allowed = min(row_max[r], col_max[c])
```

Then we add the increase:

```python
answer += allowed - grid[r][c]
```

Since `allowed` is always at least the current height, this value is never negative.

## Testing

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

    assert s.maxIncreaseKeepingSkyline([
        [3, 0, 8, 4],
        [2, 4, 5, 7],
        [9, 2, 6, 3],
        [0, 3, 1, 0],
    ]) == 35

    assert s.maxIncreaseKeepingSkyline([
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]) == 0

    assert s.maxIncreaseKeepingSkyline([
        [1, 2],
        [3, 4],
    ]) == 1

    assert s.maxIncreaseKeepingSkyline([
        [5, 5],
        [5, 5],
    ]) == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `4 x 4` sample | Checks normal skyline constraints |
| All zeroes | No building can increase without changing skyline |
| Small `2 x 2` grid | Checks row and column limits |
| All same height | Already at every row and column maximum |