Max Increase to Keep City Skyline — Problem & Solution
Max Increase to Keep City Skyline solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Max Increase to Keep City Skyline is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Matrix
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There is a city whose buildings sit on an n × n grid; grid[r][c] is the height of the building at (r, c).
You may raise any building by any amount, provided the city's skyline — the silhouette seen from each of the four cardinal directions — does not change. Return the maximum total increase possible.
Example 1
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Example 2
Input: grid = [[0,0],[0,0]]
Output: 0
Example 3
Input: grid = [[5,2],[2,5]]
Output: 6
Constraints
1 <= grid.length <= 8grid[i].length == grid.length0 <= grid[r][c] <= 100
Hints for Max Increase to Keep City Skyline
Hint 1
The skyline from the left and right is the maximum of each row; from the top and bottom it is the maximum of each column.
Hint 2
So a building may grow up to
min(rowMax[r], colMax[c])without changing either silhouette.Hint 3
Add up the difference between that ceiling and the current height at every cell.
How to solve Max Increase to Keep City Skyline
The left/right skyline is each row's maximum and the top/bottom skyline is each column's maximum; a building can rise to min(rowMax[r], colMax[c]) without altering either.
Approach
- Compute
rowMaxandcolMax. - Sum
min(rowMax[r], colMax[c]) - grid[r][c]over all cells.
Why it works
Raising a cell to that ceiling never exceeds its row's or column's current maximum, so both silhouettes are unchanged; raising it further would change one of them. The ceilings are independent per cell, so the sum is the maximum total.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- The difference is never negative because each cell is at most both maxima.
Reference solution
Python
def maxIncreaseKeepingSkyline(grid) -> int:
row_max = [max(row) for row in grid]
col_max = [max(col) for col in zip(*grid)]
return sum(min(row_max[r], col_max[c]) - grid[r][c]
for r in range(len(grid)) for c in range(len(grid[0])))Java
public static int maxIncreaseKeepingSkyline(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rowMax = new int[m];
int[] colMax = new int[n];
for (int r = 0; r < m; r++) {
for (int 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];
}
}
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
total += Math.min(rowMax[r], colMax[c]) - grid[r][c];
}
}
return total;
}C++
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int m = (int) grid.size(), n = (int) grid[0].size();
vector<int> rowMax(m, 0), colMax(n, 0);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
rowMax[r] = max(rowMax[r], grid[r][c]);
colMax[c] = max(colMax[c], grid[r][c]);
}
}
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
total += min(rowMax[r], colMax[c]) - grid[r][c];
}
}
return total;
}JavaScript
var maxIncreaseKeepingSkyline = function(grid) {
const m = grid.length, n = grid[0].length;
const rowMax = [], colMax = [];
for (let r = 0; r < m; r++) {
let best = grid[r][0];
for (let c = 1; c < n; c++) {
if (grid[r][c] > best) best = grid[r][c];
}
rowMax.push(best);
}
for (let c = 0; c < n; c++) {
let best = grid[0][c];
for (let r = 1; r < m; r++) {
if (grid[r][c] > best) best = grid[r][c];
}
colMax.push(best);
}
let total = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
total += Math.min(rowMax[r], colMax[c]) - grid[r][c];
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms