Python, O(n^2) solution, with explanation
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 overl
use```sq``` 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.\n```\nclass Solution(object):\n    def fallingSquares(self, positions):\n        """\n        :type positions: List[List[int]]\n        :rtype: List[int]\n        """\n        if not positions:\n            return []\n        sq = [[positions[0][0], positions[0][1], positions[0][1]]]\n        result = [positions[0][1]]\n        max_h = result[0]\n        for pos in positions[1: ]:\n            h = pos[1]\n            l = pos[0]\n            add = 0\n            for prev in sq:\n                if not l >= prev[0] + prev[1] and not l + h <= prev[0]:\n                    add = max(add, prev[2])\n            sq.append([l, h, h + add])\n            max_h = max(max_h, h + add)\n            result.append(max_h)\n        return result\n```
[]