Max Increase to Keep City Skyline: Row and Column Constraints

May 23, 20265 min read

leetcodeproblemmediumarraysmatrixgreedy

You are given a grid of building heights in a city. Each cell represents one building, and its value is the height. The skyline is what you see when you look at the buildings from the side or from the front: a silhouette formed by the tallest building in each row or column. Your goal is to find the maximum total increase in building heights such that the skyline viewed from any cardinal direction does not change.

This is LeetCode 807: Max Increase to Keep City Skyline. It is a clean greedy problem where the constraint on each cell comes from two projections: the row maximum and the column maximum.

The problem

Given an n x n grid of building heights, you can increase any building's height. The skyline from the top or bottom is determined by the maximum height in each column. The skyline from the left or right is determined by the maximum height in each row. You need to find the maximum total increase across all buildings such that neither skyline changes.

The key constraint: for a building at position (r, c), its new height cannot exceed min(rowMax[r], colMax[c]). If it went higher than rowMax[r], the skyline from the side would change. If it went higher than colMax[c], the skyline from the front would change. So the tightest constraint wins.

The original 4x4 grid of building heights. Blue dashed cells show row maximums (the skyline viewed from the right). Green dashed cells show column maximums (the skyline viewed from the bottom).

The approach

The algorithm has three parts:

Compute rowMax[r] for every row: the maximum value in that row.
Compute colMax[c] for every column: the maximum value in that column.
For each cell (r, c), the new height is min(rowMax[r], colMax[c]). Add newHeight - grid[r][c] to the total increase.

def max_increase_keeping_skyline(grid):
    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 = 0
    for r in range(n):
        for c in range(n):
            total += min(row_max[r], col_max[c]) - grid[r][c]

    return total

The solution is direct. You compute the two projection arrays, then sweep through every cell and accumulate the difference between the allowed maximum and the current height. There is no need for sorting, priority queues, or any fancy data structure.

Practice matrix problems

Step-by-step walkthrough

Let's trace through the example grid [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] to see how each cell's new height is determined.

Step 1: Compute row maximums and column maximums.

Row maximums: [8, 7, 9, 3]. Column maximums: [9, 4, 8, 7]. These define the skyline from each direction.

Step 2: For each cell, the limit is min(rowMax, colMax).

Take cell (0,0) with height 3. rowMax[0] = 8 (blue), colMax[0] = 9 (green). The limit is min(8, 9) = 8. So cell (0,0) can increase from 3 to 8, a gain of 5.

Step 3: New grid after maximizing each cell.

Green cells increased. Default cells stayed the same (they were already at or above the min constraint).

Step 4: Compute the total increase.

Original: 3 0 8 4 | 2 4 5 7 | 9 2 6 3 | 0 3 1 0 New: 8 4 8 4 | 7 4 7 7 | 9 4 8 7 | 3 3 3 3 Diff: 5 4 0 0 | 5 0 2 0 | 0 2 2 4 | 3 0 2 3 Total increase = 5+4+0+0 + 5+0+2+0 + 0+2+2+4 + 3+0+2+3 = 32

Sum of (newGrid[r][c] - grid[r][c]) for all cells = (5+4+0+0) + (5+0+2+0) + (0+2+2+4) + (3+0+2+3) = 32.

Every cell reaches its maximum allowed height without violating either skyline. The total increase is 32.

Complexity analysis

Metric	Value
Time	O(n^2)
Space	O(n)

Time: You traverse the grid once to compute row maximums (O(n^2) total across all rows), once to compute column maximums (O(n^2)), and once more to compute the total increase (O(n^2)). All three passes are O(n^2).

Space: The row_max and col_max arrays each have n entries. That is O(n) extra space. The grid itself is not modified.

Drill greedy matrix problems

The building blocks

Row and column projections

The skyline from the left or right is just the maximum of each row. The skyline from the top or bottom is just the maximum of each column. These are called projections: you collapse a 2D grid down to a 1D array by taking the max along one axis.

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

This same idea of projecting rows and columns into 1D summaries appears across many matrix problems. In Set Matrix Zeroes, you track which rows and columns contain a zero. In matrix search problems, you use row/column properties to eliminate candidates. Whenever a 2D problem has constraints that decompose along rows and columns independently, projections are the tool.

Greedy cell-by-cell optimization

Once you have the projections, each cell is independent. The new height for (r, c) is min(rowMax[r], colMax[c]), and there is no interaction between cells. This means you can greedily maximize each cell without worrying about how it affects other cells.

This independence is what makes the problem greedy rather than dynamic programming. If increasing one building's height affected the constraint on another, you would need a more complex approach. But because the skyline depends only on the original maximums (which do not change when you increase shorter buildings), every cell can be optimized in isolation.

Edge cases

All cells already at their maximum: if every grid[r][c] equals min(rowMax[r], colMax[c]), the total increase is 0. This happens when the grid is already "skyline-optimal."
Single row or single column: rowMax and colMax each have one entry, and the constraint for every cell is min(rowMax[0], colMax[c]). The logic still works without special handling.
Uniform grid: if all values are the same, every row max and column max equals that value. No cell can increase, so the answer is 0.

From understanding to recall

You have seen that this problem reduces to two projection arrays and a single sweep. The core formula, min(rowMax[r], colMax[c]) - grid[r][c], is simple enough to remember. But under interview pressure, it is easy to second-guess yourself: "Wait, is it min or max? Do I use the original grid or the new grid?"

Spaced repetition removes that doubt. You practice writing the three-step solution from scratch: compute row maximums, compute column maximums, sum the differences. Do it today, again in two days, again in five. After a few reps, the projection-then-sweep pattern is automatic. You see "maximize without changing the skyline" and the code flows out.

The row/column projection pattern and the greedy cell-by-cell optimization are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the details stick.

Set Matrix Zeroes - Row and column tracking in matrices
Rotate Image - Matrix manipulation
Spiral Matrix - Matrix traversal patterns

CodeBricks breaks Max Increase to Keep City Skyline into its row/column projection and greedy sweep building blocks, then drills them independently with spaced repetition. You type the projection arrays and the min-constraint loop from scratch until the pattern is automatic. When a matrix constraint problem shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free