Implement addRange(left, right), which tracks every number in [left, right); removeRange(left, right), which stops tracking them; and queryRange(left, right), which returns whether every number in [left, right) is currently tracked. The expected output lists the query results.
Before you code
If the tracked set is stored as sorted, disjoint, non-touching intervals, how many intervals can a single add or remove affect, and how do you find them?
Hints
- Store the interval boundaries in one sorted list: even positions are starts, odd positions are ends.
- For add and remove, use bisect_left and bisect_right on left and right to find the slice of boundaries to replace, and decide from the parity of the positions which new boundaries to insert.
- For query, the range is covered when bisect_right(left) and bisect_left(right) are equal and odd: both ends fall inside the same interval.
- A list slice replacement is O(n) in the worst case; a balanced tree or SortedList brings each operation to O(log n) plus the intervals removed.
Production & complexity notes
When solving Range module on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in B-trees and pages to reinforce the underlying pattern.
What it practices
Sorted ranges and boundary searches, the operations behind B+ tree range scans, from B-trees and pages.