# Max Increase to Keep City Skyline
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-increase-to-keep-city-skyline)
Canonical: https://scaleengineer.com/dsa/problems/max-increase-to-keep-city-skyline
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
**Companies:** [Rivian](https://scaleengineer.com/companies/rivian)
---
## Problem
There is a city composed of `n x n` blocks, where each block contains a single building shaped like a vertical square prism. You are given a **0-indexed** `n x n` integer matrix `grid` where `grid[r][c]` represents the **height** of the building located in the block at row `r` and column `c`.

A city's **skyline** is the outer contour formed by all the building when viewing the side of the city from a distance. The **skyline** from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of **any number of buildings by any amount** (the amount can be different per building). The height of a `0`\-height building can also be increased. However, increasing the height of a building should **not** affect the city's **skyline** from any cardinal direction.

Return _the **maximum total sum** that the height of the buildings can be increased by **without** changing the city's **skyline** from any cardinal direction_.

**Example 1:**

![](https://assets.glich.co/dsa/max-increase-to-keep-city-skyline/image0.png) 

**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`

# Approaches
## Brute-Force Approach with Recalculation
This approach iterates through every single building in the grid. For each building, it determines the maximum possible height it can be increased to without affecting the skyline. This is done by finding the maximum height in its corresponding row and column on the fly. The difference between this new maximum allowed height and the building's current height is then added to a running total.
**Time:** O(n^3), where n is the size of the grid. We have two nested loops to iterate through each cell (O(n^2)). Inside these loops, we perform two more loops, each of size n, to find the row and column maximums. This results in a total complexity of O(n^2 * (n + n)) = O(n^3). · **Space:** O(1), as we are not using any extra space that scales with the input size `n`. The variables `rowMax`, `colMax`, and `totalIncrease` use constant space.
**Pros:** Simple to understand and implement.; Very low memory usage.
**Cons:** Highly inefficient due to redundant calculations. The maximum for each row and column is calculated `n` times instead of just once.; Not suitable for larger grids, though it passes for the given constraints (n <= 50).
### Explanation
The core idea is to find the maximum allowed height for each building at `grid[i][j]`. The skyline is defined by the tallest building in each row and each column. Therefore, to not change the skyline, the new height of `grid[i][j]` cannot exceed the height of the tallest building in its row (`rowMax`) or its column (`colMax`). This means the new height must be at most `min(rowMax, colMax)`. To maximize the total increase, we should raise each building's height to this maximum allowed value. The increase for a single building `grid[i][j]` is `min(rowMax, colMax) - grid[i][j]`. This naive approach calculates `rowMax` and `colMax` for each cell `(i, j)` inside the main loop, which leads to redundant calculations.

```java
class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int totalIncrease = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Find max in row i
                int rowMax = 0;
                for (int k = 0; k < n; k++) {
                    rowMax = Math.max(rowMax, grid[i][k]);
                }

                // Find max in column j
                int colMax = 0;
                for (int k = 0; k < n; k++) {
                    colMax = Math.max(colMax, grid[k][j]);
                }

                totalIncrease += Math.min(rowMax, colMax) - grid[i][j];
            }
        }
        return totalIncrease;
    }
}
```
### Algorithm
* Initialize a variable `totalIncrease` to 0.
* Iterate through each row `i` from 0 to `n-1`.
*   Iterate through each column `j` from 0 to `n-1`.
*     Find the maximum height in row `i` (`rowMax`) by iterating through all columns `k`.
*     Find the maximum height in column `j` (`colMax`) by iterating through all rows `k`.
*     Calculate the potential increase: `min(rowMax, colMax) - grid[i][j]`.
*     Add this increase to `totalIncrease`.
* Return `totalIncrease`.

## Optimized Approach with Pre-computation
This approach improves upon the brute-force method by avoiding redundant calculations. It first pre-computes the skyline from all four cardinal directions. The skyline from the left/right is determined by the maximum height in each row, and the skyline from the top/bottom is determined by the maximum height in each column. After storing these maximums in two separate arrays, it iterates through the grid one final time to calculate the total possible increase.
**Time:** O(n^2), where n is the size of the grid. We make two passes over the grid in concept (one for pre-computation, one for summing). The first pass to compute `rowMaxes` and `colMaxes` takes O(n^2). The second pass to calculate the total increase also takes O(n^2). The total time complexity is O(n^2) + O(n^2) = O(n^2). · **Space:** O(n), where n is the size of the grid. We use two arrays, `rowMaxes` and `colMaxes`, each of size `n`, to store the pre-computed maximums. Therefore, the space required is O(n) + O(n) = O(n).
**Pros:** Significantly more efficient than the brute-force approach.; Optimal solution as every cell must be visited at least once, leading to a lower bound of O(n^2) for time complexity.; The logic is clear and follows the problem statement directly.
**Cons:** Uses extra space proportional to the grid dimension `n`, unlike the O(1) space brute-force approach.
### Explanation
The logic remains the same: the maximum height a building at `grid[i][j]` can be increased to is `min(rowMax[i], colMax[j])`. The key optimization is to calculate all row maximums and all column maximums *before* calculating the total increase. We use two arrays, `rowMaxes` and `colMaxes`, of size `n` to store these pre-computed values. This avoids the `O(n)` work inside the main `O(n^2)` loop, bringing the overall time complexity down. The pre-computation of `rowMaxes` and `colMaxes` can be done in a single `O(n^2)` pass.

```java
class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int[] rowMaxes = new int[n];
        int[] colMaxes = new int[n];

        // Pre-compute the maximums for each row and column
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowMaxes[i] = Math.max(rowMaxes[i], grid[i][j]);
                colMaxes[j] = Math.max(colMaxes[j], grid[i][j]);
            }
        }

        int totalIncrease = 0;
        // Iterate through the grid to calculate the total increase
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalIncrease += Math.min(rowMaxes[i], colMaxes[j]) - grid[i][j];
            }
        }

        return totalIncrease;
    }
}
```
### Algorithm
* Get the size of the grid, `n`.
* Create two integer arrays, `rowMaxes` and `colMaxes`, of size `n`, initialized to 0.
* Iterate through the grid with row `i` from 0 to `n-1` and column `j` from 0 to `n-1`:
*   Update `rowMaxes[i] = max(rowMaxes[i], grid[i][j])`.
*   Update `colMaxes[j] = max(colMaxes[j], grid[i][j])`.
* Initialize `totalIncrease` to 0.
* Iterate through the grid again with row `i` and column `j`:
*   Calculate the increase: `min(rowMaxes[i], colMaxes[j]) - grid[i][j]`.
*   Add this to `totalIncrease`.
* Return `totalIncrease`.

# Solutions
### Java

```java
class Solution {
public
  int maxIncreaseKeepingSkyline(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] rmx = new int[m];
    int[] cmx = new int[n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rmx[i] = Math.max(rmx[i], grid[i][j]);
        cmx[j] = Math.max(cmx[j], grid[i][j]);
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans += Math.min(rmx[i], cmx[j]) - grid[i][j];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxIncreaseKeepingSkyline(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> rmx(m, 0);
    vector<int> cmx(n, 0);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rmx[i] = max(rmx[i], grid[i][j]);
        cmx[j] = max(cmx[j], grid[i][j]);
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ans += min(rmx[i], cmx[j]) - grid[i][j];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int: rmx = [max(row) for row in grid] cmx = [max(col) for col in zip(* grid)] return sum((min(rmx[i], cmx[j]) - grid[i][j]) for i in range(len(grid)) for j in range(len(grid[0])))

```