Range Module

Range Module is a design problem disguised as an intervals problem. You build a little data structure that can turn ranges of numbers on and off, and ask whether a whole range is currently on. The trick that makes every operation fast is the same one used by calendars and memory allocators: keep your intervals sorted and never overlapping.

The slow way first

The naive design stores a boolean for every individual number that has ever been on. addRange flips a flag for each number, queryRange scans every number in the range. If the coordinates can be up to a billion, that is O(range width) per call and hopeless on memory.

The question to ask: do I really need to track every number, or just where the on-regions begin and end? The answer is the boundaries. A region of consecutive on-numbers can be described by a single interval [start, end), so we only ever store a handful of intervals no matter how wide they are.

The idea: one sorted list of disjoint intervals

Keep a list of half-open intervals [start, end) that is always sorted by start and has no overlaps. Every operation preserves that invariant:

• addRange finds every existing interval the new range touches, takes the min start and max end of all of them, and replaces the whole bunch with one merged interval.
• removeRange walks the intervals and, for any that the hole cuts through, keeps the surviving left piece [start, lo) and right piece [hi, end) — that is how one interval can split into two.
• queryRange binary-searches for the single interval that could contain lo, then checks whether that interval covers [lo, hi) entirely.

Walk through it

Step through the animation. We add [10, 20), then a disjoint [25, 30), then [18, 26) which overlaps both and merges them into [10, 30). A queryRange(14, 16) lands inside that interval, so it returns True. Finally removeRange(15, 22) carves a hole out of the middle, splitting [10, 30) into [10, 15) and [22, 30). Notice the list stays sorted and disjoint after every step.

Pseudocode

state: ranges = sorted list of disjoint [start, end)
 
addRange(lo, hi):
    absorb every interval that overlaps [lo, hi]
    replace them with [min start, max end]
 
queryRange(lo, hi):
    i = binary search for the interval whose start <= lo
    return that interval exists and covers [lo, hi)
 
removeRange(lo, hi):
    keep each interval part that lies before lo
    keep each interval part that lies at or after hi
    (an interval straddling the hole splits into two)

The Python solution

class RangeModule:
    def __init__(self):
        self.ranges = []          # sorted [start, end)
 
    def addRange(self, lo, hi):
        merged = absorb_overlaps(self.ranges, lo, hi)
        self.ranges = insert_sorted(merged)  # one merged interval
 
    def queryRange(self, lo, hi):
        i = bisect_right(self.ranges, lo)     # candidate interval
        return i > 0 and self.ranges[i - 1].covers(lo, hi)
 
    def removeRange(self, lo, hi):
        before = clip_left(self.ranges, lo)   # keep parts < lo
        after = clip_right(self.ranges, hi)   # keep parts >= hi
        self.ranges = before + after          # split around the hole

• self.ranges is the single source of truth: a list of [start, end) pairs, always sorted by start and never overlapping.
• addRange absorbs every interval that touches [lo, hi] and reinserts one merged interval spanning the combined min start to max end.
• queryRange uses binary search (bisect_right) to jump straight to the only interval that could contain lo, then checks start <= lo and hi <= end — an O(log n) lookup, not a scan.
• removeRange keeps the part of each interval that survives on each side of the hole; an interval the hole passes through contributes both a left and a right piece, which is the split.

Complexity

Here n is the number of intervals, not the size of the coordinate space — so the structure stays tiny even when the numbers run into the billions. That is the whole payoff of storing boundaries instead of individual numbers.

When this pattern shows up

Practice