Domain 2MediumMEDIUM

Max Increase to Keep City Skyline

Calculate row and column maximums to determine the skyline limit for each cell, then sum the difference between these limits and current heights.

Domain: medium•Updated: 2026-09-01
#greedy#array/list#O(N^2)#O(N)

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 (N×NN \times N).
  • Constraints: 1<N≤501 < N \le 50, 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 exceed max(row[i]) or max(col[j]).
  • Optimal Height: The maximum height for cell (i, j) without changing skyline is min⁡(row_max[i],col_max[j])\min(\text{row\_max}[i], \text{col\_max}[j]).
  • Calculation: Sum of (limit−current_height)(\text{limit} - \text{current\_height}) 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 min⁡(row_max,col_max)\min(\text{row\_max}, \text{col\_max}). This transforms an optimization problem into a direct calculation based on precomputed limits.

Approach

  1. Precompute Limits:
    • Compute row_max array where each element is the maximum height in that row (Left/Right skyline).
    • Compute col_max array where each element is the maximum height in that column (Top/Bottom skyline).
  2. 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 ≤\le limit).
  3. Return Result:
    • Return the accumulated sum of increases.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We traverse the grid once to compute row/column maximums and again to calculate differences, resulting in two passes over N×NN \times N elements. Given constraints (N≤50N \le 50), this is highly efficient.
  • Space Complexity: O(N)O(N). We store row_max (size NN) and col_max (size NN). 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 - height becomes 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 (≤100\le 100) and grid size ≤50\le 50, integer overflow is not a concern in Python, which supports arbitrary precision integers automatically.