LeetCode: 715. Range Module

 

We need to deal with ranges to solve this problem.

Below is the link of a wonderful solution.

https://leetcode.com/problems/range-module/discuss/244194/Python-solution-using-bisect_left-bisect_right-with-explanation

Python solution using bisect_left, bisect_right with explanation - LeetCode Discuss

 

The solution uses a single list of integers to deal with ranges, which allows us to use 'bisect' functions easily.

Personally, understanding his idea was easy, but coming up with it would have been very difficult.

 

Below is the code. 

class RangeModule:
    from bisect import bisect_left, bisect_right
    
    def __init__(self):
        self.range = []
    
    def addRange(self, left: int, right: int) -> None:
        start = bisect_left(self.range, left)
        end = bisect_right(self.range, right)
        
        new_range = []
        if start % 2 == 0:
            new_range.append(left)
        if end % 2 == 0:
            new_range.append(right)
        self.range[start:end] = new_range
        
    def queryRange(self, left: int, right: int) -> bool:
        start = bisect_right(self.range, left)
        end = bisect_left(self.range, right)
        return start == end and start % 2 == 1
    
    def removeRange(self, left: int, right: int) -> None:
        start = bisect_left(self.range, left)
        end = bisect_right(self.range, right)
        
        new_range = []
        if start % 2 == 1:
            new_range.append(left)
        if end % 2 == 1:
            new_range.append(right)
        self.range[start:end] = new_range


# 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)

 

addRange and removeRange functions look very alike.

The very first thing we do is looking for index (start & end) using bisect. It is very essential to notice that self.range[start:end] is affected by [left, right). In other words, we are basically finding start and end index of self.range that are affected by [left, right).

* bisect_left, bisect_right should be properly used to handle duplicates.

 

Next, self.range[start:end] is replaced by new_range. In my opinion, that is the beauty of this code. Both start and end index can be either odd or even. If they are even, it means they lie outside the existing ranges. On the contrary, if they are odd, it means they lie inside the existing ranges. So, for addRange function, among the two index (start & end), only even ones get to be in new_range. As a result, new range can have a form of [], [start], [end], [start, end]. 

 

The very same approach can be also used in the below problem as well.

https://leetcode.com/problems/amount-of-new-area-painted-each-day/

Account Login - LeetCode

class Solution:
    from bisect import bisect_left, bisect_right
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        self.ranges = []
        ret = []
        for left, right in paint:
            ret.append(self.insertRange(left, right))
        return ret
        
    def insertRange(self, left, right):
        start = bisect_left(self.ranges, left)
        end = bisect_right(self.ranges, right)
        
        residuals = []
        new_range = []
        
        if start % 2 == 0:
            new_range.append(left)
            residuals.append(left)
        residuals += self.ranges[start:end]
        if end % 2 == 0:
            new_range.append(right)
            residuals.append(right)
        self.ranges[start:end] = new_range
        
        ret = 0
        for i in range(1, len(residuals), 2):
            ret += residuals[i] - residuals[i-1]
        return ret