#807

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Max Increase to Keep City Skyline

Maximize building heights in a city grid without changing the skyline, using greedy selection constrained by row and column maxima.

array greedy matrix

Problem Statement

You are given an n x n grid representing a city where each cell contains a building's height. The skyline of the city is defined as the outline visible from the north, south, east, and west directions, which are determined by the maximum heights in each row and column.

Your task is to increase the heights of the buildings without changing the skyline from any direction. You can increase any building's height by any amount, but no building can surpass the maximum of its row or column. Return the total sum by which the building heights can be increased.

Examples

Example 1

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output: 35

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

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

Solution Approach

Compute row and column maxima

Iterate over the grid to record the maximum height in each row and each column. These maxima define the constraints for how much each building can grow without changing the skyline.

Greedy height assignment

For each building, increase its height to the minimum of its row maximum and column maximum. This greedy choice ensures you maximize the increase locally while preserving all skyline constraints.

Aggregate total increase

Subtract the original height from the new height for each building and sum these differences across the grid. This yields the maximum total increase achievable without altering the skyline.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N)

Time complexity is O(N^2) because we traverse the grid multiple times for maxima computation and increase aggregation. Space complexity is O(N) to store row and column maxima arrays.

What Interviewers Usually Probe

Candidate first identifies row and column maxima as constraints.
Candidate applies a greedy approach per cell rather than attempting global optimization.
Candidate correctly sums increases without violating skyline invariants.

Common Pitfalls or Variants

Common pitfalls

Forgetting to limit increase by both row and column maxima, changing the skyline.
Attempting to sort or globally optimize instead of using greedy per cell.
Miscomputing the total increase by using absolute heights rather than differences.

Follow-up variants

Allow decreasing building heights to minimize the skyline while maximizing the sum of reductions.
Solve for rectangular m x n grids instead of square n x n grids.
Consider non-uniform skyline constraints where only specific rows or columns are constrained.

FAQ

What is the main strategy for Max Increase to Keep City Skyline?

Use the greedy approach constrained by row and column maxima to maximize each building's height without altering the skyline.

Can a building be increased beyond its row or column maximum?

No, increasing beyond either maximum would change the skyline and violate problem constraints.

What is the time complexity of the greedy solution?

The solution runs in O(N^2) time since it traverses the entire n x n grid for maxima computation and final aggregation.

How do I handle edge cases like all-zero grids?

If all buildings are zero, any increase may affect the skyline; in this case, the maximum increase is determined by the row and column maxima which are all zeros.

Does this problem fit a common algorithm pattern?

Yes, it exemplifies greedy choice plus invariant validation, where each cell is adjusted locally under row and column constraints.

terminal

Solution

Solution 1: Greedy

According to the problem description, we can increase the value of each cell $(i, j)$ to the smaller value between the maximum value of the $i$-th row and the $j$-th column, ensuring it does not affect the skyline. Thus, the height added to each cell is $\min(\textit{rowMax}[i], \textit{colMax}[j]) - \textit{grid}[i][j]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        row_max = [max(row) for row in grid]
        col_max = [max(col) for col in zip(*grid)]
        return sum(
            min(row_max[i], col_max[j]) - x
            for i, row in enumerate(grid)
            for j, x in enumerate(row)
        )

Continue Practicing

#861 score after flipping matrix #1253 reconstruct a 2 row binary matrix #1536 minimum swaps to arrange a binary grid