Range Module
HardUpdated: Aug 2, 2025
Practice on:
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)Returnstrueif every real number in the interval[left, right)is currently being tracked, andfalseotherwise.void removeRange(int left, int right)Stops tracking every real number currently being tracked in the half-open interval[left, right).
Examples
Example 1:
**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
Java
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);
}
}
}
Python
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:
addRangehas time complexityO(n)due to merging intervals.queryRangehas time complexityO(log n)for traversing and checking.removeRangehas time complexityO(n)due to modifying intervals.
-
🧺 Space complexity:
O(n)for storing intervals.