Max Increase to Keep City Skyline Solution In C++/Python/java/JS
Problem Description
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
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] ]
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
Figuring out "Max Increase to Keep City Skyline solution" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!
Optimal Approach
Intuition
So, let's imagine we’re given a city built on a square grid, say n x n. Each cell in this grid represents a building, and the number inside it is its height. Got that?
So it's kind of like a bird’s-eye view of a city?
Exactly! Now here’s the twist—someone comes along and wants to increase the height of some buildings. That sounds harmless, right?
Hold on though we have got some constraint. The skyline of the city—when seen from any direction: North, South, East, or West - must remain the same.
Alright, so if we are looking at the city from the north, the contour - the silhouette of the tallest buildings in each column should not change?
Same goes for each row when seen from the east or west.
Now, the question becomes: how much can we increase the height of buildings in total without altering the skyline?
Let’s Build Intuition Together
Let’s forget the problem for a second. Say we’ve got a simpler 3x3 grid:
[2, 5, 3]
[4, 1, 6]
[7, 3, 2]
Want to try visualizing this? Each number is a building’s height. Now let’s figure out the skyline.
From the West (left to right), what do we see for each row?
The tallest in each row?
Row 0: 5
Row 1: 6
Row 2: 7
So that gives us: [5, 6, 7]
Yup! That’s the skyline from the west or east—depending on direction, just reverse.
Now, what about the North (top to bottom)? We want the tallest in each column.
That would be:
Column 0: max(2, 4, 7) = 7
Column 1: max(5, 1, 3) = 5
Column 2: max(3, 6, 2) = 6
So: [7, 5, 6]
Perfect! Now here's the real question: at cell (0, 0) which has height 2—how tall can we make it without changing the skyline?
Hmm... row max is 5, column max is 7. So maybe... min(5, 7) = 5?
Exactly! Because if we go beyond 5, we’ll change the row's skyline.
So we can raise that building from 2 → 5, gaining +3.
So for each building, we can look at its row max and column max, and raise it up to the minimum of those two?
That’s the core insight!
Let’s Connect the Dots
Now that we know how much we can raise each building, we just loop through the grid:
For each (i, j), the max we can raise grid[i][j] is: min(rowMax[i], colMax[j]) - grid[i][j]
We just sum these up, and that’s our answer.
This is actually a greedy idea under the hood. We're always taking the max possible height per building, while staying within constraints.
Let’s Try Our Grid Example
Given:
grid = [
[2, 5, 3],
[4, 1, 6],
[7, 3, 2]
]
Row maxes: [5, 6, 7]
Col maxes: [7, 5, 6]
Let’s compute how much each building can be raised:
|
Cell |
Current |
RowMax |
ColMax |
MaxPossible |
Increase |
|
(0,0) |
2 |
5 |
7 |
5 |
+3 |
|
(0,1) |
5 |
5 |
5 |
5 |
0 |
|
(0,2) |
3 |
5 |
6 |
5 |
+2 |
|
(1,0) |
4 |
6 |
7 |
6 |
+2 |
|
(1,1) |
1 |
6 |
5 |
5 |
+4 |
|
(1,2) |
6 |
6 |
6 |
6 |
0 |
|
(2,0) |
7 |
7 |
7 |
7 |
0 |
|
(2,1) |
3 |
7 |
5 |
5 |
+2 |
|
(2,2) |
2 |
7 |
6 |
6 |
+4 |
Total increase: 3 + 0 + 2 + 2 + 4 + 0 + 0 + 2 + 4 = 17
Wrapping Up
So what are we thinking? Were we just mindlessly increasing heights?
Nope—we were carefully respecting the skyline limits and maximizing within them! Exactly. It's like doing renovations in a heritage zone: build up all you want—as long as no one outside notices!
Yes! Now, let’s outline the steps of our Algorithm
Max Increase to Keep City Skyline Algorithm
Initialize dimensions: Get the number of rows (numRows) and columns (numCols) from the input grid.
Prepare to track skyline limits:
- Create an array maxRowHeights of size numRows to store the maximum height in each row.
- Create an array maxColHeights of size numCols to store the maximum height in each column.
Compute skyline values:
- Loop through each cell in the grid:
- For each cell (row, col), update:
- maxRowHeights[row] as the maximum of its current value and grid[row][col].
- maxColHeights[col] as the maximum of its current value and grid[row][col].
- For each cell (row, col), update:
Calculate potential height increases:
- Initialize totalIncrease to 0.
- Loop through each cell in the grid again:
- For each cell (row, col):
- Determine the maximum allowed new height as min(maxRowHeights[row], maxColHeights[col]).
- Add the difference between this new height and the original height (newHeight - grid[row][col]) to totalIncrease.
- For each cell (row, col):
Return the result: Return the total possible increase in building heights that does not change the city's skyline.
Let's Now Visualize the Dry-Run with a Video
Dry-Run
grid = [[1, 2, 3],[4, 2, 1],[3, 2, 1]]
Output: 6
Step-by-step Dry Run:
1. Initialize sizes
- numRows = 3, numCols = 3
- maxRowHeights = {0, 0, 0}
- maxColHeights = {0, 0, 0}
2. Compute max in each row and column
Row 0:
- maxRowHeights[0] = max(0, 1) = 1
- maxColHeights[0] = max(0, 1) = 1
- maxRowHeights[0] = max(1, 2) = 2
- maxColHeights[1] = max(0, 2) = 2
- maxRowHeights[0] = max(2, 3) = 3
- maxColHeights[2] = max(0, 3) = 3
Row 1:
- maxRowHeights[1] = max(0, 4) = 4
- maxColHeights[0] = max(1, 4) = 4
- maxColHeights[1] = max(2, 2) = 2
- maxColHeights[2] = max(3, 1) = 3
Row 2:
- maxRowHeights[2] = max(0, 3) = 3
- maxColHeights[0] = max(4, 3) = 4
- maxColHeights[1] = max(2, 2) = 2
- maxColHeights[2] = max(3, 1) = 3
Final values:
- maxRowHeights = {3, 4, 3}
- maxColHeights = {4, 2, 3}
3. Compute maximum increase for each cell
Row 0:
- (0, 0): min(3, 4) = 3 → Increase = 3 - 1 = 2
- (0, 1): min(3, 2) = 2 → Increase = 2 - 2 = 0
- (0, 2): min(3, 3) = 3 → Increase = 3 - 3 = 0
Subtotal = 2 + 0 + 0 = 2
Row 1:
- (1, 0): min(4, 4) = 4 → Increase = 4 - 4 = 0
- (1, 1): min(4, 2) = 2 → Increase = 2 - 2 = 0
- (1, 2): min(4, 3) = 3 → Increase = 3 - 1 = 2
Subtotal = 0 + 0 + 2 = 2 → Total so far = 4
Row 2:
- (2, 0): min(3, 4) = 3 → Increase = 3 - 3 = 0
- (2, 1): min(3, 2) = 2 → Increase = 2 - 2 = 0
- (2, 2): min(3, 3) = 3 → Increase = 3 - 1 = 2
Subtotal = 0 + 0 + 2 = 2 → Final Total = 6
Final Output: 6
Max Increase to Keep City Skyline Solution
Now lets checkout the "Max Increase to Keep City Skyline code in C++ , Java, Python and JavaScript.
"Max Increase to Keep City Skyline" Code in all Languages.
1. Max Increase to Keep City Skyline solution in C++ Try on Compiler
class Solution {
public:
// Method to calculate the maximum increase without changing the skyline
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
// Get number of rows and columns
int numRows = grid.size();
int numCols = grid[0].size();
// Arrays to store max height in each row and column
vector<int> maxRowHeights(numRows, 0);
vector<int> maxColHeights(numCols, 0);
// Find max height for each row and column
for (int row = 0; row < numRows; ++row) {
for (int col = 0; col < numCols; ++col) {
maxRowHeights[row] = max(maxRowHeights[row], grid[row][col]);
maxColHeights[col] = max(maxColHeights[col], grid[row][col]);
}
}
// Variable to store total increase
int totalIncrease = 0;
// Calculate possible increase for each building
for (int row = 0; row < numRows; ++row) {
for (int col = 0; col < numCols; ++col) {
int newHeight = min(maxRowHeights[row], maxColHeights[col]);
totalIncrease += newHeight - grid[row][col];
}
}
return totalIncrease;
}
};2. Max Increase to Keep City Skyline Solution in Java Try on Compiler
class Solution {
// Method to calculate the maximum total increase in building heights without changing the skyline
public int maxIncreaseKeepingSkyline(int[][] grid) {
// Get the number of rows and columns of the grid
int numRows = grid.length;
int numCols = grid[0].length;
// Initialize arrays to store the maximum height in each row and each column
int[] maxRowHeights = new int[numRows];
int[] maxColHeights = new int[numCols];
// Compute the maximum height for each row and column
for (int row = 0; row < numRows; ++row) {
for (int col = 0; col < numCols; ++col) {
maxRowHeights[row] = Math.max(maxRowHeights[row], grid[row][col]);
maxColHeights[col] = Math.max(maxColHeights[col], grid[row][col]);
}
}
// Initialize a variable to track the total increase
int totalIncrease = 0;
// Calculate the possible increase for each cell without changing the skyline
for (int row = 0; row < numRows; ++row) {
for (int col = 0; col < numCols; ++col) {
// The new height must be the minimum of the maximum row and column height
int newHeight = Math.min(maxRowHeights[row], maxColHeights[col]);
// Add the difference between the new height and original height to total increase
totalIncrease += newHeight - grid[row][col];
}
}
// Return the computed total increase
return totalIncrease;
}
}3. Max Increase to Keep City Skyline Solution in Python Try on Compiler
class Solution:
# Method to compute max increase without changing the skyline
def maxIncreaseKeepingSkyline(self, grid):
# Number of rows and columns
numRows = len(grid)
numCols = len(grid[0])
# Max in each row and column
maxRowHeights = [max(row) for row in grid]
maxColHeights = [max(col) for col in zip(*grid)]
# Total increase tracker
totalIncrease = 0
# Calculate increase for each cell
for i in range(numRows):
for j in range(numCols):
newHeight = min(maxRowHeights[i], maxColHeights[j])
totalIncrease += newHeight - grid[i][j]
return totalIncrease4. Max Increase to Keep City Skyline solution in JavaScript Try on Compiler
class Solution {
maxIncreaseKeepingSkyline(grid) {
const numRows = grid.length;
const numCols = grid[0].length;
// Arrays for max row and column heights
const maxRowHeights = Array(numRows).fill(0);
const maxColHeights = Array(numCols).fill(0);
// Compute max heights
for (let i = 0; i < numRows; i++) {
for (let j = 0; j < numCols; j++) {
maxRowHeights[i] = Math.max(maxRowHeights[i], grid[i][j]);
maxColHeights[j] = Math.max(maxColHeights[j], grid[i][j]);
}
}
let totalIncrease = 0;
// Calculate total possible increase
for (let i = 0; i < numRows; i++) {
for (let j = 0; j < numCols; j++) {
const newHeight = Math.min(maxRowHeights[i], maxColHeights[j]);
totalIncrease += newHeight - grid[i][j];
}
}
return totalIncrease;
}
}Max Increase to Keep City Skyline Complexity Analysis
Time Complexity: O(n × m)
Let n = numRows, m = numCols.
Computing max in each row and column
Loops through the entire grid: O(n × m)
Computing total possible increase
Another pass through the grid: O(n × m)
Total Time Complexity: O(n × m)
Space Complexity: O(n+m)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
- maxRowHeights: vector of size n → O(n)
- maxColHeights: vector of size m → O(m)
- Temporary loop variables and totalIncrease: O(1)
Auxiliary Space Complexity: O(n + m)
Total Space Complexity
- Input Grid: vector<vector<int>> grid of size n × m → O(n × m)
- Auxiliary Arrays: O(n + m) (from above)
Total Space Complexity: O(n × m + n + m)
Which simplifies to: O(n × m)
Similar Problems
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Consider a rat placed at position (0, 0) in an n x n square matrix mat. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).
The matrix contains only two possible values:
- 0: A blocked cell through which the rat cannot travel.
- 1: A free cell that the rat can pass through.