Python with dict, O(N^2) solution with comments

  • 3
    class Solution:
        def fallingSquares(self, positions):
            :type positions: List[List[int]]
            :rtype: List[int]
            ans = []
            heights = {}
            for pos, side in positions:
                # finds nearby positions, if any
                left, right = pos, pos+side-1
                # compare to see if this block overlaps with L/R boundaries of existing blocks
                nearby = [key for key in heights.keys() if not (key[1] < pos or key[0] > right)]
                # finds height of block based on heights of existing and overlapping blocks
                if len(nearby) > 0:
                    h = max(heights[key] for key in nearby) + side
                    h = side
                # update the heights for left and right boundaries
                heights[(pos,right)] = h
                # add height to ans
                if len(ans) == 0:
            return ans

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.