Intuition

To maximize the total increase in building heights while maintaining the city skyline, we can observe that: - Each row has a maximum height that determines its skyline when viewed from the left or right. - Each column has a maximum height that determines its skyline when viewed from the top or bottom. The height of any building can be increased to the minimum of the maximum height in its row and column.

Approach

1. Calculate Maximum Heights:
2. Traverse the grid to find the maximum height for each row (maxRow) and each column (maxCol).
3. Calculate Total Increase:
4. For each building, calculate the potential increase as min(maxRow[row], maxCol[col]) - grid[row][col], ensuring the skyline constraints are maintained.
5. Sum the Increases:
6. Accumulate the height increases for all buildings into the result.

Complexity

• Time complexity: O(N²), where N is the dimension of the grid. This includes:
• O(N²) to compute maxRow and maxCol.

• O(N²) to compute the total increase.

• Space complexity: O(N), for storing the maxRow and maxCol arrays.

Code

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int N = grid.length;
        int[] maxRow = new int[N];
        int[] maxCol = new int[N];

        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                maxRow[row] = Math.max(maxRow[row], grid[row][col]);
            }
        }

        for (int col = 0; col < N; col++) {
            for (int row = 0; row < N; row++) {
                maxCol[col] = Math.max(maxCol[col], grid[row][col]);
            }
        }

        int result = 0;

        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (grid[row][col] < maxRow[row] && grid[row][col] < maxCol[col]) {
                    result += Math.min(maxRow[row], maxCol[col]) - grid[row][col];
                }
            }
        }

        return result;
    }
}