Max Increase to Keep City Skyline

Medium

Asked by:

10 views

Topics:

ArraysGreedy Algorithms

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

Try coding it in LeetCode

Max Increase to Keep City Skyline

Medium

Asked by:

10 views

Topics:

ArraysGreedy Algorithms

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `grid` (number of rows and columns)?
Can the values in the `grid` be negative or zero? What is the maximum value of any cell?
If the increase is not possible (i.e., all buildings are already at the maximum possible height allowed by the skyline), should I return 0?
Are all rows guaranteed to have the same number of columns (i.e., is it a valid rectangular grid)?
Is the input `grid` guaranteed to be non-empty?

Brute Force Solution

Approach

The problem asks us to increase the height of buildings in a city while maintaining the city's skyline from all four directions. A brute-force approach would be to try every possible height increase for each building, within the constraints of the skyline.

Here's how the algorithm would work step-by-step:

Consider each building in the city, one at a time.
For each building, explore every possible increase in height, starting from zero increase.
After each increase, check if the new height violates the skyline when viewed from the north, south, east, and west directions.
If increasing the height violates any skyline rule, try a smaller increase or no increase at all for that building.
If the increase does NOT violate the skyline, calculate how much the total increase across all buildings is with this change.
Repeat this process for every building to find the combination of height increases that gives the maximum total increase without messing up the skyline.

Code Implementation

def max_increase_to_keep_city_skyline_brute_force(grid):
    city_size = len(grid)
    max_total_increase = 0

    for building_row in range(city_size):
        for building_col in range(city_size):
            original_height = grid[building_row][building_col]
            
            for potential_increase in range(city_size * city_size): #try every height
                new_height = original_height + potential_increase
                
                # Check if the new height violates skyline constraints.
                is_valid = True
                
                # Check north/south skyline
                max_north_south = 0
                for i in range(city_size):
                    max_north_south = max(max_north_south, grid[i][building_col] if i != building_row else new_height)

                for i in range(city_size):
                    if i != building_row and grid[i][building_col] > new_height and max_north_south != new_height:
                        is_valid = False
                        break

                # Check east/west skyline
                max_east_west = 0
                for j in range(city_size):
                    max_east_west = max(max_east_west, grid[building_row][j] if j != building_col else new_height)

                for j in range(city_size):
                    if j != building_col and grid[building_row][j] > new_height and max_east_west != new_height:
                        is_valid = False
                        break

                if is_valid:
                    #If valid, calculate the total increase
                    total_increase = 0
                    temp_grid = [row[:] for row in grid] #create a temporary grid
                    temp_grid[building_row][building_col] = new_height

                    for row in range(city_size):
                        for col in range(city_size):
                            total_increase += (temp_grid[row][col] - grid[row][col])

                    max_total_increase = max(max_total_increase, total_increase)
                else:
                    break # if not valid, move to next building

    return max_total_increase

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each of the n*n buildings in the grid. For each building, it tries increasing its height, potentially up to a maximum that depends on the grid size, but we can consider it bounded by n in the worst case for simplicity. After each potential height increase, it checks all n rows and n columns to verify the skyline constraint. Therefore, for each building, we are doing O(n) work (checking the skyline) potentially n times (trying different height increases). This gives us an overall time complexity of O(n*n * n), which simplifies to O(n^3).

Space Complexity

O(1) – The described brute-force approach iterates through buildings and possible height increases. While it calculates the total increase and checks skyline validity, it doesn't explicitly use any auxiliary data structures like lists, hash maps, or trees to store intermediate results or track visited states. It re-calculates skyline validity each time. Therefore, the auxiliary space remains constant, independent of the input grid's size.

Optimal Solution

Approach

The goal is to increase the height of buildings in a city grid without changing the skyline. The optimal strategy involves finding the tallest building in each row and column, and then increasing each building's height up to the minimum of its row's tallest and its column's tallest.

Here's how the algorithm would work step-by-step:

First, find the highest building in each row of the city.
Next, find the highest building in each column of the city.
Now, for each building in the city, determine the maximum height it can be increased to without changing the skyline. This height will be the smaller of the tallest building in its row and the tallest building in its column.
If the building's current height is less than this maximum allowable height, calculate the difference, which is the amount we can increase the building's height by.
Sum up all these increases to find the total maximum increase possible for the city while maintaining the skyline.

Code Implementation

def max_increase_keeping_skyline(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    # Find the tallest building in each row.
    tallest_in_each_row = [max(row) for row in grid]

    # Find the tallest building in each column.
    tallest_in_each_column = [max(grid[i][j] for i in range(number_of_rows)) for j in range(number_of_columns)]

    total_increase = 0
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            # Determine the maximum allowable height.
            max_allowable_height = min(tallest_in_each_row[row_index], tallest_in_each_column[column_index])

            if grid[row_index][column_index] < max_allowable_height:
                total_increase += max_allowable_height - grid[row_index][column_index]

    return total_increase

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first finds the maximum height in each of the n rows, requiring O(n²) operations to traverse the entire grid. Similarly, finding the maximum height in each of the n columns also takes O(n²) time. Finally, iterating through each building (n x n) to calculate the potential increase involves another O(n²) operation. Therefore, the overall time complexity is dominated by the grid traversals, summing up to O(n² + n² + n²), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm uses two arrays, rowMax and colMax, to store the maximum height of buildings in each row and column, respectively. For an N x N grid, rowMax and colMax will each have a size of N. Therefore, the auxiliary space required is proportional to the size of a single dimension of the input grid, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or empty, as no increase is possible.
Grid with only one row/column	Calculate the maximum value in the row/column and compute the increase for each cell.
Grid with all identical values	All cells can be increased to the identical value, resulting in a total increase equal to the number of cells times 0.
Large grid with large integer values	Ensure calculations (especially when summing increases) do not cause integer overflow and use appropriate data types.
Grid with negative numbers	The problem statement implicitly implies non-negative values, but if negative values are allowed, the skyline calculation must correctly handle them by finding min values in rows/cols instead of max.
Grid where all cells are already at the maximum possible value for their row and column	The increase for all cells will be 0, thus returning 0.
Non-square grid (m x n, m != n)	Ensure the skyline calculation correctly handles the different dimensions when calculating the maximum values for rows and columns.
Grid with very large dimensions approaching memory limits	Algorithm should have a low memory footprint, accessing elements iteratively to avoid loading the entire grid into memory if possible.

Null or empty grid

How to Handle:

Return 0 if the grid is null or empty, as no increase is possible.

Grid with only one row/column

How to Handle:

Calculate the maximum value in the row/column and compute the increase for each cell.

Grid with all identical values

How to Handle:

All cells can be increased to the identical value, resulting in a total increase equal to the number of cells times 0.

Large grid with large integer values

How to Handle:

Ensure calculations (especially when summing increases) do not cause integer overflow and use appropriate data types.

Grid with negative numbers

How to Handle:

The problem statement implicitly implies non-negative values, but if negative values are allowed, the skyline calculation must correctly handle them by finding min values in rows/cols instead of max.

Grid where all cells are already at the maximum possible value for their row and column

How to Handle:

The increase for all cells will be 0, thus returning 0.

Non-square grid (m x n, m != n)

How to Handle:

Ensure the skyline calculation correctly handles the different dimensions when calculating the maximum values for rows and columns.

Grid with very large dimensions approaching memory limits

How to Handle:

Algorithm should have a low memory footprint, accessing elements iteratively to avoid loading the entire grid into memory if possible.