Problem statement

https://leetcode.com/problems/max-increase-to-keep-city-skyline/

Solution

We can notice, that at each point we can increase height in such way, that it is not more that minimum among two numbers: maximum is current row and maximum in current column. So, let us find these maximums and then just iterate over all grid and calculate sum.

Complexity

Time complexity is O(n^2), space complexity is O(n).

Code

class Solution:
    def maxIncreaseKeepingSkyline(self, grid):
        n, ans = len(grid), 0
        V = [max(i) for i in zip(*grid)]
        H = [max(i) for i in grid]
        for i,j in product(range(n), range(n)):
            ans += min(V[i], H[j]) - grid[i][j]        
        return ans