Solution Explanation: 807. Max Increase to Keep City Skyline

This problem asks to find the maximum total sum of height increases for buildings in an n x n grid without changing the skyline from any direction (north, east, south, west). The skyline is determined by the maximum height in each row and column.

Approach: A greedy approach is optimal here. The key insight is that for each building, the maximum possible increase in height is limited by the maximum height in its row and the maximum height in its column. We can't increase a building's height beyond either of these constraints without altering the skyline.

Algorithm:

1. Find Row and Column Maximums: Iterate through the grid to find the maximum height in each row and each column. Store these maximums in separate arrays (rowMax and colMax).

2. Calculate Maximum Increase for Each Building: For each building grid[i][j], calculate the maximum possible increase: min(rowMax[i], colMax[j]) - grid[i][j]. This represents how much the building's height can be increased without affecting the skyline.

3. Sum the Increases: Sum up the maximum possible increases for all buildings to get the final answer.

Time Complexity Analysis:

• Finding row and column maximums: O(n²) - We iterate through the n x n grid once.
• Calculating maximum increases and summing them: O(n²) - We iterate through the grid again.

Therefore, the overall time complexity is O(n²).

Space Complexity Analysis:

We use two arrays, rowMax and colMax, each of size n to store the maximum heights. The space complexity is thus O(n).

Code Examples (with detailed explanations):

Python:

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)  # Get the size of the grid (assuming it's square)
        row_max = [max(row) for row in grid] #List Comprehension for row max
        col_max = [max(col) for col in zip(*grid)] #zip(*grid) transposes the grid for column max
        total_increase = 0
        for i in range(n):
            for j in range(n):
                max_increase = min(row_max[i], col_max[j]) - grid[i][j] #Find max increase for current building
                total_increase += max_increase #Add to total
        return total_increase
 

Java:

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int[] rowMax = new int[n];
        int[] colMax = new int[n];
 
        // Find row and column maximums
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }
 
        int totalIncrease = 0;
        // Calculate and sum increases
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalIncrease += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }
        return totalIncrease;
    }
}

The C++, Go, and TypeScript code would follow a very similar structure to the Python and Java examples, just with different syntax. The core logic remains the same. The key is understanding the greedy approach and how to efficiently find the row and column maximums.