Solution
The skyline from top/bottom is the maximum of each column and the skyline from left/right is the maximum of each row. So an element grid[i][j] can be increased until it reaches the maximum of row i or column j. So grid[i][j] = min(max(row i), max(column j));.
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int s = grid.size();
int maxLens[2][s];
// maxLens[0][i] stores maximum for each row i
// maxLens[1][j] stores maximum for each column j
// initialise maxLens
for (int i=0; i<2; i++)
for (int j=0; j<s; j++)
maxLens[i][j] = 0;
// store maximum for each row/column
for (int i=0; i<s; i++)
for (int j=0; j<s; j++) {
maxLens[0][i] = max(maxLens[0][i], grid[i][j]);
maxLens[1][j] = max(maxLens[1][j], grid[i][j]);
}
int ans = 0;
for (int i=0; i<s; i++)
for (int j=0; j<s; j++) {
ans += min(maxLens[0][i], maxLens[1][j])-grid[i][j];
}
return ans;
}
Time complexity: O(n^2)
Space complexity: O(n)