unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 715: Range Module

link

Set

We can keep a set of the actual numbers contained within ranges.

class RangeModule:

    def __init__(self):
        self.range_set = set()
        
    def addRange(self, left: int, right: int) -> None:
        for x in range(left, right):
            self.range_set.add(x)

    def queryRange(self, left: int, right: int) -> bool:
        for x in range(left, right):
            if x not in self.range_set:
                return False
        return True
        
    def removeRange(self, left: int, right: int) -> None:
        for x in range(left, right):
            self.range_set.discard(x)

# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

Sorted list of ranges

We maintain a list of disjoint ranges sorted by left.

Say at the time of operations, there are n disjoint ranges. Total space is \mathcal{O}(n).

OperationTimeSpace
__init__\mathcal{O}(1)\mathcal{O}(1)
addRange\mathcal{O}(n \cdot \lg{n})\mathcal{O}(n)
queryRange\mathcal{O}(n)\mathcal{O}(1)
removeRange\mathcal{O}(n)\mathcal{O}(n)
class RangeModule:

    def __init__(self):
        self.ranges = []

    def __merge(self):
        if not self.ranges:
            return

        self.ranges.sort()
        merged = []
        prev = self.ranges[0]
        for i in range(1, len(self.ranges)):
            curr = self.ranges[i]
            if prev[1] < curr[0]:
                merged.append(prev)
                prev = curr
            else:
                prev = [ prev[0], max(prev[1], curr[1]) ]
        
        merged.append(prev)
        self.ranges = merged

    def addRange(self, left: int, right: int) -> None:
        self.ranges.append( [left, right] )
        self.__merge()

    def queryRange(self, left: int, right: int) -> bool:
        for r in self.ranges:
            if left >= r[0] and right <= r[1]:
                return True
        
        return False
        
    def removeRange(self, left: int, right: int) -> None:
        removed = []
        for r in self.ranges:
            if r[1] <= left or r[0] >= right:
                removed.append(r)
            else: # overlaps
                left_range = [ r[0], left ]
                if left_range[0] < left_range[1]:
                    removed.append(left_range)
                right_range = [ right, r[1] ]
                if right_range[0] < right_range[1]:
                    removed.append( right_range )
        
        self.ranges = removed

# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

Since we have a sorted list of disjoint ranges, we can do binary-search in queryRange().

OperationTimeSpace
__init__\mathcal{O}(1)\mathcal{O}(1)
addRange\mathcal{O}(n \cdot \lg{n})\mathcal{O}(n)
queryRange\mathcal{O}(\lg{n})\mathcal{O}(1)
removeRange\mathcal{O}(n)\mathcal{O}(n)
class RangeModule:

    def __init__(self):
        self.ranges = []

    def __merge(self):
        if not self.ranges:
            return

        self.ranges.sort()
        merged = []
        prev = self.ranges[0]
        for i in range(1, len(self.ranges)):
            curr = self.ranges[i]
            if prev[1] < curr[0]:
                merged.append(prev)
                prev = curr
            else:
                prev = [ prev[0], max(prev[1], curr[1]) ]
        
        merged.append(prev)
        self.ranges = merged

    def addRange(self, left: int, right: int) -> None:
        self.ranges.append( [left, right] )
        self.__merge()

    def queryRange(self, left: int, right: int) -> bool:
        lo, hi = 0, len(self.ranges)-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.ranges[mid][1] <= left:
                lo = mid+1
            else:
                hi = mid-1
        
        if lo == len(self.ranges):
            return False
        
        container_left, container_right = self.ranges[lo]
        return container_left <= left and right <= container_right
        
    def removeRange(self, left: int, right: int) -> None:
        removed = []
        for r in self.ranges:
            if r[1] <= left or r[0] >= right:
                removed.append(r)
            else: # overlaps
                left_range = [ r[0], left ]
                if left_range[0] < left_range[1]:
                    removed.append(left_range)
                right_range = [ right, r[1] ]
                if right_range[0] < right_range[1]:
                    removed.append( right_range )
        
        self.ranges = removed

# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

Since we already have the ranges sorted, we do not need to sort in addRange().

OperationTimeSpace
__init__\mathcal{O}(1)\mathcal{O}(1)
addRange\mathcal{O}(n)\mathcal{O}(n)
queryRange\mathcal{O}(\lg{n})\mathcal{O}(1)
removeRange\mathcal{O}(n)\mathcal{O}(n)
class RangeModule:

    def __init__(self):
        self.ranges = []

    def addRange(self, left: int, right: int) -> None:
        if not self.ranges:
            self.ranges.append([left, right])
            return

        merged = []
        i = 0
        while i < len(self.ranges) and self.ranges[i][1] < left:
            merged.append(self.ranges[i])
            i += 1

        if i == len(self.ranges):
            self.ranges.append([left, right])
            return

        if left < self.ranges[i][0]:
            prev = [left, right]
        else:
            prev = [ self.ranges[i][0], max(right, self.ranges[i][1]) ]
            i += 1

        while i < len(self.ranges):
            curr = self.ranges[i]
            if prev[1] < curr[0]:
                merged.append(prev)
                prev = curr
            else:
                prev = [ prev[0], max( prev[1], curr[1] ) ]

            i += 1
        
        merged.append(prev)
        self.ranges = merged

    def queryRange(self, left: int, right: int) -> bool:
        lo, hi = 0, len(self.ranges)-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.ranges[mid][1] <= left:
                lo = mid+1
            else:
                hi = mid-1
        
        if lo == len(self.ranges):
            return False
        
        container_left, container_right = self.ranges[lo]
        return container_left <= left and right <= container_right
        
    def removeRange(self, left: int, right: int) -> None:
        removed = []
        for r in self.ranges:
            if r[1] <= left or r[0] >= right:
                removed.append(r)
            else: # overlaps
                left_range = [ r[0], left ]
                if left_range[0] < left_range[1]:
                    removed.append(left_range)
                right_range = [ right, r[1] ]
                if right_range[0] < right_range[1]:
                    removed.append( right_range )
        
        self.ranges = removed

# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

tanvirdotzaman

,

Leave a comment