13 Sept 2026•Go / Python / TypeScript•Medium

Max Increase to Keep City Skyline

Maximize the total height increase while preserving every row and column skyline.

Compute the maximum height in each row and column. Each building can grow to the smaller of those two skyline limits, so sum the difference between that limit and the original height.

complexity

O(n²) time and O(n) auxiliary space for an n × n grid.

solution files

Go max-increase-to-keep-city-skyline/solution.go
Python max-increase-to-keep-city-skyline/solution.py
TypeScript max-increase-to-keep-city-skyline/solution.ts

Solution files

Go•max-increase-to-keep-city-skyline/solution.go

package main

func maxIncreaseKeepingSkyline(grid [][]int) int {
	n := len(grid)
	rowMax := make([]int, n)
	columnMax := make([]int, n)

	for row := 0; row < n; row++ {
		for column := 0; column < n; column++ {
			if grid[row][column] > rowMax[row] {
				rowMax[row] = grid[row][column]
			}
			if grid[row][column] > columnMax[column] {
				columnMax[column] = grid[row][column]
			}
		}
	}

	total := 0
	for row := 0; row < n; row++ {
		for column := 0; column < n; column++ {
			limit := rowMax[row]
			if columnMax[column] < limit {
				limit = columnMax[column]
			}
			total += limit - grid[row][column]
		}
	}

	return total
}

Python•max-increase-to-keep-city-skyline/solution.py

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: list[list[int]]) -> int:
        row_max = [max(row) for row in grid]
        column_max = [max(column) for column in zip(*grid)]

        return sum(
            min(row_max[row], column_max[column]) - grid[row][column]
            for row in range(len(grid))
            for column in range(len(grid))
        )

TypeScript•max-increase-to-keep-city-skyline/solution.ts

function maxIncreaseKeepingSkyline(grid: number[][]): number {
  const rowMax = grid.map((row) => Math.max(...row));
  const columnMax = grid[class="syntax-number">0].map((_, column) =>
    Math.max(...grid.map((row) => row[column])),
  );

  return grid.reduce(
    (total, row, r) =>
      total +
      row.reduce(
        (rowTotal, height, c) =>
          rowTotal + Math.min(rowMax[r], columnMax[c]) - height,
        class="syntax-number">0,
      ),
    class="syntax-number">0,
  );
}