LeetCode Solutions Blog

Range Module

Difficulty: Hard

Problem Description

Design a data structure to track ranges represented as half-open intervals and query about them. Implement the RangeModule class with methods to add, query, and remove ranges.

Key Insights

A half-open interval [left, right) includes left but excludes right.
Overlapping intervals must be merged when adding a new range.
Removing a range can split existing intervals into smaller intervals.
Efficient querying requires checking if the entire queried range is covered.

Space and Time Complexity

Time Complexity:

addRange: O(n) in the worst case (merging intervals).
removeRange: O(n) in the worst case (splitting intervals).
queryRange: O(log n) for searching intervals if using a sorted list.

Space Complexity: O(n) for storing the intervals.

Solution

The solution uses a list to store intervals. Each interval is represented as a tuple (left, right). When adding a range, we merge overlapping intervals. When removing a range, we split existing intervals as needed. Querying checks if the requested range is fully covered by the stored intervals.

Code Solutions

class RangeModule:
    def __init__(self):
        self.intervals = []

    def addRange(self, left: int, right: int) -> None:
        new_intervals = []
        added = False
        
        for l, r in self.intervals:
            if r < left:  # Current interval is completely to the left
                new_intervals.append((l, r))
            elif right < l:  # Current interval is completely to the right
                if not added:  # Add new range before current interval
                    new_intervals.append((left, right))
                    added = True
                new_intervals.append((l, r))  # Current interval
            else:  # Overlapping intervals
                left = min(left, l)
                right = max(right, r)
        
        if not added:  # If new range wasn't added, add it at the end
            new_intervals.append((left, right))
        
        self.intervals = new_intervals

    def queryRange(self, left: int, right: int) -> bool:
        for l, r in self.intervals:
            if l <= left < r and l < right <= r:
                return True
            if l >= left and r <= right:
                return True
            if l < left and r > right:
                return False
        return False

    def removeRange(self, left: int, right: int) -> None:
        new_intervals = []
        
        for l, r in self.intervals:
            if r <= left:  # Current interval is completely to the left
                new_intervals.append((l, r))
            elif l >= right:  # Current interval is completely to the right
                new_intervals.append((l, r))
            else:  # Overlapping intervals
                if l < left:  # Left part remains
                    new_intervals.append((l, left))
                if r > right:  # Right part remains
                    new_intervals.append((right, r))
        
        self.intervals = new_intervals