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


  • 1
    C
    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
                else:
                    h = side
                # update the heights for left and right boundaries
                heights[(pos,right)] = h
                # add height to ans
                if len(ans) == 0:
                    ans.append(h)
                else:
                    ans.append(max(h,ans[-1]))
            return ans
    

Log in to reply
 

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