Code Implementation

class Solution:
    def maxIncreaseKeepingSkyline(self, grid):
        n = len(grid)
        max_row = [max(row) for row in grid]
        max_col = [max(grid[i][j] for i in range(n)) for j in range(n)]
        increase = 0
        for i in range(n):
            for j in range(n):
                increase += min(max_row[i], max_col[j]) - grid[i][j]
        return increase
      

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> maxRow(n, 0), maxCol(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                maxRow[i] = max(maxRow[i], grid[i][j]);
                maxCol[j] = max(maxCol[j], grid[i][j]);
            }
        }
        int increase = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                increase += min(maxRow[i], maxCol[j]) - grid[i][j];
            }
        }
        return increase;
    }
};
      

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int[] maxRow = new int[n];
        int[] maxCol = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxRow[i] = Math.max(maxRow[i], grid[i][j]);
                maxCol[j] = Math.max(maxCol[j], grid[i][j]);
            }
        }
        int increase = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                increase += Math.min(maxRow[i], maxCol[j]) - grid[i][j];
            }
        }
        return increase;
    }
}
      

var maxIncreaseKeepingSkyline = function(grid) {
    const n = grid.length;
    const maxRow = Array(n).fill(0);
    const maxCol = Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            maxRow[i] = Math.max(maxRow[i], grid[i][j]);
            maxCol[j] = Math.max(maxCol[j], grid[i][j]);
        }
    }
    let increase = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            increase += Math.min(maxRow[i], maxCol[j]) - grid[i][j];
        }
    }
    return increase;
};
      

Problem Description

You are given a 2D integer array grid representing the heights of buildings in a city, where grid[i][j] is the height of the building located at row i and column j. The city's skyline from the left (row-wise) and from the top (column-wise) must remain unchanged.

Your task is to calculate the maximum total sum by which the height of the buildings can be increased, without changing the city's skyline when viewed from any of the four directions (top, bottom, left, right).

Key constraints:

• You cannot decrease any building's height.
• The skyline from each row and column must remain the same as the original.
• Each building's height can be increased independently, but not above the minimum of its row and column skyline.

Thought Process

At first glance, it might seem that you could simply increase every building to a large value, but the skyline constraint means each row and column must maintain its maximum value.

A brute-force approach would be to try every possible combination of increases, but that's computationally infeasible. Instead, we need to find a pattern or limiting factor for each building.

By observing the problem, we realize that for each building at grid[i][j], the maximum possible height it can reach is limited by the tallest building in its row and the tallest in its column—otherwise, the skyline would change when viewed from that direction.

Therefore, the best we can do for each building is to increase it up to the minimum of its row and column maxima, and sum up all these potential increases.

Solution Approach

We can break down the solution into clear steps:

1. Compute Row Maxima: For each row, find the tallest building. This represents the skyline when viewed from the left or right.
2. Compute Column Maxima: For each column, find the tallest building. This is the skyline from the top or bottom.
3. Calculate Allowed Increases: For each cell grid[i][j], the maximum allowed height is min(max_row[i], max_col[j]). The increase for this cell is min(max_row[i], max_col[j]) - grid[i][j].
4. Sum the Increases: Add up all the individual increases to get the answer.

We use arrays (or lists) to store the row and column maxima for fast lookup, ensuring an efficient solution.

Example Walkthrough

Let's consider the following input:

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

Step 1: Compute row maxima:

• Row 0: max = 8
• Row 1: max = 7
• Row 2: max = 9
• Row 3: max = 3

Step 2: Compute column maxima:

• Col 0: max = 9
• Col 1: max = 4
• Col 2: max = 8
• Col 3: max = 7

Step 3: For each cell, calculate the allowed increase:

• (0,0): min(8,9) - 3 = 5
• (0,1): min(8,4) - 0 = 4
• (0,2): min(8,8) - 8 = 0
• (0,3): min(8,7) - 4 = 3
• (1,0): min(7,9) - 2 = 5
• (1,1): min(7,4) - 4 = 0
• (1,2): min(7,8) - 5 = 2
• (1,3): min(7,7) - 7 = 0
• (2,0): min(9,9) - 9 = 0
• (2,1): min(9,4) - 2 = 2
• (2,2): min(9,8) - 6 = 2
• (2,3): min(9,7) - 3 = 4
• (3,0): min(3,9) - 0 = 3
• (3,1): min(3,4) - 3 = 0
• (3,2): min(3,8) - 1 = 2
• (3,3): min(3,7) - 0 = 3

Step 4: Sum all increases: 5 + 4 + 0 + 3 + 5 + 0 + 2 + 0 + 0 + 2 + 2 + 4 + 3 + 0 + 2 + 3 = 35

So, the answer is 35.

Time and Space Complexity

Brute-force Approach: If we tried every possible increase for every cell, the time complexity would be exponential and infeasible for large grids.

Optimized Approach:

• Time Complexity: O(n²) — We make three passes over the grid: one for row maxima, one for column maxima, and one for summing increases. Each pass is O(n²) for an n x n grid.
• Space Complexity: O(n) — We store two arrays of length n for row and column maxima.

Summary

The key insight is that the maximum allowed height for each building is limited by both its row and column skyline. By calculating these maxima and increasing each building to the minimum of the two, we ensure the skyline remains unchanged. This approach is both elegant and efficient, requiring only a few passes over the grid and simple array operations.

This problem demonstrates the power of breaking down a problem into its constraints and leveraging them for an optimal solution.