DDSA Solutions

807. Max Increase to Keep City Skyline

MediumView on LeetCode
ArrayGreedyMatrix
Time: O(n²)
Space: O(n)

Problem Overview

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

Intuition

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

Algorithm

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

Common Pitfalls

  • •Limit is the minimum of the two maximums (most restrictive constraint).
807.cs
C#
// 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?

Related Problems