LeetCode Solutions Blog

Range Module

Number: 715

Difficulty: Hard

Paid? No

Problem Description

Design a data structure to track ranges of numbers represented as half-open intervals [left, right). The structure must support adding an interval (merging with existing intervals if necessary), querying whether an entire interval is currently tracked, and removing an interval (which may split tracked intervals into multiple parts).

Key Insights

Use a sorted data structure (like an ordered list or balanced BST) to maintain non-overlapping intervals.
When adding an interval, merge it with overlapping intervals.
Query by checking if an interval is fully covered by one of the existing intervals.
Removing an interval requires splitting overlapping intervals accordingly.
Binary search can be used to quickly locate intervals that might overlap with the query range.

Space and Time Complexity

Time Complexity: Each addRange, queryRange, and removeRange operation can take O(n) in the worst-case as merging or splitting intervals might require scanning through intervals. Space Complexity: O(n) where n is the number of disjoint intervals stored.

Solution

We maintain a sorted list of intervals, where each interval is a pair [start, end) and the intervals are non-overlapping. For the addRange operation, we locate all intervals that overlap with [left, right) and merge them together. For queryRange, we use binary search to check if an interval exists that completely covers [left, right). For removeRange, overlapping intervals are modified or split to remove the range [left, right).

The key is to update the intervals list while ensuring it remains sorted and non-overlapping. This data structure avoids tracking every single number and is efficient in handling intervals up to large input sizes.

Code Solutions

# Python implementation with detailed line-by-line comments
class RangeModule:
    def __init__(self):
        # List to hold the non-overlapping intervals sorted by start
        self.intervals = []
    
    def addRange(self, left: int, right: int) -> None:
        new_intervals = []
        i = 0
        # Add all intervals that end before 'left'
        while i < len(self.intervals) and self.intervals[i][1] < left:
            new_intervals.append(self.intervals[i])
            i += 1
        
        # Merge all overlapping intervals with [left, right)
        while i < len(self.intervals) and self.intervals[i][0] <= right:
            left = min(left, self.intervals[i][0])
            right = max(right, self.intervals[i][1])
            i += 1
        
        # Add the merged interval
        new_intervals.append([left, right])
        
        # Append the remaining intervals that start after 'right'
        while i < len(self.intervals):
            new_intervals.append(self.intervals[i])
            i += 1
        
        self.intervals = new_intervals

    def queryRange(self, left: int, right: int) -> bool:
        # Binary search to find the position where 'left' would be inserted
        lo, hi = 0, len(self.intervals)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.intervals[mid][1] < left:
                lo = mid + 1
            else:
                hi = mid
        # If no interval covers [left, right), return false
        if lo < len(self.intervals) and self.intervals[lo][0] <= left and self.intervals[lo][1] >= right:
            return True
        return False

    def removeRange(self, left: int, right: int) -> None:
        new_intervals = []
        i = 0
        # Add all intervals that end before 'left'
        while i < len(self.intervals) and self.intervals[i][1] <= left:
            new_intervals.append(self.intervals[i])
            i += 1
        
        # Process intervals that overlap with [left, right)
        while i < len(self.intervals) and self.intervals[i][0] < right:
            # If part of the interval is left of 'left', keep it
            if self.intervals[i][0] < left:
                new_intervals.append([self.intervals[i][0], left])
            # If part of the interval is right of 'right', keep it
            if self.intervals[i][1] > right:
                new_intervals.append([right, self.intervals[i][1]])
            i += 1
        
        # Append the remaining intervals that start after 'right'
        while i < len(self.intervals):
            new_intervals.append(self.intervals[i])
            i += 1
        
        self.intervals = new_intervals