Range Module — Disjoint Intervals, Sorted Map & Segment Tree Coverage Tracker

Problem Statement#

LeetCode 715 — Range Module | Difficulty: Hard

Design a data structure to track ranges of numbers. Implement these methods:

• addRange(left, right) — add the half-open interval [left, right) to the tracked set.
• removeRange(left, right) — remove [left, right) from the tracked set.
• queryRange(left, right) — return true if every real number in [left, right) is currently being tracked.

Constraints:

• 1 is less than or equal to left, which is less than right, which is less than or equal to 10^9
• At most 10^4 calls across all three methods

Example:

addRange(10, 20)   -> tracked: [10, 20)
removeRange(14, 16) -> tracked: [10, 14) and [16, 20)
queryRange(10, 14) -> true
queryRange(13, 15) -> false  (the point 14 is not tracked)
queryRange(16, 17) -> true

Why This Problem Matters#

Range Module is the hardest interval-tracking problem in the LeetCode top-100 set because it forces three operations to share one data structure: add (which merges overlapping intervals), remove (which splits them), and query (which verifies full coverage). Google and Amazon use it as a senior interview signal because real systems — feature flag rollouts, IP-range whitelists, time-series gap tracking, garbage collector free-list management — solve exactly this problem.

The data structure choice matters: a naive list of intervals gives O(n) per call. A sorted map of disjoint intervals gives amortized O(log n) because each interval can only be created or destroyed once. A segment tree with lazy propagation generalizes to richer queries but is overkill here. Knowing which to pick under what constraints is the senior signal.

The Core Insight#

Maintain a sorted map of disjoint half-open intervals, keyed by start. The invariant is that no two intervals in the map overlap or touch. Every operation preserves this invariant.

addRange(left, right)#

Find every interval that overlaps or touches [left, right):

1. Walk forward from the predecessor.
2. For each overlapping interval, extend left and right to absorb it, then delete it.
3. Insert the merged super-interval at the end.

removeRange(left, right)#

Find every interval that overlaps [left, right):

1. Walk forward from the predecessor.
2. For each overlapping interval, delete it. Re-insert any portion that lies strictly outside [left, right).

queryRange(left, right)#

Find the latest interval whose start is at or below left:

1. If it exists and its end is greater than or equal to right, return true.
2. Otherwise return false.

The amortized complexity is O(log n) per operation because each interval enters the map at most once per insertion and leaves at most once. Across q operations, total work is O(q log q).

Visual Dry Run#

Initial state: { }
 
addRange(10, 20):
  no overlaps -> insert (10, 20)
  state: {(10, 20)}
 
addRange(15, 25):
  predecessor (10, 20) overlaps -> absorb
  merged left=10, right=25, delete (10,20)
  no further overlaps -> insert (10, 25)
  state: {(10, 25)}
 
removeRange(14, 16):
  (10, 25) overlaps with [14, 16)
  delete (10, 25)
  reinsert left fragment (10, 14)
  reinsert right fragment (16, 25)
  state: {(10, 14), (16, 25)}
 
queryRange(10, 13):
  predecessor at or below 10: (10, 14), end = 14, 14 >= 13 -> true
 
queryRange(13, 17):
  predecessor at or below 13: (10, 14), end = 14, 14 >= 17? no -> false
 
queryRange(16, 25):
  predecessor at or below 16: (16, 25), end = 25, 25 >= 25 -> true

The invariant — disjoint, non-touching intervals — is the foundation that makes every operation simple.

Solution (Optimal)#

Python — SortedList of (start, end) Tuples#

from sortedcontainers import SortedList
 
class RangeModule:
    def __init__(self):
        self.ranges = SortedList()                     # list of (start, end) sorted by start
 
    def addRange(self, left: int, right: int) -> None:
        # find intervals that overlap or touch [left, right)
        i = self.ranges.bisect_left((left, left))      # first interval with start >= left
        if i > 0 and self.ranges[i - 1][1] >= left:    # predecessor extends into our range
            i -= 1                                     # include it in the merge
 
        # absorb every overlapping or touching interval
        while i < len(self.ranges) and self.ranges[i][0] <= right:
            l, r = self.ranges.pop(i)                  # remove from sorted list
            left = min(left, l)                        # extend left boundary
            right = max(right, r)                      # extend right boundary
 
        self.ranges.add((left, right))                 # insert merged super-interval
 
    def removeRange(self, left: int, right: int) -> None:
        i = self.ranges.bisect_left((left, left))
        if i > 0 and self.ranges[i - 1][1] > left:     # predecessor extends past left
            i -= 1
 
        # delete and re-insert fragments outside [left, right)
        new_fragments = []
        while i < len(self.ranges) and self.ranges[i][0] < right:
            l, r = self.ranges.pop(i)
            if l < left:
                new_fragments.append((l, left))        # left fragment survives
            if r > right:
                new_fragments.append((right, r))       # right fragment survives
 
        for fragment in new_fragments:
            self.ranges.add(fragment)
 
    def queryRange(self, left: int, right: int) -> bool:
        # predecessor: interval whose start is at or below left
        i = self.ranges.bisect_right((left, float('inf'))) - 1
        return i >= 0 and self.ranges[i][0] <= left and self.ranges[i][1] >= right

JavaScript — Sorted Array of [start, end]#

class RangeModule {
    constructor() {
        this.ranges = [];                              // sorted by start
    }
 
    // binary search: smallest index i where ranges[i][0] >= target
    _lowerBound(target) {
        let lo = 0, hi = this.ranges.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.ranges[mid][0] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
 
    addRange(left, right) {
        let i = this._lowerBound(left);
        // check predecessor for overlap
        if (i > 0 && this.ranges[i - 1][1] >= left) i--;
 
        // absorb overlapping or touching intervals
        while (i < this.ranges.length && this.ranges[i][0] <= right) {
            left = Math.min(left, this.ranges[i][0]);
            right = Math.max(right, this.ranges[i][1]);
            this.ranges.splice(i, 1);                  // remove absorbed interval
        }
 
        this.ranges.splice(i, 0, [left, right]);       // insert merged interval
    }
 
    removeRange(left, right) {
        let i = this._lowerBound(left);
        if (i > 0 && this.ranges[i - 1][1] > left) i--;
 
        const fragments = [];
        while (i < this.ranges.length && this.ranges[i][0] < right) {
            const [l, r] = this.ranges[i];
            this.ranges.splice(i, 1);                  // remove the overlapping interval
            if (l < left)  fragments.push([l, left]);  // surviving left part
            if (r > right) fragments.push([right, r]); // surviving right part
        }
        for (const f of fragments) {
            const idx = this._lowerBound(f[0]);
            this.ranges.splice(idx, 0, f);             // reinsert surviving fragment
        }
    }
 
    queryRange(left, right) {
        // find largest interval start that is <= left
        let lo = 0, hi = this.ranges.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.ranges[mid][0] <= left) lo = mid + 1;
            else hi = mid;
        }
        const idx = lo - 1;
        return idx >= 0 && this.ranges[idx][1] >= right;
    }
}

Complexity: Amortized O(log n) per addRange and removeRange because each interval enters and leaves the structure at most once. queryRange is O(log n). Space O(n) where n is the current number of disjoint intervals.

Common Mistakes#

1. Forgetting to check the predecessor before merging. When the predecessor ends exactly at left for addRange, you must absorb it because half-open intervals touch. Skipping the back-step gives non-merged neighbors.
2. Wrong inequality on touching versus overlapping. For addRange, intervals that touch (prev.end == left) should merge. For removeRange, touching does not require fragmentation.
3. Mutating during iteration. Calling pop while iterating with index variables on the same SortedList works only because i does not advance after a pop. If you increment i after popping, you skip the next interval.
4. Re-inserting the wrong fragment. During removeRange, the left fragment is (l, left) and the right fragment is (right, r). Swapping them silently corrupts the structure.
5. Querying without checking the start. queryRange needs the predecessor whose start is at or below left AND whose end covers right. Skipping the start check accepts wrong intervals.
6. Using a regular list with O(n) lookups. Plain Python lists lack binary search; the operations degrade to O(n) per call and time out on adversarial inputs.

Interview Tips#

• State the disjoint-interval invariant first. "I will maintain a sorted set of pairwise-disjoint half-open intervals" — this single sentence sets the stage and explains every operation.
• Walk through merge logic on a whiteboard. Show two cases: predecessor that touches versus predecessor that overlaps. The interviewer wants to see you handle both.
• Mention the amortized argument. Each interval enters the map once and leaves once across the lifetime of the program. That gives amortized O(log n) per call despite the inner while loop.
• Compare to segment tree. Say "a dynamic segment tree with lazy propagation also works and generalizes to richer queries, but the sorted-map approach is simpler when the only query is point coverage."
• Test the boundary cases. Empty range structure, single interval, removing past the right edge, querying a range that exactly matches an interval.

Follow-up Questions#

1. Find the total covered length. Maintain a running sum of (end - start) updated incrementally on add and remove.
2. Count of disjoint intervals at any moment. That is just len(self.ranges).
3. Get the k-th covered point. Walk the sorted structure with running cumulative length.
4. Persistent version with snapshots. Use a persistent balanced BST or copy-on-write.
5. Concurrent updates from multiple writers. Add a lock per shard or use lock-free skip lists.
6. Generalize to weighted intervals. Replace the boolean coverage with an integer count and use a segment tree with lazy propagation to support "add 1 to range" and "query coverage at a point".

Key Takeaways#

• Maintain a sorted map of pairwise-disjoint, non-touching half-open intervals as the single source of truth — every operation preserves this invariant.
• addRange merges all overlapping or touching neighbors; removeRange deletes overlaps and re-inserts surviving fragments; queryRange checks just the predecessor.
• Amortized O(log n) per operation is achievable because each interval can only be created and destroyed once.
• Half-open semantics matter — touching intervals merge in addRange but do not require fragmentation in removeRange.
• The same disjoint-intervals scaffold powers feature flag systems, IP whitelists, GC free-lists, and time-series gap tracking.
• For richer queries (range counts, weighted coverage), upgrade to a segment tree with lazy propagation; for pure boolean coverage, the sorted map is simpler and faster.