Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals is a design problem: numbers arrive one at a time, and at any moment you must be able to report them as a tidy list of non-overlapping ranges. The trick is to keep that list sorted and merged as you insert, so reporting is free.

The slow way first

The lazy approach: just dump every number into a set, and rebuild the intervals from scratch every time getIntervals is called by sorting and scanning. That makes getIntervals cost O(n log n) every single call, which is wasteful when the stream is long and you query often.

The better question: what if I keep the answer correct at all times? If the interval list is always sorted and disjoint, then getIntervals is just a return statement, and all the work moves into addNum.

The idea: merge on insert

Keep intervals as a list sorted by start. When a new value arrives, walk the list and sort each existing interval into one of three buckets relative to the new point: it ends before the new value, it starts after the new value, or it touches (overlaps or is adjacent to) the new value. Anything that touches gets absorbed by expanding the new interval to cover it.

Because we process intervals in sorted order, the result we build is itself sorted and disjoint with no extra cleanup.

Walk through it

Step through the animation. Slots 1, 3, and 7 turn on as separate intervals. When 2 arrives it sits between 1 and 3: its left neighbor ends at 1 and its right neighbor starts at 3, so both touch it. We absorb both, fusing them with 2 into [1, 3]. The set shrinks from three intervals to two.

Pseudocode

addNum(val):
    new = [val, val]
    merged = []
    placed = false
    for each [s, e] in intervals (sorted by start):
        if e < val - 1:                 # ends strictly before new
            keep [s, e]
        else if s > val + 1:            # starts strictly after new
            if new not yet placed: add new; placed = true
            keep [s, e]
        else:                           # overlaps or is adjacent
            new = [min(s, new.start), max(e, new.end)]
    if new not yet placed: add new
    intervals = merged
 
getIntervals(): return intervals

The Python solution

class SummaryRanges:
    def __init__(self):
        self.intervals = []  # sorted, disjoint [start, end]
 
    def addNum(self, val):
        new = [val, val]
        merged, placed = [], False
        for s, e in self.intervals:
            if e < new[0] - 1:          # interval ends before new
                merged.append([s, e])
            elif s > new[1] + 1:        # interval starts after new
                if not placed: merged.append(new); placed = True
                merged.append([s, e])
            else:                       # overlaps/adjacent -> absorb
                new = [min(s, new[0]), max(e, new[1])]
        if not placed: merged.append(new)
        self.intervals = merged
 
    def getIntervals(self):
        return self.intervals

• new starts as the single-point interval [val, val] and grows as it absorbs neighbors.
• e < new[0] - 1 means the stored interval finishes with a gap before the new value — it is fully to the left, so keep it untouched.
• s > new[1] + 1 means the stored interval starts with a gap after the new value — it is fully to the right, so first drop new into place (once), then keep it.
• The else branch is the adjacent or overlapping case: stretch new to cover the stored interval with min/max.
• If we finished the loop without placing new (it belongs at the end), we append it last.
• getIntervals simply returns the list, which is always kept sorted and disjoint.

Complexity

The simple list scan is O(n) per addNum. With an ordered map (or SortedList) you can binary-search the two neighbors and merge only those, dropping addNum to O(log n) — the version interviewers love to hear about.

When this pattern shows up

Practice