807. Max Increase to Keep City Skyline
Problem Description
In the given problem, we have a simulated city that's made up of n x n
blocks, and each block contains a building. The grid
matrix provided as input indicates the heights of these buildings, with each cell grid[r][c]
showing the height of the building at the r
row and c
column. The city's skyline is the outer contour of buildings when they are viewed from far away in any of the cardinal (North, East, South, West) directions. What we need to determine is the maximum height we can add to each of the buildings without changing the skyline from any direction. The question asks for the total sum of the heights that we could add to these buildings.
Understanding the problem involves realizing that:
- We can increase the height of any building.
- The increase in height for each building may be different.
- The skyline must not be altered by these height increases.
The key idea here is that the skyline is determined by the tallest buildings in each row when viewing from the East or West, and in each column when viewed from the North or South.
Intuition
To arrive at the solution:
-
We first determine what the current skyline looks like from each direction. For the North/South view, we need the maximum heights in each column, and for the East/West perspective, we need the maximum heights in each row.
-
The key insight is that the maximum height to which a particular building can be increased without altering the skyline is the minimum of the maximums of its row and column.
-
For each building, we calculate this potential increase by taking the minimum of the two maximum heights (of the row and column it's in) and subtracting the current height of the building. This is how we abide by the condition of not changing the skyline after increasing the building's height.
-
By summing these potential increases for each building, we get the total sum that the heights of buildings can be increased by without affecting the skyline.
In terms of implementation:
- First,
rmx
stores the maximum height for each row whilecmx
stores the maximum heights for each column, which are the skylines when looking from East/West and North/South respectively. - Then, we iterate over each cell in the grid, and for each building, calculate the potential increase as the difference between the smaller of the two maximum heights (
min(rmx[i], cmx[j])
) and the current height (grid[i][j]
). - The
sum()
function accumulates these positive differences to provide the answer: the total sum of height increases across the grid.
Learn more about Greedy patterns.
Solution Approach
The implementation of the solution utilizes a simple yet efficient approach combining elements of array manipulation and mathematics.
Here's a step-by-step breakdown of the implementation:
-
Calculate Row Maxima (
rmx
):- We iterate through each row of the
grid
matrix to find the maximum height of the buildings in each row. - The built-in
max()
function applied to each row results in a list of the tallest building per row, which represents the East/West skyline. - This list is stored in the variable
rmx
.
- We iterate through each row of the
-
Calculate Column Maxima (
cmx
):- We use the
zip(*grid)
function to transpose the originalgrid
matrix. This effectively converts the columns into rows for easy traversal. - Applying the
max()
function on the transposed grid gives us the maximum heights for each column, which presents the North/South skyline. - The resulting maximum values for each column are stored in the variable
cmx
.
- We use the
-
Evaluate the Height Increase Limit:
- The solution utilizes a nested for-loop to iterate through each cell in the
grid
. For each cell located at(i, j)
, it calculates the minimum height that can be achieved between the maximum heights of the row and column which the cell belongs to, usingmin(rmx[i], cmx[j])
. - It subtracts the current building height
grid[i][j]
from this minimum value to find the possible height increase without changing the skyline. This calculation is in direct correlation with the mathematical definition of the problem statement.
- The solution utilizes a nested for-loop to iterate through each cell in the
-
Summing the Results:
- Each of these height increase values for the individual buildings are added together using the
sum()
function. The addition is done through a generator expression which runs through each cell coordinate(i, j)
and applies the previous step's logic. - This sum is the maximum total sum that building heights can be increased without affecting the city's skyline from any cardinal direction.
- Each of these height increase values for the individual buildings are added together using the
The algorithm's essence is in leveraging the minimum of the maximum heights of rows and columns to find the optimal height increase for each building. A crucial factor is that the algorithm runs in O(n^2)
time complexity, where n
is the dimension of the input matrix, making it suitable for reasonably large values of n
. No additional space is used besides the two arrays storing maxima of rows and columns, resulting in O(n)
space complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example with a 3 x 3
grid, represented by the matrix:
1grid = [ 2 [3, 0, 8], 3 [4, 5, 7], 4 [9, 2, 6] 5]
Following the steps outlined in the solution approach:
-
Calculate Row Maxima (
rmx
):We look for the tallest building in each row (East/West skyline):
- Row 0: max is 8.
- Row 1: max is 7.
- Row 2: max is 9.
So,
rmx = [8, 7, 9]
. -
Calculate Column Maxima (
cmx
):By transposing the
grid
and finding the tallest building in each column (North/South skyline):- Column 0: max is 9 (from transposed grid row 0).
- Column 1: max is 5 (from transposed grid row 1).
- Column 2: max is 8 (from transposed grid row 2).
Hence,
cmx = [9, 5, 8]
. -
Evaluate the Height Increase Limit:
We iterate over the grid and for each cell
(i, j)
, we find the minimum of the maximum height of the ith row and jth column (min(rmx[i], cmx[j])
) to determine the limit to which we can raise each building:At
grid[0][0]
(3
):- Minimum of row max and column max is
min(8, 9) = 8
. - Maximum height increase:
8 - 3 = 5
.
At
grid[0][1]
(0
):- Minimum of row max and column max is
min(8, 5) = 5
. - Maximum height increase:
5 - 0 = 5
.
And so on for the other buildings.
- Minimum of row max and column max is
-
Summing the Results:
We sum up the calculated increases for each building to get the total height increase without changing the skyline:
grid[0][0]
: 5 +grid[0][1]
: 5 +grid[0][2]
: 0 (since 8 - 8 = 0, no increase needed) +grid[1][0]
: 2 +grid[1][1]
: 0 (since 7 - 7 = 0, no increase needed) +grid[1][2]
: 0 (since 7 - 7 = 0, no increase needed) +grid[2][0]
: 0 (since 9 - 9 = 0, no increase needed) +grid[2][1]
: 3 +grid[2][2]
: 2= 5 + 5 + 0 + 2 + 0 + 0 + 0 + 3 + 2
= 17
So according to the algorithm, the maximum total sum that building heights can be increased by, without affecting the city's skyline from any cardinal direction, is 17.
Solution Implementation
1class Solution:
2 def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
3 # Find the maximum heights in each row (the row skylines)
4 max_height_in_row = [max(row) for row in grid]
5
6 # Find the maximum heights in each column (the column skylines)
7 # We do this by using zip to iterate over columns instead of rows
8 max_height_in_column = [max(column) for column in zip(*grid)]
9
10 # Calculate the sum of the possible height increase for each building
11 # without exceeding the row and column skylines.
12 total_increase = sum(
13 min(max_height_in_row[i], max_height_in_column[j]) - grid[i][j]
14 for i in range(len(grid))
15 for j in range(len(grid[0]))
16 )
17
18 # Return the total possible increase sum.
19 return total_increase
20
1class Solution {
2
3 public int maxIncreaseKeepingSkyline(int[][] grid) {
4 // Get the number of rows and columns of the grid.
5 int numRows = grid.length;
6 int numCols = grid[0].length;
7
8 // Initialize arrays to store the max height of the skyline
9 // for each row (maxRowHeights) and column (maxColHeights).
10 int[] maxRowHeights = new int[numRows];
11 int[] maxColHeights = new int[numCols];
12
13 // Compute the max height for each row and column.
14 for (int row = 0; row < numRows; ++row) {
15 for (int col = 0; col < numCols; ++col) {
16 maxRowHeights[row] = Math.max(maxRowHeights[row], grid[row][col]);
17 maxColHeights[col] = Math.max(maxColHeights[col], grid[row][col]);
18 }
19 }
20
21 // Initialize a variable to keep track of the total increase in height.
22 int totalIncrease = 0;
23
24 // Calculate the maximum possible increase for each building
25 // while keeping the skyline unchanged.
26 for (int row = 0; row < numRows; ++row) {
27 for (int col = 0; col < numCols; ++col) {
28 // The new height is the minimum of the max heights of the
29 // current row and column.
30 int newHeight = Math.min(maxRowHeights[row], maxColHeights[col]);
31 // Increase by the difference between the new height and the original height.
32 totalIncrease += newHeight - grid[row][col];
33 }
34 }
35
36 // Return the total increase in the height of the buildings.
37 return totalIncrease;
38 }
39}
40
1#include <vector>
2#include <algorithm> // Required for std::max and std::min functions
3
4class Solution {
5public:
6 int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
7 // Determine the number of rows and columns in the grid
8 int rowCount = grid.size(), colCount = grid[0].size();
9
10 // Create vectors to store the max values for each row and column
11 vector<int> rowMax(rowCount, 0);
12 vector<int> colMax(colCount, 0);
13
14 // Iterate through the grid to find the max values for each row and column
15 for (int i = 0; i < rowCount; ++i) {
16 for (int j = 0; j < colCount; ++j) {
17 // Update the maximum in the current row
18 rowMax[i] = std::max(rowMax[i], grid[i][j]);
19 // Update the maximum in the current column
20 colMax[j] = std::max(colMax[j], grid[i][j]);
21 }
22 }
23
24 // Initialize the answer variable to accumulate the total increase in height
25 int totalIncrease = 0;
26
27 // Iterate through the grid to compute the maximum possible increase
28 // while maintaining the skylines
29 for (int i = 0; i < rowCount; ++i) {
30 for (int j = 0; j < colCount; ++j) {
31 // The increase is the smaller of the two max values for the
32 // current row and column minus the current grid height
33 totalIncrease += std::min(rowMax[i], colMax[j]) - grid[i][j];
34 }
35 }
36
37 // Return the total possible increase in height for the buildings
38 return totalIncrease;
39 }
40};
41
1function maxIncreaseKeepingSkyline(grid: number[][]): number {
2 // Create an array to store the maximum height in each row.
3 let rowMaxes = grid.map(row => Math.max(...row));
4
5 // Create an array to store the maximum height in each column.
6 let colMaxes = new Array(grid[0].length).fill(0).map((_, colIndex) =>
7 Math.max(...grid.map(row => row[colIndex]))
8 );
9
10 // Initialize a variable to keep track of the total increase in height.
11 let totalIncrease = 0;
12
13 // Calculate the maximum increase in height for each building while
14 // keeping the skyline from changing.
15 for (let rowIndex = 0; rowIndex < grid.length; rowIndex++) {
16 for (let colIndex = 0; colIndex < grid[0].length; colIndex++) {
17 // Find the minimum of the maximum heights of the current row and column.
18 let limitHeight = Math.min(rowMaxes[rowIndex], colMaxes[colIndex]);
19
20 // Increase the total height by the difference between the limit height and the current building's height.
21 totalIncrease += limitHeight - grid[rowIndex][colIndex];
22 }
23 }
24
25 // Return the total increase in height.
26 return totalIncrease;
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the code can be broken down into two parts:
-
Calculating the maximum value for each row and column:
- We iterate through each row with
max(row)
which takesO(N)
time for each row, whereN
is the number of columns. This is done for each of theM
rows, resulting inO(M*N)
time. - Similarly, zipping (
zip(*grid)
) the columns takesO(M*N)
because it iterates through all elements, and computing max for each column isO(M)
, which is also done forN
columns. This does not increase the total time complexity, so it remainsO(M*N)
.
- We iterate through each row with
-
Calculating the increment for each building (sum):
- The double for loop iterates over all elements of the matrix, which is
M*N
operations. Within each operation, we perform a constant-time calculation (min(rmx[i], cmx[j]) - grid[i][j]
). Hence, this part is alsoO(M*N)
.
- The double for loop iterates over all elements of the matrix, which is
Since both steps are O(M*N)
and they are performed sequentially, the total time complexity of the function is O(M*N)
.
Space Complexity
The space complexity is determined by the additional space used besides the input grid:
- The space to store maximums of rows (
rmx
) isO(M)
. - The space for maximums of columns (
cmx
) isO(N)
.
Here, M is the number of rows and N is the number of columns in the grid. Thus, the total additional space used is O(M + N)
.
Therefore, the overall space complexity is O(M + N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first