Easy understand Python O(n^2) using binary search

  • 0

    Ordered already fell square by their endpoints, using binary search to find earliest possible overlap position.

    def fallingSquares(self, positions):
            :type positions: List[List[int]]
            :rtype: List[int]
            import bisect
            d = []
            ret = []
            mi = 0
            for i,p in enumerate(positions):
                index = bisect.bisect(d,(p[0],float('inf'),p[1]))
                h = p[1]
                while index < len(d):
                    if d[index][1] < p[0]+p[1]:
                        h = max(h,p[1]+d[index][2])
                    index += 1
                mi = max(h,mi)
            return ret

Log in to reply

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