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.
1public class Solution {
2 public int MaxIncreaseKeepingSkyline(int[][] grid) {
3 int n = grid.Length;
4 int[] rowMax = new int[n];
5 int[] colMax = new int[n];
6
7 for (int i = 0; i < n; i++) {
8 for (int j = 0; j < n; j++) {
9 rowMax[i] = Math.Max(rowMax[i], grid[i][j]);
10 colMax[j] = Math.Max(colMax[j], grid[i][j]);
11 }
12 }
13
14 int increase = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
increase += Math.Min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return increase;
}
}
The C# solution is essentially similar to its C++ and Java counterparts. It uses arrays to store row and column maximums, iterating over the grid to ascertain the maximum permissible incremental increase for each building height.