Max Increase to Keep City Skyline

medium arrays matrix greedy

Problem

Given an n x n grid of building heights, you may increase each building's height. The grid's skyline viewed from top/bottom/left/right must remain the same. Return the maximum total sum of increases.

Inputgrid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output35

See LeetCode; each cell rises to min(row max, col max).

grid

def maxIncreaseKeepingSkyline(grid):
    n = len(grid)
    row_max = [max(r) for r in grid]
    col_max = [max(grid[i][j] for i in range(n)) for j in range(n)]
    total = 0
    for i in range(n):
        for j in range(n):
            total += min(row_max[i], col_max[j]) - grid[i][j]
    return total

var maxIncreaseKeepingSkyline = function(grid) {
    const n = grid.length;
    const rowMax = grid.map(r => Math.max(...r));
    const colMax = new Array(n).fill(0);
    for (let j = 0; j < n; j++) for (let i = 0; i < n; i++) colMax[j] = Math.max(colMax[j], grid[i][j]);
    let total = 0;
    for (let i = 0; i < n; i++)
        for (let j = 0; j < n; j++)
            total += Math.min(rowMax[i], colMax[j]) - grid[i][j];
    return total;
};

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int[] rowMax = new int[n], colMax = new int[n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            rowMax[i] = Math.max(rowMax[i], grid[i][j]);
            colMax[j] = Math.max(colMax[j], grid[i][j]);
        }
        int total = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
            total += Math.min(rowMax[i], colMax[j]) - grid[i][j];
        return total;
    }
}

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> rowMax(n, 0), colMax(n, 0);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            rowMax[i] = max(rowMax[i], grid[i][j]);
            colMax[j] = max(colMax[j], grid[i][j]);
        }
        int total = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
            total += min(rowMax[i], colMax[j]) - grid[i][j];
        return total;
    }
};

Explanation

The skyline seen from the left/right is just the tallest building in each row, and the skyline from top/bottom is the tallest in each column. To keep those silhouettes unchanged, a building can grow but must not poke above either limit.

So we first compute rowMax[i] (the max in row i) and colMax[j] (the max in column j).

Each cell (i, j) can safely rise to min(rowMax[i], colMax[j]) — the smaller of its two skyline limits. The gain for that cell is that cap minus its current height, grid[i][j].

Summing those per-cell gains over the whole grid gives the maximum total increase. Taking the min guarantees no row or column silhouette ever changes.

Example: a cell of height 2 sitting in a row whose max is 8 and a column whose max is 5 can rise to min(8, 5) = 5, adding 3. Doing this everywhere yields 35 for the sample grid.

Time: O(n^2) Space: O(n)