Max Increase To Keep City Skyline - Leetcode Solution

The problem of Max Increase To Keep City Skyline on LeetCode can be solved using a greedy approach. Here is a step-by-step solution:

1. Firstly, find the maximum element in each row and each column. These values will give the height of the buildings on the skyline from left to right and from top to bottom.

2. Create two arrays to store these maximum values for rows and columns.

3. Traverse the input matrix again and for each cell, calculate the difference between the minimum of row and column maximum values and the current value of that cell.

4. Increment a counter with the above-calculated difference and store it in a variable.

5. Return the final value of the counter.

Here is the Python code for the same:

    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        nrows = len(grid)
        ncols = len(grid[0])
        
        row_max = [max(row) for row in grid]
        col_max = [max(col) for col in zip(*grid)]
        
        counter = 0
        
        for i in range(nrows):
            for j in range(ncols):
                counter += min(row_max[i], col_max[j]) - grid[i][j]
        
        return counter

Time Complexity: O(N^2) where N is the number of rows or columns. We are traversing the matrix twice, once to calculate maximum values and then to calculate the final result.

Space Complexity: O(N) to store maximum values for rows and columns.

1