Problem Breakdown
We are given a square grid where each integer represents building height. The goal is to increase building heights such that the “skyline” (maximum height visible from Top, Bottom, Left, Right) remains unchanged while maximizing the total sum of increases.
Inputs:
- A 2D list (
grid) representing initial heights (). - Constraints: , Heights in
[0, 100].
Outputs:
- An integer representing the maximum total sum of height increases.
Implicit Logic:
- Skyline Definition: The skyline from Top/Bottom is defined by the max value in each column. Left/Right is defined by the max value in each row.
- Constraint Preservation: To maintain these skylines, no building at
(i, j)can exceedmax(row[i])ormax(col[j]). - Optimal Height: The maximum height for cell
(i, j)without changing skyline is . - Calculation: Sum of for all cells.
Intuition
The problem can be decomposed into two independent constraints per cell: one from its row and one from its column. The skyline is determined solely by the maximum height in each row/column view. Therefore, increasing a building’s height beyond the current row or column maximum would alter that specific part of the skyline. To maximize increase without violating these rules, every building should be raised to exactly . This transforms an optimization problem into a direct calculation based on precomputed limits.
Approach
- Precompute Limits:
- Compute
row_maxarray where each element is the maximum height in that row (Left/Right skyline). - Compute
col_maxarray where each element is the maximum height in that column (Top/Bottom skyline).
- Compute
- Calculate Increases:
- Iterate through every cell
(i, j)of the grid. - Determine the allowed limit:
limit = min(row_max[i], col_max[j]). - Add
limit - grid[i][j]to a running total (since original height is guaranteed limit).
- Iterate through every cell
- Return Result:
- Return the accumulated sum of increases.
Complexity Analysis
- Time Complexity: . We traverse the grid once to compute row/column maximums and again to calculate differences, resulting in two passes over elements. Given constraints (), this is highly efficient.
- Space Complexity: . We store
row_max(size ) andcol_max(size ). This linear space usage is optimal for storing skyline limits relative to input dimensions.
Solution
class Solution:
def maxIncreaseKeepingSkyline(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
n = len(grid)
# Step 1: Precompute row and column maximums (Skyline limits)
# Row max determines Left/Right skyline constraint for each row index
row_max = [max(row) for row in grid]
# Col max determines Top/Bottom skyline constraint for each col index
col_max = []
for j in range(n):
current_col_max = max(grid[i][j] for i in range(n))
col_max.append(current_col_max)
# Step 2: Calculate total possible increase
total_increase = 0
for r_idx, row in enumerate(grid):
for c_idx, height in enumerate(row):
# The building can be raised up to the minimum of its
# corresponding row skyline and column skyline.
limit = min(row_max[r_idx], col_max[c_idx])
# Add the difference between allowed max height and current height
total_increase += (limit - height)
return total_increase
Edge Cases Handled
- Empty/Null Input: The check
if not grid or not grid[0]:ensures safe handling of empty grids, returning 0. - Uniform Heights: If all buildings are equal to the row/column maxes,
limit - heightbecomes 0 for every cell, correctly resulting in a total increase sum of 0. - Zeros (Empty Cells): Height 0 is treated as valid input. The logic handles cells with 0 by calculating how much they can grow up to their respective skyline limits without issue.
- Maximum Heights: Since heights are bounded () and grid size , integer overflow is not a concern in Python, which supports arbitrary precision integers automatically.