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


  • 0
    A

    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
                bisect.insort(d,(p[0]+p[1],p[0],h))
                mi = max(h,mi)
                ret.append(mi)
            return ret
    

Log in to reply
 

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