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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize) {
This C solution first computes the maximum height seen from each row and column and stores them in two arrays, maxRow and maxCol. Then, it iterates over each building position in the grid to calculate the new possible height by taking the minimum value between the corresponding values in maxRow and maxCol. The potential increase for each building is accumulated to give the total maximum increase possible without altering the skyline.