LeetCode 807. Max Increase to Keep City Skyline

September 13, 2020

A given element can be increased to the lesser of {max in its column, max in its row}. We can do that naively in $O((nm)^2)$ time. We can reduce that to $O(nm)$ by pre-computing the $(n+m)$ column and row maxes.

We can't do better than $O(nm)$ since we have to touch each element at least once.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]), 35)

class Solution:

    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        row_maxes = [0] * len(grid)
        col_maxes = [0] * len(grid[0])
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                col_maxes[j] = max(col_maxes[j], grid[i][j])
                row_maxes[i] = max(row_maxes[i], grid[i][j])
        increase = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                increase += min(row_maxes[i], col_maxes[j]) - grid[i][j]
        return increase

if __name__ == "__main__":
    unittest.main()