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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Increase to Keep City Skyline

Number: 825

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an n x n grid where each cell represents the height of a building, determine the maximum total sum by which the building heights can be increased without changing the city’s skyline from any cardinal direction (i.e., the maximum values in each row and each column remain the same).

Key Insights

  • The skyline from the left/right is determined by the maximum value in each row.
  • The skyline from the top/bottom is determined by the maximum value in each column.
  • Each building at position (i, j) can be increased to at most the minimum of the maximum value in its row and the maximum value in its column.
  • The optimal increase for a building is given by: allowed height (min(row_max, col_max)) - current height.

Space and Time Complexity

Time Complexity: O(n²) since we iterate through the grid multiple times. Space Complexity: O(n) used to store the row and column maximums.

Solution

The solution first involves calculating the maximum values for each row and each column. Then, for every building in the grid, determine the maximum height it can be raised to by taking the minimum of its row maximum and column maximum. The increase is the difference between this allowed height and the current height. Summing these increases gives the answer.

Data Structures:

  • Two arrays (or lists) to store maximum values for rows and columns.

Algorithm:

  1. Traverse the grid to compute the maximum for each row.
  2. Traverse the grid to compute the maximum for each column.
  3. Iterate over each cell in the grid and compute the allowed increase, which is the difference between the minimum of the corresponding row and column maximums and the current cell value.
  4. Sum these differences to get the total increase.

The key insight is ensuring the skyline is maintained by not exceeding the precomputed maximum values for any row or column.

Code Solutions

# Function to calculate maximum increase keeping city skyline unchanged
def maxIncreaseKeepingSkyline(grid):
    # Get the number of rows (and columns, since grid is square)
    n = len(grid)
    
    # Compute the maximum value for each row
    row_max = [max(row) for row in grid]
    
    # Compute the maximum value for each column
    col_max = [max(grid[i][j] for i in range(n)) for j in range(n)]
    
    total_increase = 0
    # Traverse each cell in the grid
    for i in range(n):
        for j in range(n):
            # Determine allowed height: minimum of the corresponding row and column maximums
            allowed_height = min(row_max[i], col_max[j])
            # Increase is the difference between allowed height and current height
            increase = allowed_height - grid[i][j]
            total_increase += increase
    return total_increase

# Example usage:
# print(maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]))  # Expected output: 35
← Back to All Questions