Max Increase to Keep City Skyline

Medium
285.

Max Increase to Keep City Skyline

Max Increase to Keep City Skyline is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Google interviews.

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 <= 8
  • grid[i].length == grid.length
  • 0 <= grid[r][c] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxIncreaseKeepingSkyline = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 8
  • grid[i].length == grid.length
  • 0 <= grid[r][c] <= 100

Hints for Max Increase to Keep City Skyline

  1. 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.

  2. Hint 2

    So a building may grow up to min(rowMax[r], colMax[c]) without changing either silhouette.

  3. 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

  1. Compute rowMax and colMax.
  2. 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