• 6

    self.X is a sorted list of x-coordinates used by add/remove, where the tracking might start/stop. The corresponding self.track values tell whether tracking is on at the coordinate and to its right. Removing is really just adding a range of False, so I reuse addRange for it.

    class RangeModule(object):
        def __init__(self):
            self.X = [0, 10**9]
            self.track = [False] * 2
        def addRange(self, left, right, track=True):
            def index(x):
                i = bisect.bisect_left(self.X, x)
                if self.X[i] != x:
                    self.X.insert(i, x)
                    self.track.insert(i, self.track[i-1])
                return i
            i = index(left)
            j = index(right)
            self.X[i:j] = [left]
            self.track[i:j] = [track]
        def queryRange(self, left, right):
            i = bisect.bisect(self.X, left) - 1
            j = bisect.bisect_left(self.X, right)
            return all(self.track[i:j])
        def removeRange(self, left, right):
            self.addRange(left, right, False)

  • 2

    Share my python solution. Really the difficult part is to make sure I use bisect_left and bisect correctly.

    from bisect import bisect_left, bisect
    class RangeModule(object):
        def __init__(self):
            self.range = [-float('inf'), float('inf')]
        def addRange(self, left, right):
            self._updateRange(left, right, 0)
        def queryRange(self, left, right):
            li = bisect(self.range, left)
            ri = bisect_left(self.range, right)
            return li == ri and li % 2 == 0
        def removeRange(self, left, right):
            self._updateRange(left, right, 1)
        def _updateRange(self, left, right, op):
            li = bisect_left(self.range, left)
            ri = bisect(self.range, right)
            if li % 2 == op:
                li = li - 1
                left = self.range[li]
            if ri % 2 == op:
                right = self.range[ri]
                ri += 1
            self.range[li:ri] = [left, right]

  • 0

    @StefanPochmann I always learn something new from your solutions

  • 0

    @derek3 Mind explaining your logic?

  • 0

    @derek3 Awesome. I had actually briefly considered that idea (i.e., a sorted list of alternating on and off coordinates) but didn't try to implement it, I think it seemed difficult. And reading and thinking through your code, I still think it's difficult :-P. But it's short and fast, I just submitted it three times and it took about 420 ms, beating 100%, 99% and 99%, losing only to an earlier version of itself. (Next fastest submission was my solution, at 476 ms).

  • 0

    @StefanPochmann said in Python:
    do you mind explaining the "sorted list of alternating on and off coordinates" logic?

  • 0

    @StefanPochmann Your queryRange method is O(n), maybe that's why. When it's called repeatedly, it's way slower than O(lgn) solution.

Log in to reply

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