Max Increase to Keep City Skyline

Max Increase to Keep City Skyline

What is this problem about?

The Max Increase to Keep City Skyline problem gives you an n x n grid representing the heights of buildings in a city. The "skyline" is the outer contour of the city viewed from the four cardinal directions (North, South, East, West). The North/South skyline is determined by the maximum building height in each column. The East/West skyline is determined by the maximum building height in each row. You want to increase the height of buildings as much as possible without changing the original skyline. Return the total sum of height increases.

Why is this asked in interviews?

This is a fun, highly visual Matrix traversal problem. Interviewers use it to see if candidates can abstract visual concepts into mathematical constraints. It is essentially a test of Precomputation and Greedy Algorithms. It separates candidates who overcomplicate with 3D models from those who realize it's just finding row and column maximums.

Algorithmic pattern used

This problem relies on a Greedy approach via Array Precomputation. To ensure the skyline doesn't change, no building at (r, c) can be raised higher than the maximum building in its row r, nor higher than the maximum building in its column c. Therefore, the maximum allowable height for any given building is simply min(max_of_row[r], max_of_col[c]).

1. First pass: Precompute max_row array and max_col array.
2. Second pass: For every cell, calculate the allowed increase: min(max_row[r], max_col[c]) - grid[r][c]. Sum these up.

Example explanation

Grid:

3 0 8 4
2 4 5 7
9 2 6 3

1. Calculate Maximums:

• Row maxes: [8, 7, 9]
• Col maxes: [9, 4, 8, 7]

1. Calculate max increases:

• Cell (0,0) is 3. Row max is 8, Col max is 9. Limit is min(8, 9) = 8. Increase = 8 - 3 = 5.
• Cell (0,1) is 0. Limit is min(8, 4) = 4. Increase = 4 - 0 = 4.
• Cell (1,1) is 4. Limit is min(7, 4) = 4. Increase = 4 - 4 = 0. By applying this greedy logic cell by cell and summing the differences, you get the absolute maximum total increase without altering the outer contour.

Common mistakes candidates make

Candidates rarely fail the logic, but they often fail to optimize. A common mistake is finding the row max and column max inside the nested loops for every single cell. Since finding a max takes $O(N)$ time, doing this for $N^2$ cells results in an $O(N^3)$ time complexity. Precomputing the maxes in $O(N^2)$ time first is strictly required for optimal performance.

Interview preparation tip

For the Max Increase to Keep City Skyline coding problem, always emphasize the time complexity optimization to your interviewer. State clearly: "To avoid recalculating the skyline for every building, I will precompute the row and column maximums in a single pass." This demonstrates strong fundamental engineering principles regarding caching and redundant work elimination.