Python sorted list comments O(nlogn)
I wrote this before looking at other people\'s solutions. It\'s definitely not the most concise, but I think it\'s logically clear what\'s happening. The commen
I wrote this before looking at other people\'s solutions. It\'s definitely not the most concise, but I think it\'s logically clear what\'s happening. The comments explain everything but the strategy is to keep a list of ranges and find the tallest height of the ranges which intersect the shadow of the new square. While we find this height, we can simultaneously update/remove ranges to account for this new square. Any partially covered range gets chopped off at the corresponding edge of the new square. Any range that is completely covered by the square gets deleted. If the square is in the middle of a range, then the range gets cut off at the left side of the new square and a new range covers from the right side onward until the end of the original range.\n\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        # sorted list where value is a tuple of (leftside, length, height)\n        # iterate through squares and find which ranges it intersects,\n        #       updating the ranges and tracking the highest point\n        # add a new range with the appropriate height\n        # if this height is greater than tallest, replace tallest.\n        # append tallest to answer\n        \n        # add, del/pop, bisect, and __getitem__ are all O(log(n)) operations on SortedList\n        # number of operations is bounded by c*n times where n is the length of positions and c is a constant\n        # time complexity: O(n log(n))\n        # space complexity: O(n)\n        \n        \n        sl = SortedList()\n        ans = []\n        tallest = 0\n        \n        for left, length in positions:\n            idx = sl.bisect_left((left, 0, 0))\n            max_height = 0\n            if idx > 0:\n                # ls: left side, l: length, h: height\n                ls, l, h = sl[idx-1]\n                # left side of new square is within range\n                if ls + l > left:\n                    max_height = h\n                    del sl[idx-1]\n                    sl.add((ls, left-ls, h))\n                    # new square is in middle of range\n                    if ls + l > left + length:\n                        sl.add((left+length, ls+l-(left+length), h))\n            \n            right = left + length\n            # while right side of new square is to the right of left side of range\n            # (should only run n times total since ranges are being compressed on each iteration)\n            while idx < len(sl) and sl[idx][0] < right:\n                ls, l, h = sl[idx]\n                max_height = max(max_height, h)\n                # new square completely covers range\n                if ls + l <= right:\n                    sl.pop(idx)\n                # new square covers left side of range\n                else:\n                    del sl[idx]\n                    sl.add((right, ls + l - right, h))\n                    \n            tallest = max(max_height+length, tallest)\n            sl.add((left, length, max_height+length))\n            ans.append(tallest)\n            #print(sl)\n        return ans\n\t```
['Python', 'Python3']