algoadvance

You are given an n x n grid representing the heights of buildings in a city. The grid is sent as a list of lists. The height of the building at row i and column j is grid[i][j].

You are allowed to increase the height of any building, but keeping in mind the following constraints for each building:

  1. The new height of any building cannot exceed the maximum height of any building in the same row.
  2. The new height of any building cannot exceed the maximum height of any building in the same column.

You need to find the maximum total sum of the heights that the buildings can be increased.

Example

Input:

grid = [
  [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0]
]

Output:

35

Explanation:

[
  [8, 4, 8, 7],
  [7, 4, 7, 7],
  [9, 4, 8, 7],
  [3, 3, 3, 3]
]

(8-3) + (4-0) + (8-8) + (7-4) +
(7-2) + (4-4) + (7-5) + (7-7) +
(9-9) + (4-2) + (8-6) + (7-3) +
(3-0) + (3-3) + (3-1) + (3-0) = 35

Clarifying Questions

  1. Are all the heights non-negative integers?
  2. Is the grid guaranteed to be a square matrix (i.e., n x n)?
  3. Are there any constraints on the value of n?

Strategy

  1. Calculate the maximum heights for each row (max_row).
  2. Calculate the maximum heights for each column (max_col).
  3. Iterate through the grid and determine the maximum height that the building can be increased to for each cell. This will be the minimum of the maximum heights of the corresponding row and column.
  4. Calculate the sum of the allowed increases.

Code

def maxIncreaseKeepingSkyline(grid):
    n = len(grid)
    
    # Step 1: Calculate maximum heights of each row
    max_row = [max(row) for row in grid]
    
    # Step 2: Calculate maximum heights of each column
    max_col = [max(grid[i][j] for i in range(n)) for j in range(n)]
    
    total_increase = 0
    
    # Step 3 and 4: Calculate the total increase
    for i in range(n):
        for j in range(n):
            # Find the minimum of max_row and max_col values for the current cell
            max_height = min(max_row[i], max_col[j])
            total_increase += max_height - grid[i][j]
    
    return total_increase

# Example usage
grid = [
  [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0]
]
print(maxIncreaseKeepingSkyline(grid))  # Output: 35

Time Complexity

The time complexity of the solution is:

  1. O(n^2) for calculating maximum heights for each row.
  2. O(n^2) for calculating maximum heights for each column.
  3. O(n^2) for iterating through the grid and calculating the total increase.

Thus, the overall time complexity is O(n^2).

Try our interview co-pilot at AlgoAdvance.com