Max Increase to Keep City Skyline

Med

#0761Time: O(n^3), where n is the size of the grid. We have two nested loops to iterate through each cell (O(n^2)). Inside these loops, we perform two more loops, each of size n, to find the row and column maximums. This results in a total complexity of O(n^2 * (n + n)) = O(n^3).Space: O(1), as we are not using any extra space that scales with the input size `n`. The variables `rowMax`, `colMax`, and `totalIncrease` use constant space.1 company

Patterns

Greedy

Data structures

Array Matrix

Companies

Rivian

Prompt

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.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every single building in the grid. For each building, it determines the maximum possible height it can be increased to without affecting the skyline. This is done by finding the maximum height in its corresponding row and column on the fly. The difference between this new maximum allowed height and the building's current height is then added to a running total.

Algorithm

Initialize a variable totalIncrease to 0.
Iterate through each row i from 0 to n-1.
Iterate through each column j from 0 to n-1.
Find the maximum height in row `i` (`rowMax`) by iterating through all columns `k`.
Find the maximum height in column `j` (`colMax`) by iterating through all rows `k`.
Calculate the potential increase: `min(rowMax, colMax) - grid[i][j]`.
Add this increase to `totalIncrease`.
Return totalIncrease.

Walkthrough

The core idea is to find the maximum allowed height for each building at grid[i][j]. The skyline is defined by the tallest building in each row and each column. Therefore, to not change the skyline, the new height of grid[i][j] cannot exceed the height of the tallest building in its row (rowMax) or its column (colMax). This means the new height must be at most min(rowMax, colMax). To maximize the total increase, we should raise each building's height to this maximum allowed value. The increase for a single building grid[i][j] is min(rowMax, colMax) - grid[i][j]. This naive approach calculates rowMax and colMax for each cell (i, j) inside the main loop, which leads to redundant calculations.

1class Solution {2    public int maxIncreaseKeepingSkyline(int[][] grid) {3        int n = grid.length;4        int totalIncrease = 0;5 6        for (int i = 0; i < n; i++) {7            for (int j = 0; j < n; j++) {8                // Find max in row i9                int rowMax = 0;10                for (int k = 0; k < n; k++) {11                    rowMax = Math.max(rowMax, grid[i][k]);12                }13 14                // Find max in column j15                int colMax = 0;16                for (int k = 0; k < n; k++) {17                    colMax = Math.max(colMax, grid[k][j]);18                }19 20                totalIncrease += Math.min(rowMax, colMax) - grid[i][j];21            }22        }23        return totalIncrease;24    }25}

Complexity

Time

O(n^3), where n is the size of the grid. We have two nested loops to iterate through each cell (O(n^2)). Inside these loops, we perform two more loops, each of size n, to find the row and column maximums. This results in a total complexity of O(n^2 * (n + n)) = O(n^3).

Space

O(1), as we are not using any extra space that scales with the input size `n`. The variables `rowMax`, `colMax`, and `totalIncrease` use constant space.

Trade-offs

Pros

Simple to understand and implement.
Very low memory usage.

Cons

Highly inefficient due to redundant calculations. The maximum for each row and column is calculated n times instead of just once.
Not suitable for larger grids, though it passes for the given constraints (n <= 50).

This approach improves upon the brute-force method by avoiding redundant calculations. It first pre-computes the skyline from all four cardinal directions. The skyline from the left/right is determined by the maximum height in each row, and the skyline from the top/bottom is determined by the maximum height in each column. After storing these maximums in two separate arrays, it iterates through the grid one final time to calculate the total possible increase.

Algorithm

Get the size of the grid, n.
Create two integer arrays, rowMaxes and colMaxes, of size n, initialized to 0.
Iterate through the grid with row i from 0 to n-1 and column j from 0 to n-1:
Update rowMaxes[i] = max(rowMaxes[i], grid[i][j]).
Update colMaxes[j] = max(colMaxes[j], grid[i][j]).
Initialize totalIncrease to 0.
Iterate through the grid again with row i and column j:
Calculate the increase: min(rowMaxes[i], colMaxes[j]) - grid[i][j].
Add this to totalIncrease.
Return totalIncrease.

Walkthrough

The logic remains the same: the maximum height a building at grid[i][j] can be increased to is min(rowMax[i], colMax[j]). The key optimization is to calculate all row maximums and all column maximums before calculating the total increase. We use two arrays, rowMaxes and colMaxes, of size n to store these pre-computed values. This avoids the O(n) work inside the main O(n^2) loop, bringing the overall time complexity down. The pre-computation of rowMaxes and colMaxes can be done in a single O(n^2) pass.

1class Solution {2    public int maxIncreaseKeepingSkyline(int[][] grid) {3        int n = grid.length;4        int[] rowMaxes = new int[n];5        int[] colMaxes = new int[n];6 7        // Pre-compute the maximums for each row and column8        for (int i = 0; i < n; i++) {9            for (int j = 0; j < n; j++) {10                rowMaxes[i] = Math.max(rowMaxes[i], grid[i][j]);11                colMaxes[j] = Math.max(colMaxes[j], grid[i][j]);12            }13        }14 15        int totalIncrease = 0;16        // Iterate through the grid to calculate the total increase17        for (int i = 0; i < n; i++) {18            for (int j = 0; j < n; j++) {19                totalIncrease += Math.min(rowMaxes[i], colMaxes[j]) - grid[i][j];20            }21        }22 23        return totalIncrease;24    }25}

Complexity

Time

O(n^2), where n is the size of the grid. We make two passes over the grid in concept (one for pre-computation, one for summing). The first pass to compute `rowMaxes` and `colMaxes` takes O(n^2). The second pass to calculate the total increase also takes O(n^2). The total time complexity is O(n^2) + O(n^2) = O(n^2).

Space

O(n), where n is the size of the grid. We use two arrays, `rowMaxes` and `colMaxes`, each of size `n`, to store the pre-computed maximums. Therefore, the space required is O(n) + O(n) = O(n).

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Optimal solution as every cell must be visited at least once, leading to a lower bound of O(n^2) for time complexity.
The logic is clear and follows the problem statement directly.

Cons

Uses extra space proportional to the grid dimension n, unlike the O(1) space brute-force approach.

Solutions

Solution

1class Solution {2public3  int maxIncreaseKeepingSkyline(int[][] grid) {4    int m = grid.length, n = grid[0].length;5    int[] rmx = new int[m];6    int[] cmx = new int[n];7    for (int i = 0; i < m; ++i) {8      for (int j = 0; j < n; ++j) {9        rmx[i] = Math.max(rmx[i], grid[i][j]);10        cmx[j] = Math.max(cmx[j], grid[i][j]);11      }12    }13    int ans = 0;14    for (int i = 0; i < m; ++i) {15      for (int j = 0; j < n; ++j) {16        ans += Math.min(rmx[i], cmx[j]) - grid[i][j];17      }18    }19    return ans;20  }21}

1class Solution {2public:3  int maxIncreaseKeepingSkyline(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    vector<int> rmx(m, 0);6    vector<int> cmx(n, 0);7    for (int i = 0; i < m; ++i) {8      for (int j = 0; j < n; ++j) {9        rmx[i] = max(rmx[i], grid[i][j]);10        cmx[j] = max(cmx[j], grid[i][j]);11      }12    }13    int ans = 0;14    for (int i = 0; i < m; ++i)15      for (int j = 0; j < n; ++j)16        ans += min(rmx[i], cmx[j]) - grid[i][j];17    return ans;18  }19};

1class Solution:2    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int: rmx = [max(row) for row in grid] cmx = [max(col) for col in zip(* grid)] return sum((min(rmx[i], cmx[j]) - grid[i][j]) for i in range(len(grid)) for j in range(len(grid[0])))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem