Max Increase to Keep City Skyline

Problem Statement

In the problem, we're dealing with a city layout represented by an n x n matrix where each entry (r, c) in the matrix grid denotes the height of a building located in the r-th row and c-th column. Each building is visualized like a vertical square prism, and the city's skyline, as viewed from north, south, east, and west directions, is simply the highest silhouette formed by these buildings.

The objective here is to maximize the sum of increments to the heights of the buildings such that the city's skyline when viewed from each of these four cardinal directions remains unaltered i.e., the tallest buildings as viewed from each direction do not get overshadowed by an increase in height of neighboring buildings. By analyzing how much each building’s height can be safely increased without altering the skyline, we can determine the maximum sum of all these possible increments.

Examples

Example 1

Input:

grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output:

35

Explanation:

The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]

Example 2

Input:

grid = [[0,0,0],[0,0,0],[0,0,0]]

Output:

0

Explanation:

Increasing the height of any building will result in the skyline changing.

Constraints

• n == grid.length
• n == grid[r].length
• 2 <= n <= 50
• 0 <= grid[r][c] <= 100

Approach and Intuition

To solve the task, the general strategy involves:

1. Identify the maximum heights seen from each row (viewed from east or west) and each column (viewed from north or south).
2. For each matrix cell (r, c), determine how much the height of the building can be increased without affecting the skyline:
   • The potential increase for a building in cell (r, c) is limited either by the maximum height of any building in its row or its column — specifically, it is the smaller value between the maximum height of row r and the maximum height of column c.
   • However, to preserve the skyline, the new height after increment (current building height plus increment) at (r, c) should not exceed the aforementioned smaller value.
   • Therefore, the height increment will be the difference between this limit (smaller max height between corresponding row and column) and the building's current height.
3. Summing across all possible increments will yield the maximum total sum of increases without changing the city's skyline.

The described plan ensures that all operations are checked against the constraints:

• Matrix dimensions satisfy 2 <= n <= 50.
• Each building's height varies between 0 and 100.

These steps are corroborated by the provided examples, which help elucidate how calculations are performed based on the matrix grid values and their respective impact on the city's skylines from all directions.

Solutions

class Solution {
    public int maxIncrease(int[][] buildings) {
        int size = buildings.length;
        int[] maxRow = new int[size];
        int[] maxCol = new int[size];

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

        int totalIncrease = 0;
        for (int row = 0; row < size; ++row)
            for (int col = 0; col < size; ++col)
                totalIncrease += Math.min(maxRow[row], maxCol[col]) - buildings[row][col];

        return totalIncrease;
    }
}