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).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)
Constraints:
1 <= left < right <= 109104 calls will be made to addRange, queryRange, and removeRange.The Range Module problem requires designing a data structure that can efficiently addRange, removeRange, and queryRange over continuous intervals. The key challenge is managing overlapping intervals while keeping operations fast.
A common approach uses an ordered set (balanced BST) or a map that stores disjoint intervals. When adding or removing ranges, you merge or split overlapping intervals while maintaining sorted order. Querying then becomes a matter of checking whether a stored interval fully covers the requested range.
Another advanced approach uses a Segment Tree with lazy propagation. This method treats the number line as a range and tracks coverage with node states. It allows efficient updates and queries across large coordinate ranges, especially when intervals are sparse.
The ordered-set solution is usually simpler to implement, while the segment tree approach provides more flexibility for large-scale interval operations. Both approaches aim to keep updates and queries efficient while maintaining correct interval coverage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Ordered Set / Interval Map | O(log n) per operation (with possible merges) | O(n) |
| Segment Tree with Lazy Propagation | O(log n) per update or query | O(n) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Maintain a sorted set of disjoint intervals. addRange and removeRange can be performed with time complexity linear to the size of this set; queryRange can be performed with time complexity logarithmic to the size of this set.
This approach involves maintaining a sorted list of disjoint intervals. Each interval is represented by a tuple of start and end. The trick is to ensure efficient merging of intervals when adding, removal of specific intervals, and checking for fully covered range during queries. The list remains sorted to optimize these operations.
Time complexity for addRange, queryRange, and removeRange is O(n), where n is the number of tracked intervals. Space complexity is O(n) due to storage of intervals.
1class RangeModule:
2 def __init__(self):
3 self.intervals = []
4
5 def addRange(self, left: int, right: int) -> None:
6 new_intervals = []
7 placed = False
8 for start, end in self.intervals:
9 if end < left or start > right:
10 new_intervals.append((start, end))
11 else:
12 left = min(left, start)
13 right = max(right, end)
14 placed = True
15 if not placed:
16 new_intervals.append((left, right))
17 new_intervals.sort()
18 self.intervals = new_intervals
19
20 def queryRange(self, left: int, right: int) -> bool:
21 for start, end in self.intervals:
22 if start <= left and right <= end:
23 return True
24 return False
25
26 def removeRange(self, left: int, right: int) -> None:
27 new_intervals = []
28 for start, end in self.intervals:
29 if end <= left or start >= right:
30 new_intervals.append((start, end))
31 else:
32 if start < left:
33 new_intervals.append((start, left))
34 if end > right:
35 new_intervals.append((right, end))
36 self.intervals = new_intervals
37The class maintains a list of tuples representing intervals. The addRange method merges overlapping or adjacent intervals into the list. The queryRange checks if an entire range falls within one of the tracked intervals, and removeRange removes parts of intervals that fall within a given range by splitting intervals as necessary.
A more advanced approach involves using a balanced binary search tree to maintain the intervals, allowing logarithmic time complexity for add, query, and remove operations.
Time complexity for addRange, queryRange, and removeRange is O(log n), where n is the number of distinct intervals. Space complexity is O(n) due to storage requirements of the tree map.
1import java.util.TreeMap;
2
3class RangeModule {
4
This approach utilizes a sorted list of intervals to represent the tracked ranges. The key operations involve merging intervals upon addition, checking containment for queries, and properly splitting and removing intervals as needed. The merging operation helps to keep the list of intervals minimal and efficiently queryable.
The basic idea is to maintain a list with no overlapping intervals, merge overlapping intervals on addition, and adjust intervals on remove operations accordingly.
Time Complexity: O(N) per operation, where N is the number of tracked ranges. This is because merging intervals during addition and updating during removal requires traversing the list.
Space Complexity: O(N), where N is the amount of memory required to store the intervals.
1class RangeModule:
2 def __init__(self)
In this approach, a balanced binary search tree (or map) is used to keep track of the intervals. The idea is to leverage the ordering properties of a tree structure to efficiently find, add, and remove intervals.
Each node in the tree represents an interval, and operations on intervals involve traversals and updates of the tree nodes. This ensures logarithmic time complexity for most operations.
Time Complexity: O(log N) per operation due to operations on the tree structure for lookups and updates.
Space Complexity: O(N), as we need to store the intervals in the tree map.
1import java.util.TreeMap;
2
3class RangeModule
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval management and design problems like Range Module are common in FAANG-style interviews. They test understanding of ordered structures, interval merging logic, and advanced data structures such as segment trees.
The most common approach uses an ordered set or map of disjoint intervals. By merging overlapping intervals during additions and splitting them during removals, you can maintain efficient updates and queries in logarithmic time.
The difficulty comes from correctly handling overlapping intervals while supporting three operations: add, remove, and query. Maintaining interval consistency and ensuring efficient updates requires careful data structure design.
Balanced binary search trees (such as TreeMap or ordered sets) are widely used because they maintain sorted intervals and allow efficient merging and lookup. Segment trees with lazy propagation are another powerful alternative for handling large numeric ranges.
This implementation uses Java's TreeMap, which is a balanced binary search tree. The keys in the tree represent the start of intervals, and the values represent the ends. This structure allows for efficient merging and querying of intervals using logarithmic time operations.
This Python implementation uses a sorted list of intervals to keep track of the range. The addRange function merges overlapping intervals. The queryRange function checks if the given range is fully covered by any existing interval, and removeRange updates the intervals by effectively splitting any overlapping intervals to remove the specified range. The list remains sorted, ensuring efficient updates and queries.
This Java implementation leverages a TreeMap to automatically sort and manage the intervals. The addRange method finds existing overlapping ranges and merges them. The queryRange method checks if the range falls completely within any existing tracked range. The removeRange method carefully adjusts intervals by potentially splitting existing ones. The use of a TreeMap ensures that lookups and modifications remain efficient.