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

Examples

Example:

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

The row skyline is:

[8, 7, 9, 3]

The column skyline is:

[9, 4, 8, 7]

One maximum valid final grid is:

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

The total increase is:

35

So the answer is:

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:

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

The increase at that cell is:

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:

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

Compute the maximum value in every column:

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:

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

2. Add the possible increase:

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.

Implementation

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:

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

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

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:

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

Then we add the increase:

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

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

Testing

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()