LC-0807 Medium LeetCode

807. Max Increase to Keep City Skyline

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 86% Topics: Array, Greedy, Matrix

Reading material

Arrays & Hashing 12 min Greedy 11 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

import itertools


class Solution(object):
    def maxIncreaseKeepingSkyline(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row_maxes = [max(row) for row in grid]
        col_maxes = [max(col) for col in itertools.izip(*grid)]

        return sum(min(row_maxes[r], col_maxes[c])-val \
                   for r, row in enumerate(grid) \
                   for c, val in enumerate(row))

Solution from kamyu104/LeetCode-Solutions · MIT