Problem Description

You have a city represented as an n x n grid where each cell grid[r][c] contains the height of a building at row r and column c.

The skyline is what you see when looking at the city from far away in each direction (north, east, south, west). When viewing from:

• North or South: You see the maximum height in each column
• East or West: You see the maximum height in each row

Your task is to increase the heights of buildings to maximize the total sum of increases, but with one constraint: the skyline from all four directions must remain unchanged.

For example, if a building at position (i, j) has height grid[i][j], you can increase it up to min(rowMax[i], colMax[j]) where:

• rowMax[i] is the maximum height in row i (the skyline when viewing from east/west)
• colMax[j] is the maximum height in column j (the skyline when viewing from north/south)

This ensures that:

• The building doesn't become taller than the tallest building in its row (preserving east/west skyline)
• The building doesn't become taller than the tallest building in its column (preserving north/south skyline)

Return the maximum total sum by which you can increase the heights of all buildings without changing any skyline view.

Intuition

The key insight is understanding what preserves the skyline. When we look at the city from any direction, we only see the tallest building in each row or column - these form the skyline silhouette.

Think about a single building at position (i, j). If we increase its height:

• It cannot exceed the current maximum in row i, otherwise we'd change the east/west skyline
• It cannot exceed the current maximum in column j, otherwise we'd change the north/south skyline

So the maximum safe height for any building is the minimum of these two constraints: min(rowMax[i], colMax[j]).

Why does this work? Consider what happens when we increase a building's height to exactly min(rowMax[i], colMax[j]):

• If rowMax[i] < colMax[j], the building reaches the row's maximum but stays below the column's maximum. The row skyline stays the same (still has the same max), and the column skyline is unaffected.
• If colMax[j] < rowMax[i], the building reaches the column's maximum but stays below the row's maximum. Similar reasoning applies.
• If they're equal, the building reaches both limits simultaneously but doesn't exceed either.

This greedy approach is optimal because we're maximizing each building's height independently within its constraints. Since each building's contribution to the total sum is independent, maximizing each one individually gives us the maximum total sum.

The solution naturally follows: first scan the grid to find all row and column maximums, then for each building, calculate how much we can increase it: min(rowMax[i], colMax[j]) - grid[i][j].

Learn more about Greedy patterns.

Solution Approach

The implementation follows a straightforward greedy approach with two passes through the grid:

Step 1: Calculate Row and Column Maximums

First, we need to find the maximum height in each row and column:

• row_max = [max(row) for row in grid] - This iterates through each row and finds its maximum value
• col_max = [max(col) for col in zip(*grid)] - This uses zip(*grid) to transpose the matrix (converting rows to columns), then finds the maximum of each column

The zip(*grid) operation is a Python idiom that effectively transposes the matrix. For example, if grid = [[1,2], [3,4]], then zip(*grid) gives us [(1,3), (2,4)], which are the columns.

Step 2: Calculate Total Increase

Next, we calculate the sum of all possible increases:

sum(
    min(row_max[i], col_max[j]) - x
    for i, row in enumerate(grid)
    for j, x in enumerate(row)
)

This nested comprehension:

1. Iterates through each cell (i, j) with value x in the grid
2. Calculates the maximum safe height: min(row_max[i], col_max[j])
3. Subtracts the current height x to get the increase amount
4. Sums all these increases

Time Complexity: O(n²) where n is the grid dimension - we traverse the grid twice (once for finding maximums, once for calculating increases)

Space Complexity: O(n) for storing the row_max and col_max arrays

The beauty of this solution is its simplicity - by pre-computing the constraints (row and column maximums), we can determine each building's optimal height in a single calculation.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 grid:

grid = [[3, 0, 8],
        [2, 4, 5],
        [9, 2, 6]]

Step 1: Calculate Row and Column Maximums

First, find the maximum height in each row:

• Row 0: max(3, 0, 8) = 8
• Row 1: max(2, 4, 5) = 5
• Row 2: max(9, 2, 6) = 9
• row_max = [8, 5, 9]

Next, find the maximum height in each column:

• Column 0: max(3, 2, 9) = 9
• Column 1: max(0, 4, 2) = 4
• Column 2: max(8, 5, 6) = 8
• col_max = [9, 4, 8]

Step 2: Calculate Increases for Each Building

Now examine each building and determine how much we can increase it:

Position (0,0): Current height = 3

• Row max = 8, Column max = 9
• Can increase to min(8, 9) = 8
• Increase = 8 - 3 = 5

Position (0,1): Current height = 0

• Row max = 8, Column max = 4
• Can increase to min(8, 4) = 4
• Increase = 4 - 0 = 4

Position (0,2): Current height = 8

• Row max = 8, Column max = 8
• Can increase to min(8, 8) = 8
• Increase = 8 - 8 = 0 (already at maximum)

Position (1,0): Current height = 2

• Row max = 5, Column max = 9
• Can increase to min(5, 9) = 5
• Increase = 5 - 2 = 3

Position (1,1): Current height = 4

• Row max = 5, Column max = 4
• Can increase to min(5, 4) = 4
• Increase = 4 - 4 = 0 (already at maximum)

Position (1,2): Current height = 5

• Row max = 5, Column max = 8
• Can increase to min(5, 8) = 5
• Increase = 5 - 5 = 0 (already at maximum)

Position (2,0): Current height = 9

• Row max = 9, Column max = 9
• Can increase to min(9, 9) = 9
• Increase = 9 - 9 = 0 (already at maximum)

Position (2,1): Current height = 2

• Row max = 9, Column max = 4
• Can increase to min(9, 4) = 4
• Increase = 4 - 2 = 2

Position (2,2): Current height = 6

• Row max = 9, Column max = 8
• Can increase to min(9, 8) = 8
• Increase = 8 - 6 = 2

Total sum of increases = 5 + 4 + 0 + 3 + 0 + 0 + 0 + 2 + 2 = 16

The final grid after all increases would be:

[[8, 4, 8],
 [5, 4, 5],
 [9, 4, 8]]

Notice how the skylines remain unchanged:

• From North/South (column maxes): [9, 4, 8] ✓
• From East/West (row maxes): [8, 5, 9] ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the side length of the matrix grid.

• Computing row_max: Iterating through each row and finding the maximum takes O(n) per row, with n rows total, resulting in O(n²).
• Computing col_max: The zip(*grid) operation transposes the matrix in O(n²) time, and finding the maximum for each column takes O(n) per column, with n columns total, resulting in O(n²).
• The final sum operation uses nested iteration through all n² elements of the grid, where each operation inside (accessing row_max[i], col_max[j], and computing the difference) takes O(1) time, resulting in O(n²).

Overall time complexity: O(n²) + O(n²) + O(n²) = O(n²).

The space complexity is O(n), where n is the side length of the matrix grid.

• row_max stores n values (one maximum per row): O(n).
• col_max stores n values (one maximum per column): O(n).
• The generator expression in the sum doesn't create additional storage beyond temporary variables: O(1).

Overall space complexity: O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Grid

A common mistake is attempting to modify the grid in-place while calculating the increases, which can lead to incorrect results if you need to reference the original values later.

Incorrect approach:

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)]
    total = 0
  
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            new_height = min(row_max[i], col_max[j])
            total += new_height - grid[i][j]
            grid[i][j] = new_height  # DON'T DO THIS - modifies input
  
    return total

Solution: Keep the grid unchanged and only calculate the differences.

2. Assuming Square Grid

The code assumes an n x n square grid, but the problem might have rectangular grids (m x n). Using incorrect indices can cause index out of bounds errors.

Incorrect approach:

def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
    n = len(grid)  # Assumes square grid
    row_max = [max(grid[i]) for i in range(n)]
    col_max = [max(grid[i][j] for i in range(n)) for j in range(n)]  # Wrong for non-square

Solution: Handle rectangular grids properly:

def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0]) if grid else 0
    row_max = [max(row) for row in grid]
    col_max = [max(grid[i][j] for i in range(rows)) for j in range(cols)]

3. Misunderstanding the Constraint

Some might think they need to increase every building to exactly min(row_max[i], col_max[j]), but the problem asks for the maximum total increase, which means each building should be increased as much as possible (up to the constraint).

Incorrect interpretation: Thinking you need to choose which buildings to increase. Correct interpretation: Every building should be increased to its maximum allowed height.

4. Empty Grid Edge Case

Not handling empty grids or grids with empty rows can cause the code to crash.

Solution: Add validation:

def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
    if not grid or not grid[0]:
        return 0
  
    # Rest of the implementation...

5. Using Wrong Transpose Method

Attempting to transpose manually with incorrect indexing is error-prone.

Incorrect approach:

col_max = []
for j in range(len(grid)):
    col_max.append(max(grid[i][j] for i in range(len(grid))))  # Might fail if not square

Solution: Use zip(*grid) which handles the transpose elegantly and works for any rectangular grid.