We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Increase to Keep City Skyline

Difficulty: Medium

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

Key Insights

  • The maximum height to which a building can be increased is determined by the minimum height of the tallest building in its respective row and column.
  • We can compute the maximum possible heights for each building by finding the maximum height in each row and the maximum height in each column.
  • The total increase in height for the buildings is the sum of the differences between the new maximum heights and the original heights.

Space and Time Complexity

Time Complexity: O(n^2) - We need to iterate through the grid to find maximum heights for rows and columns, and then again to calculate the total increase. Space Complexity: O(n) - We need additional arrays to store the maximum heights for rows and columns.

Solution

To solve this problem, we will:

  1. Iterate through the grid to determine the maximum height of buildings in each row and each column.
  2. For each building, calculate the maximum height it can be increased to, which is the minimum of its respective row and column maximum heights.
  3. Compute the total increase by summing the differences between the new maximum height and the original height for all buildings.

We will use two arrays to store the maximum heights for rows and columns.

Code Solutions

def maxIncreaseKeepingSkyline(grid):
    n = len(grid)
    row_max = [0] * n
    col_max = [0] * n

    # Calculate the maximum heights for each row and column
    for r in range(n):
        for c in range(n):
            row_max[r] = max(row_max[r], grid[r][c])
            col_max[c] = max(col_max[c], grid[r][c])

    total_increase = 0
    # Calculate the total increase
    for r in range(n):
        for c in range(n):
            total_increase += min(row_max[r], col_max[c]) - grid[r][c]

    return total_increase
← Back to All Questions