Watch 10 video solutions for Max Increase to Keep City Skyline, a medium level problem involving Array, Greedy, Matrix. This walkthrough by Nick White has 11,339 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.
A city's skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.
We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.
Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction.
Example 1:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
Example 2:
Input: grid = [[0,0,0],[0,0,0],[0,0,0]] Output: 0 Explanation: Increasing the height of any building will result in the skyline changing.
Constraints:
n == grid.lengthn == grid[r].length2 <= n <= 500 <= grid[r][c] <= 100Problem Overview: You are given an n x n grid where each value represents the height of a building. You can increase building heights, but the skyline viewed from the top/bottom (columns) and left/right (rows) must remain unchanged. The goal is to compute the maximum total height increase across all buildings while preserving those skylines.
Approach 1: Brute Force Skyline Check (O(n^3) time, O(1) space)
The skyline from the left/right is defined by the maximum value in each row, and the skyline from the top/bottom is defined by the maximum value in each column. A brute-force strategy recomputes the row maximum and column maximum for every cell before deciding how much that building can grow. For each position (i, j), iterate through row i to find the row max and through column j to find the column max. The allowed height becomes min(rowMax, colMax), and the increase is the difference from the current height. This repeatedly scans rows and columns, producing O(n^3) time complexity. It works but wastes computation because the same maxima are recalculated many times.
Approach 2: Row and Column Maximum Approach (O(n^2) time, O(n) space)
The key observation: the skyline constraints are fixed by the maximum value in each row and column. First compute two arrays: rowMax[i] for every row and colMax[j] for every column. This requires one pass through the grid. For each cell (i, j), the tallest possible building that keeps both skylines unchanged is min(rowMax[i], colMax[j]). The allowed increase is min(rowMax[i], colMax[j]) - grid[i][j]. Summing this for all cells gives the final answer. Each cell is processed a constant number of times, giving O(n^2) time and O(n) extra space for the two arrays.
This technique is a clean combination of Array traversal and Matrix analysis. The decision rule min(rowMax, colMax) acts like a local Greedy constraint: increase each building as much as possible without breaking skyline limits.
Recommended for interviews: The row and column maximum approach is the expected solution. Interviewers want to see the skyline constraint translated into row/column maxima and then applied with a simple min() rule. Mentioning the brute force approach first shows you understand the constraint, but precomputing maxima demonstrates optimization awareness and clean problem decomposition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Skyline Check | O(n^3) | O(1) | Useful for explaining the skyline constraint before optimizing |
| Row and Column Maximum Approach | O(n^2) | O(n) | Optimal solution for interviews and production code |