DSA problem
Range Module
Design a RangeModule that tracks ranges of numbers and supports three operations on the half-open interval [left, right). addRange(left, right) adds every real number in [left, right) to the tracked set, merging with any existing range that overlaps or is adjacent to the new one. queryRange(left, right) returns true only if every real number in [left, right) is currently tracked. removeRange(left, right) removes every real number in [left, right) from the tracked set, splitting any range that crosses the boundary.
Storing every integer would be impossible because the endpoints are up to 10^9 and the values are continuous; we store disjoint intervals instead. The natural representation is an ordered map keyed by interval start with the value being the matching end. Because the intervals we store are always disjoint and non-adjacent (we merge on insert), the map is a clean compressed view of the tracked set.
For addRange(left, right) we walk the map from the first interval whose start could overlap or touch the new range — that is, all intervals with start <= right and end >= left — absorbing their endpoints into left and right and deleting them. After the scan we insert one merged [left, right) entry. The "adjacent" case (end == left) is included so two abutting intervals collapse into one rather than sitting beside each other.
removeRange(left, right) is the mirror operation: find all intervals overlapping the request, delete them, and reinsert at most two leftover fragments — one for the part before left if the deleted interval extended further left, and one for the part after right if it extended further right. queryRange(left, right) uses a floor lookup on left (the largest stored start <= left) and returns true only if that interval's end is >= right.
Examples
addRange(10, 20); removeRange(14, 16); queryRange(10, 14); queryRange(13, 15); queryRange(16, 17)[true, false, true]addRange(6, 8); removeRange(7, 8); addRange(8, 9); queryRange(7, 8); queryRange(7, 9)[false, false]addRange(1, 5); addRange(4, 10); queryRange(1, 10)trueConstraints
- 1 <= left < right <= 10^9
- At most 10^4 calls will be made to addRange, queryRange, and removeRange.
- Intervals are half-open: [left, right) — the right endpoint is exclusive.
- addRange must merge with overlapping AND adjacent intervals.
- removeRange may split an existing interval into 0, 1, or 2 fragments.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.