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.Problem Overview: Design a data structure that tracks numeric ranges. You must support three operations: addRange(left, right), removeRange(left, right), and queryRange(left, right). The challenge is efficiently merging, splitting, and checking overlapping intervals while the structure changes dynamically.
Approach 1: Sorted List of Intervals (O(n) time, O(n) space)
Maintain a sorted list of non-overlapping intervals. Each time you call addRange, iterate through the list, merge overlapping intervals, and insert the new merged interval in the correct position. For removeRange, scan the list and split any interval that partially overlaps with the removal range. queryRange simply checks whether a single interval fully covers the requested range. Because updates may require scanning and rebuilding parts of the list, operations take O(n) time in the worst case while storing up to O(n) intervals.
This approach is straightforward and works well when the number of stored intervals is small. It focuses on interval merging logic rather than advanced data structures.
Approach 2: Balanced Tree Map (O(log n) updates, O(n) space)
Store intervals in a balanced tree keyed by their start positions (for example TreeMap in Java). The tree keeps intervals sorted automatically and allows efficient neighbor lookups. For addRange, locate the first interval that might overlap using a floor or ceiling search, then merge all overlapping intervals while updating the map. removeRange works similarly but may split intervals into two smaller segments. queryRange checks the closest interval starting before left and verifies it extends past right.
Because tree operations like insertion, deletion, and predecessor search run in O(log n), the overall complexity for updates becomes O(log n + k), where k is the number of affected intervals. This makes the structure much more scalable for large numbers of updates.
The technique is conceptually related to interval management problems solved with ordered sets or advanced range structures like a segment tree. While a segment tree can also solve the problem, most interview solutions rely on ordered maps because the implementation is shorter and easier to reason about.
Recommended for interviews: The balanced tree map approach is typically expected in senior-level interviews. It demonstrates understanding of interval merging combined with efficient ordered lookups. Implementing the sorted list version first shows you understand the core interval logic; transitioning to the tree-based solution shows you can optimize operations from linear scans to logarithmic lookups.
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.
The 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.
Python
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.
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.
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.
Java
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.
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.
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.
Python
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.
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.
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.
Java
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.
According to the problem description, we need to maintain a set of intervals, supporting operations of interval addition, deletion, and query. For the addition and deletion of intervals, we can use a segment tree to maintain the set of intervals.
The segment tree divides the entire interval into multiple non-continuous sub-intervals, the number of which does not exceed log(width). To update the value of an element, only log(width) intervals need to be updated, and these intervals are all included in a large interval containing the element. When modifying the interval, we need to use lazy propagation to ensure efficiency.
[1,N];1, [x,x];[l,r], its left child is [l,mid], and the right child is [mid+1,r], where mid=⌊(l+r)/2⌋ (rounded down).Due to the large data range of the problem, we can implement it with a dynamically allocated segment tree. A dynamically allocated segment tree means that we only allocate nodes when needed, instead of allocating all nodes at the beginning. This can save space, but it requires lazy propagation to maintain interval modification.
In terms of time complexity, the time complexity of each operation is O(log n). The space complexity is O(m times log n). Here, m is the number of operations, and n is the data range.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorted List of Intervals | 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. |
| Approach 2: Balanced Tree (BST) | 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. |
| Approach 1: Using a Sorted List of Intervals | Time Complexity: |
| Approach 2: Using a Balanced Tree Map | Time Complexity: |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorted List of Intervals | O(n) per operation | O(n) | Simple implementation when the number of intervals is small and updates are infrequent |
| Balanced Tree Map (BST) | O(log n + k) | O(n) | Best general solution for frequent add/remove operations and large datasets |
RANGE MODULE | LEETCODE 715 | PYTHON SOLUTION • Cracking FAANG • 9,870 views views
Watch 9 more video solutions →Practice Range Module with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor