Sponsored
This approach involves calculating the maximum possible heights for each building in the grid so that the skyline remains unchanged. To achieve this, determine the maximum heights seen from the north/south (for each column) and from the west/east (for each row). For each building, the new maximum height is the minimum of these two values. This way, the skyline's constraints are not violated.
Once you compute the possible maximum height for each building, the sum of differences between these new heights and the original heights will yield the maximum total sum that the heights can be increased by.
Time Complexity: O(n^2) where n is the number of rows (or columns) in the grid since we must iterate over the entire grid at least twice (once for calculating maxRow and maxCol, and once for computing the total increase).
Space Complexity: O(n), as additional space for storing the skyline views of rows and columns is required.
1def maxIncreaseKeepingSkyline(grid):
2 n = len(grid)
3 row_max = [max(row) for row in grid]
4 col_max = [max
In this Python solution, the maximum heights for each row and column are calculated using list comprehensions, with the zip function being used to transpose the grid for column operations. By comparing these maximum values for each position in the grid, the code efficiently computes how much each building height can be increased.