LeetCode 807: Max Increase to Keep City Skyline Solution

Master LeetCode problem 807 (Max Increase to Keep City Skyline), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

807. Max Increase to Keep City Skyline

Medium

Array Greedy Matrix

Problem Explanation

Explanation

To solve this problem, we need to find the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction. We can achieve this by iterating over the grid and calculating the maximum allowable height for each building based on the skylines viewed from the north and east directions. We then find the minimum value between these two constraints to ensure that the skyline is not affected in any direction.

Algorithm:

Initialize two arrays maxRows and maxCols to store the maximum building height seen from the north and east directions respectively.
Iterate over the grid to fill the maxRows array with the maximum height seen from each row.
Iterate over the grid again to fill the maxCols array with the maximum height seen from each column.
Iterate over the grid once more to calculate the maximum allowable height increase for each building based on the skyline constraints.
Sum up all the allowable height increases to get the maximum total sum.

Time Complexity:

The time complexity of this algorithm is O(n^2) where n is the size of the grid.

Space Complexity:

The space complexity of this algorithm is O(n) to store the maxRows and maxCols arrays.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 807 (Max Increase to Keep City Skyline)?

This page provides optimized solutions for LeetCode problem 807 (Max Increase to Keep City Skyline) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 807 (Max Increase to Keep City Skyline)?

The time complexity for LeetCode 807 (Max Increase to Keep City Skyline) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 807 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 807 in Java, C++, or Python.

Back to LeetCode Solutions