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 <vector>
2#include <algorithm>
3using namespace std;
4
5int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
6 int n = grid.size();
7 vector<int> rowMax(n, 0);
8 vector<int> colMax(n, 0);
9
10 for (int i = 0; i < n; ++i) {
11 for (int j = 0; j < n; ++j) {
12 rowMax[i] = max(rowMax[i], grid[i][j]);
13 colMax[j] = max(colMax[j], grid[i][j]);
14 }
}
int increase = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
increase += min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return increase;
}
This C++ solution follows the same logic. It uses vectors to store the maximum heights seen from each row and column. By iterating over the grid twice, once to fill the max heights and another to compute the allowed heights, it calculates the total possible height increases for the grid buildings.