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:

  1. 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.

  2. 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.

  3. 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.

  4. 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 while cmx 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. 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.
  2. Calculate Column Maxima (cmx):

    • We use the zip(*grid) function to transpose the original grid 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.
  3. 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, using min(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.
  4. 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example 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:

  1. 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].

  2. 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].

  3. 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.

  4. 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.

Not Sure What to Study? Take the 2-min Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into two parts:

  1. Calculating the maximum value for each row and column:

    • We iterate through each row with max(row) which takes O(N) time for each row, where N is the number of columns. This is done for each of the M rows, resulting in O(M*N) time.
    • Similarly, zipping (zip(*grid)) the columns takes O(M*N) because it iterates through all elements, and computing max for each column is O(M), which is also done for N columns. This does not increase the total time complexity, so it remains O(M*N).
  2. 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 also O(M*N).

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:

  1. The space to store maximums of rows (rmx) is O(M).
  2. The space for maximums of columns (cmx) is O(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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫