807. Max Increase to Keep City Skyline

MediumView on LeetCode

Array Greedy Matrix

Time: O(n²)

Space: O(n)

Intuition

Each building can be increased to min(rowMax, colMax) without changing the skyline from either direction.

Algorithm

1Compute rowMax[i] = max of row i, colMax[j] = max of col j.
2For each (i,j): allowed = min(rowMax[i], colMax[j]). Increase = allowed - grid[i][j].
3Sum all increases.

Common Pitfalls

•Limit is the minimum of the two maximums (most restrictive constraint).

807.cs

// Approach: Precompute row max and column max; each cell can be increased to min(rowMax[i], colMax[j]) without changing the skyline.
// Time: O(n²) Space: O(n)

public class Solution
{
    public int MaxIncreaseKeepingSkyline(int[][] grid)
    {
        int n = grid.Length;
        int[] row = new int[n];
        int[] col = new int[n];

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                row[i] = Math.Max(row[i], grid[i][j]);
                col[j] = Math.Max(col[j], grid[i][j]);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                ans += Math.Min(row[i], col[j]) - grid[i][j];
        }

        return ans;
    }
}

Was this solution helpful?