Python, O(n^2) solution, with explanation


  • 1

    usesq to store information of squares. sq[i][0] is left edge, sq[i][1] is length, sq[i][2] is highest point. Everytime a new square falls, check if it has overlap with previous sq, if so, add the largest sq[i][2] to its height.

    class Solution(object):
        def fallingSquares(self, positions):
            """
            :type positions: List[List[int]]
            :rtype: List[int]
            """
            if not positions:
                return []
            sq = [[positions[0][0], positions[0][1], positions[0][1]]]
            result = [positions[0][1]]
            max_h = result[0]
            for pos in positions[1: ]:
                h = pos[1]
                l = pos[0]
                add = 0
                for prev in sq:
                    if not l >= prev[0] + prev[1] and not l + h <= prev[0]:
                        add = max(add, prev[2])
                sq.append([l, h, h + add])
                max_h = max(max_h, h + add)
                result.append(max_h)
            return result
    

Log in to reply
 

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