Problem

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval [left, right) denotes all the real numbers x where left <= x < right.

Implement the RangeModule class:

  • RangeModule() Initializes the object of the data structure.
  • void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
  • boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
  • void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

**Input**
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
**Output**
[null, null, null, true, false, true]

**Explanation**
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Solution

Method 1 - Using TreeMap

To efficiently track intervals and perform operations like adding, querying, and removing ranges, we can use a Sorted Map (TreeMap in Java or SortedDict in Python). These structures allow for efficient ordering and updates of key-value pairs.

Key Considerations

  • A TreeMap/SortedDict structure allows us to maintain intervals in sorted order and easily manage overlaps.
  • Add Range: Merge overlapping intervals and add the new range while preserving the sorted order.
  • Query Range: Iterate through the intervals to check whether the given range is fully covered by existing intervals.
  • Remove Range: Modify or split existing intervals as needed, excluding the range to be removed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class RangeModule {
    private TreeMap<Integer, Integer> intervals;

    public RangeModule() {
        intervals = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        int l = left, r = right;
        // Find overlapping intervals
        Map.Entry<Integer, Integer> start = intervals.floorEntry(left);
        if (start != null && start.getValue() >= left) {
            l = Math.min(l, start.getKey());
            r = Math.max(r, start.getValue());
            intervals.remove(start.getKey());
        }
        
        Map.Entry<Integer, Integer> curr = intervals.ceilingEntry(left);
        while (curr != null && curr.getKey() <= right) {
            l = Math.min(l, curr.getKey());
            r = Math.max(r, curr.getValue());
            intervals.remove(curr.getKey());
            curr = intervals.ceilingEntry(left);
        }
        // Add the merged interval
        intervals.put(l, r);
    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> prev = intervals.floorEntry(left);
        // Check if an interval fully covers [left, right)
        return prev != null && left >= prev.getKey() && right <= prev.getValue();
    }

    public void removeRange(int left, int right) {
        Map.Entry<Integer, Integer> start = intervals.floorEntry(left);
        if (start != null && start.getValue() > left) {
            int s = start.getKey();
            int e = start.getValue();
            intervals.remove(s);
            if (s < left) {
                intervals.put(s, left);
            }
            if (e > right) {
                intervals.put(right, e);
            }
        }
        
        Map.Entry<Integer, Integer> curr = intervals.ceilingEntry(left);
        while (curr != null && curr.getKey() < right) {
            int s = curr.getKey();
            int e = curr.getValue();
            intervals.remove(s);
            if (e > right) {
                intervals.put(right, e);
            }
            curr = intervals.ceilingEntry(left);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class RangeModule:
    def __init__(self) -> None:
        # SortedDict to track intervals as key-value pairs (start -> end)
        self.intervals = SortedDict()

    def addRange(self, left: int, right: int) -> None:
        # Start and end of the new range to be merged 
        l, r = left, right
        # Find all intervals that overlap with the range [left, right)
        keys_to_remove = []
        for start in self.intervals.keys():
            end = self.intervals[start]
            if end < l:  # No overlap since this interval is completely before
                continue
            elif start > r:  # No overlap since this interval is completely after
                break
            # Merge intervals
            l = min(l, start)
            r = max(r, end)
            keys_to_remove.append(start)
        
        # Remove merged intervals
        for key in keys_to_remove:
            del self.intervals[key]
        # Add the final merged interval
        self.intervals[l] = r

    def queryRange(self, left: int, right: int) -> bool:
        # Check if there is an interval covering [left, right)
        start = self.intervals.bisect_right(left) - 1
        if start == -1:
            return False
        return self.intervals.values()[start] >= right and list(self.intervals.keys())[start] <= left

    def removeRange(self, left: int, right: int) -> None:
        l, r = left, right
        keys_to_remove = []
        to_add = []
        
        for start in self.intervals.keys():
            end = self.intervals[start]
            if end <= l:  # No overlap since this interval is completely before
                continue
            elif start >= r:  # No overlap since this interval is completely after
                break
            # Partial overlap cases
            if start < l:
                to_add.append((start, l))
            if end > r:
                to_add.append((r, end))
            keys_to_remove.append(start)
        
        # Remove affected intervals
        for key in keys_to_remove:
            del self.intervals[key]
        # Add the remaining unaffected intervals
        for start, end in to_add:
            self.intervals[start] = end

Complexity

  • ⏰ Time complexity:

    • addRange has time complexity O(n) due to merging intervals.
    • queryRange has time complexity O(log n) for traversing and checking.
    • removeRange has time complexity O(n) due to modifying intervals.

  • 🧺 Space complexity: O(n) for storing intervals.