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
The Java solution implements the same logic as C and C++. It employs arrays to keep track of the maximum heights of each row and column. It processes the grid in O(n^2) to determine the overall max increase possible for the building heights.