Skip to main content
Talentd

Max Increase to Keep City Skyline - Solution & Explanation

MediumArrayGreedyMatrix15 min readAsked at: Meta, Google, Rivian
Practice this problem

Problem Statement

There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.

A city's skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.

Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction.

 

Example 1:

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You are given an n x n grid where each value represents the height of a building. You can increase building heights, but the skyline viewed from the top/bottom (columns) and left/right (rows) must remain unchanged. The goal is to compute the maximum total height increase across all buildings while preserving those skylines.

Approach 1: Brute Force Skyline Check (O(n^3) time, O(1) space)

The skyline from the left/right is defined by the maximum value in each row, and the skyline from the top/bottom is defined by the maximum value in each column. A brute-force strategy recomputes the row maximum and column maximum for every cell before deciding how much that building can grow. For each position (i, j), iterate through row i to find the row max and through column j to find the column max. The allowed height becomes min(rowMax, colMax), and the increase is the difference from the current height. This repeatedly scans rows and columns, producing O(n^3) time complexity. It works but wastes computation because the same maxima are recalculated many times.

Approach 2: Row and Column Maximum Approach (O(n^2) time, O(n) space)

The key observation: the skyline constraints are fixed by the maximum value in each row and column. First compute two arrays: rowMax[i] for every row and colMax[j] for every column. This requires one pass through the grid. For each cell (i, j), the tallest possible building that keeps both skylines unchanged is min(rowMax[i], colMax[j]). The allowed increase is min(rowMax[i], colMax[j]) - grid[i][j]. Summing this for all cells gives the final answer. Each cell is processed a constant number of times, giving O(n^2) time and O(n) extra space for the two arrays.

This technique is a clean combination of Array traversal and Matrix analysis. The decision rule min(rowMax, colMax) acts like a local Greedy constraint: increase each building as much as possible without breaking skyline limits.

Recommended for interviews: The row and column maximum approach is the expected solution. Interviewers want to see the skyline constraint translated into row/column maxima and then applied with a simple min() rule. Mentioning the brute force approach first shows you understand the constraint, but precomputing maxima demonstrates optimization awareness and clean problem decomposition.

Approach 1: Row and Column Maximum Approach

This approach involves calculating the maximum possible heights for each building in the grid so that the skyline remains unchanged. To achieve this, determine the maximum heights seen from the north/south (for each column) and from the west/east (for each row). For each building, the new maximum height is the minimum of these two values. This way, the skyline's constraints are not violated.

Once you compute the possible maximum height for each building, the sum of differences between these new heights and the original heights will yield the maximum total sum that the heights can be increased by.

This C solution first computes the maximum height seen from each row and column and stores them in two arrays, maxRow and maxCol. Then, it iterates over each building position in the grid to calculate the new possible height by taking the minimum value between the corresponding values in maxRow and maxCol. The potential increase for each building is accumulated to give the total maximum increase possible without altering the skyline.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) where n is the number of rows (or columns) in the grid since we must iterate over the entire grid at least twice (once for calculating maxRow and maxCol, and once for computing the total increase).
Space Complexity: O(n), as additional space for storing the skyline views of rows and columns is required.

Try this approach in the editor →

Approach 2: Greedy

According to the problem description, we can increase the value of each cell (i, j) to the smaller value between the maximum value of the i-th row and the j-th column, ensuring it does not affect the skyline. Thus, the height added to each cell is min(rowMax[i], colMax[j]) - grid[i][j].

Therefore, we can first traverse the matrix once to calculate the maximum value of each row and column, storing them in the arrays rowMax and colMax, respectively. Then, we traverse the matrix again to compute the answer.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Row and Column Maximum Approach

Time Complexity: O(n^2) where n is the number of rows (or columns) in the grid since we must iterate over the entire grid at least twice (once for calculating maxRow and maxCol, and once for computing the total increase).
Space Complexity: O(n), as additional space for storing the skyline views of rows and columns is required.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Skyline CheckO(n^3)O(1)Useful for explaining the skyline constraint before optimizing
Row and Column Maximum ApproachO(n^2)O(n)Optimal solution for interviews and production code

Video Solution

LeetCode Max Increase to Keep City Skyline Solution Explained - Java • Nick White • 11,422 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Increase to Keep City Skyline easy or hard?
The problem is rated Medium on LeetCode but is conceptually straightforward once you identify that skylines correspond to row and column maximums. The challenge is recognizing the min(rowMax, colMax) constraint for each building.
Max Increase to Keep City Skyline Python/Java solution
Most implementations follow the same structure across languages: compute rowMax and colMax arrays, then iterate through the grid to accumulate the allowed increase. The logic is identical in Python, Java, C++, C, C#, and JavaScript.
How to solve Max Increase to Keep City Skyline in O(n^2)?
First compute the maximum value of each row and each column in one pass through the grid. Then iterate through the grid again and increase each building to min(rowMax[i], colMax[j]) while summing the difference from its current height. This guarantees the skyline remains unchanged.
What is the best approach for Max Increase to Keep City Skyline?
The optimal approach precomputes the maximum height for every row and column. For each cell, the tallest allowed value is min(rowMax[i], colMax[j]) so the skyline from both directions stays unchanged. This method runs in O(n^2) time with O(n) extra space.
Is Max Increase to Keep City Skyline asked at Google/Amazon/Meta?
Max Increase to Keep City Skyline is a common matrix and greedy-style interview problem seen in coding interviews and practice sets similar to those used by companies like Amazon and Google. It tests reasoning about constraints derived from row and column maxima.
What data structure is used in Max Increase to Keep City Skyline?
The solution primarily uses arrays to store row maximums and column maximums. The input grid is treated as a matrix, and simple array lookups allow constant-time checks for the skyline constraint.
What is the time complexity of Max Increase to Keep City Skyline?
The optimal solution runs in O(n^2) time because each grid cell is processed a constant number of times. Two arrays store row and column maxima, which also requires O(n) extra space.

Ready to solve this problem?

Practice Max Increase to Keep City Skyline with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays