LeetCode 807 - Max Increase to Keep City Skyline

This problem gives us an n x n grid where each cell represents the height of a building in a city. The city can be viewed from four directions: north, south, east, and west. From these viewpoints, the skyline is determined by the tallest building visible in each row or column.

leetcodemediumarraygreedymatrix

LeetCode Problem 807

Difficulty: 🟡 Medium
Topics: Array, Greedy, Matrix

Solution

Problem Understanding

This problem gives us an n x n grid where each cell represents the height of a building in a city. The city can be viewed from four directions: north, south, east, and west. From these viewpoints, the skyline is determined by the tallest building visible in each row or column.

When viewing the city from the west or east, the skyline for a row is simply the maximum value in that row. Similarly, when viewing from the north or south, the skyline for a column is the maximum value in that column.

We are allowed to increase building heights, but we are not allowed to change any skyline. This means:

  • The maximum value in every row must remain unchanged.
  • The maximum value in every column must remain unchanged.

Our goal is to maximize the total amount by which building heights increase while preserving all row and column maximums.

The input consists of:

  • A square matrix grid
  • grid[r][c] represents the height of the building at row r and column c

The output is:

  • A single integer representing the maximum total increase across all buildings

The constraints are relatively small:

  • 2 <= n <= 50
  • 0 <= grid[r][c] <= 100

Since the grid is at most 50 x 50, even an O(n^3) solution would be acceptable. This tells us we do not need advanced optimization techniques, but we should still aim for a clean and efficient solution.

Several edge cases are important:

  • A grid filled with zeros. No increases are possible because any increase would change the skyline.
  • Rows or columns where multiple cells already share the maximum height.
  • Very small grids such as 2 x 2.
  • Buildings that are already at their maximum allowed height.

The problem guarantees the grid is square and non-empty, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A brute-force solution would examine each building independently and try increasing its height one unit at a time until the skyline changes.

For every cell:

  1. Temporarily increase the height.
  2. Recompute all row and column skylines.
  3. Check whether any skyline changed.
  4. Continue increasing until the increase becomes invalid.

This approach is correct because it explicitly verifies every possible increase while preserving the skyline constraints. However, it is inefficient because every attempted increase requires recomputing row and column maximums repeatedly.

If building heights can grow up to around 100 and we recompute skylines each time, the runtime becomes unnecessarily large.

Key Insight

The skyline constraints immediately tell us the maximum allowed height for each building.

For a building at position (r, c):

  • The row skyline is the maximum value in row r
  • The column skyline is the maximum value in column c

To preserve both skylines, the building cannot exceed either limit.

Therefore, the maximum valid height is:

min(rowMax[r], colMax[c])

The increase for a building becomes:

min(rowMax[r], colMax[c]) - grid[r][c]

We simply compute this value for every cell and sum the increases.

This observation transforms the problem into a straightforward matrix traversal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) or worse O(1) Repeatedly increases cells and recomputes skylines
Optimal O(n^2) O(n) Precompute row and column maximums

Algorithm Walkthrough

  1. Compute the maximum value for every row.

We create an array row_max where row_max[r] stores the tallest building in row r. These values define the skyline when viewing from east or west. 2. Compute the maximum value for every column.

We create another array col_max where col_max[c] stores the tallest building in column c. These values define the skyline when viewing from north or south. 3. Traverse every cell in the grid.

For each building at (r, c), determine the tallest height it can safely become without changing any skyline. 4. Compute the allowed maximum height.

The building cannot exceed either the row maximum or the column maximum, so its limit is:

min(row_max[r], col_max[c])
  1. Compute the increase for the current building.

The increase is:

allowed_height - current_height

Since the allowed height is always at least the current height, this value is never negative. 6. Add the increase to the total answer.

Repeat for all cells. 7. Return the total increase.

Why it works

The skyline for a row depends only on the row maximum, and the skyline for a column depends only on the column maximum. By restricting every building to at most min(rowMax[r], colMax[c]), we guarantee that no row or column maximum increases. At the same time, choosing this maximum possible value for every building ensures the total increase is as large as possible.

Python Solution

from typing import List

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

        total_increase = 0

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

        return total_increase

The implementation starts by computing the maximum building height for each row using a list comprehension. These values represent the row skylines.

Next, it computes the maximum height for each column. Since Python stores the grid row-wise, we iterate through all rows for every column index.

After preprocessing the skyline limits, we traverse the grid again. For every building, we calculate the maximum safe height using the minimum of the row and column limits.

The difference between this allowed height and the current height is the amount by which the building can grow. We accumulate these increases into total_increase.

Finally, we return the total.

Go Solution

func maxIncreaseKeepingSkyline(grid [][]int) int {
	n := len(grid)

	rowMax := make([]int, n)
	colMax := make([]int, n)

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] > rowMax[r] {
				rowMax[r] = grid[r][c]
			}

			if grid[r][c] > colMax[c] {
				colMax[c] = grid[r][c]
			}
		}
	}

	totalIncrease := 0

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			allowedHeight := rowMax[r]
			if colMax[c] < allowedHeight {
				allowedHeight = colMax[c]
			}

			totalIncrease += allowedHeight - grid[r][c]
		}
	}

	return totalIncrease
}

The Go implementation follows the same logic as the Python version. Instead of using built-in functions like max() and min(), we manually compare integers.

Go slices are initialized with zero values automatically, which works correctly because building heights are non-negative.

Integer overflow is not a concern because the maximum total increase is small:

  • Maximum increase per cell is at most 100
  • Maximum number of cells is 50 * 50 = 2500
  • Maximum total is around 250000

This easily fits within Go's int type.

Worked Examples

Example 1

Input:

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

Step 1: Compute Row Maximums

Row Maximum
[3,0,8,4] 8
[2,4,5,7] 7
[9,2,6,3] 9
[0,3,1,0] 3

So:

row_max = [8, 7, 9, 3]

Step 2: Compute Column Maximums

Column Values Maximum
0 3,2,9,0 9
1 0,4,2,3 4
2 8,5,6,1 8
3 4,7,3,0 7

So:

col_max = [9, 4, 8, 7]

Step 3: Compute Allowed Heights

Cell Current Allowed Increase
(0,0) 3 min(8,9)=8 5
(0,1) 0 min(8,4)=4 4
(0,2) 8 min(8,8)=8 0
(0,3) 4 min(8,7)=7 3
(1,0) 2 min(7,9)=7 5
(1,1) 4 min(7,4)=4 0
(1,2) 5 min(7,8)=7 2
(1,3) 7 min(7,7)=7 0
(2,0) 9 min(9,9)=9 0
(2,1) 2 min(9,4)=4 2
(2,2) 6 min(9,8)=8 2
(2,3) 3 min(9,7)=7 4
(3,0) 0 min(3,9)=3 3
(3,1) 3 min(3,4)=3 0
(3,2) 1 min(3,8)=3 2
(3,3) 0 min(3,7)=3 3

Total:

5+4+0+3+5+0+2+0+0+2+2+4+3+0+2+3 = 35

Answer:

35

Example 2

Input:

grid =
[
    [0,0,0],
    [0,0,0],
    [0,0,0]
]

Step 1: Row Maximums

row_max = [0,0,0]

Step 2: Column Maximums

col_max = [0,0,0]

Step 3: Allowed Heights

Every cell has:

min(0,0) = 0

No building can increase.

Total increase:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We traverse the grid a constant number of times
Space O(n) We store row and column maximum arrays

The algorithm performs three major passes over the grid:

  1. Compute row maximums
  2. Compute column maximums
  3. Compute total increases

Each pass touches every cell once, resulting in O(n^2) time complexity.

The only extra memory used is two arrays of size n, giving O(n) auxiliary space complexity.

Test Cases

from typing import List

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

        total_increase = 0

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

        return total_increase

sol = Solution()

# Example 1 from problem statement
assert sol.maxIncreaseKeepingSkyline([
    [3,0,8,4],
    [2,4,5,7],
    [9,2,6,3],
    [0,3,1,0]
]) == 35

# Example 2, all zeros
assert sol.maxIncreaseKeepingSkyline([
    [0,0,0],
    [0,0,0],
    [0,0,0]
]) == 0

# Already at maximum everywhere
assert sol.maxIncreaseKeepingSkyline([
    [5,5],
    [5,5]
]) == 0

# Single cell increases possible in some positions
assert sol.maxIncreaseKeepingSkyline([
    [1,2],
    [3,4]
]) == 1

# Multiple equal row and column maximums
assert sol.maxIncreaseKeepingSkyline([
    [1,1,1],
    [1,5,1],
    [1,1,1]
]) == 8

# Smallest valid grid size
assert sol.maxIncreaseKeepingSkyline([
    [0,1],
    [1,0]
]) == 1

# Mixed values with no possible increase in some rows
assert sol.maxIncreaseKeepingSkyline([
    [8,4],
    [2,8]
]) == 4

# Large values near constraint limit
assert sol.maxIncreaseKeepingSkyline([
    [100,0],
    [0,100]
]) == 200

Test Case Summary

Test Why
Problem example 1 Validates the standard scenario
All zeros Ensures skyline restrictions prevent increases
Uniform grid Tests case where no increases are possible
Small 2x2 grid Verifies correctness on minimal dimensions
Central peak grid Tests multiple increases around one maximum
Mixed diagonal maximums Ensures row/column constraints interact correctly
Large values Confirms handling near maximum constraints

Edge Cases

One important edge case is a grid filled entirely with zeros. In this scenario, every row skyline and column skyline is zero. Increasing any building would immediately change a skyline, so the correct answer is zero. A buggy implementation might incorrectly assume zero-height buildings can always increase.

Another important case is when every building in a row or column already equals the skyline maximum. In these situations, no increase is allowed for those buildings. The implementation handles this naturally because:

allowed_height - current_height = 0

A third important edge case occurs when a building is limited more by its column skyline than its row skyline, or vice versa. For example:

[
    [1,10],
    [5,2]
]

The building at (1,1) cannot grow to 10 because the column maximum is only 10 while the row maximum is 5. Using the minimum of the two limits ensures both skylines remain unchanged.

Finally, very small grids such as 2 x 2 can expose indexing mistakes or incorrect assumptions about dimensions. Since the implementation consistently uses n = len(grid) and iterates carefully over rows and columns, these cases are handled correctly.