Watch 10 video solutions for Range Module, a hard level problem involving Design, Segment Tree, Ordered Set. This walkthrough by Cracking FAANG has 9,870 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |