To solve Max Increase to Keep City Skyline, identify the maximum height in each row and column. Then, greedily increase each building to the minimal value of its row and column maximum while preserving the skyline. Sum all height increases to compute the total maximum increase efficiently.
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.
How GhostInterview Helps
- Highlights the greedy choice plus invariant pattern for skyline constraints.
- Automatically computes row and column maxima to prevent common missteps.
- Guides calculation of total increase efficiently for interview execution.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Max Increase to Keep City Skyline instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Max Increase to Keep City Skyline from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize the score of a binary matrix by flipping rows and columns using a greedy approach and validation of invariants.
Open problem page#1253 Reconstruct a 2-Row Binary MatrixReconstruct a 2-row binary matrix by distributing column sums while respecting upper and lower row limits using greedy placement.
Open problem page#1536 Minimum Swaps to Arrange a Binary GridCompute the minimum number of adjacent row swaps to transform a binary grid so all upper-triangle cells are zero using a greedy approach.
Open problem page