Data Stream as Disjoint Intervals — Data Structures & Algorithms

Problem Statement

Given a stream of integers, maintain a summary of the numbers seen so far as a list of disjoint intervals. Implement:

addNum(value) — record a new value.
getIntervals() — return the current disjoint interval list in sorted order.

Input

Sequential calls to addNum(value) with integer values, interleaved with calls to getIntervals().

Example call sequence

addNum(1)
addNum(3)
addNum(7)
addNum(2)
addNum(6)

Output

Each call to getIntervals() returns the current disjoint set of integer ranges.

Expected interval state after each call

addNum(1) → [[1,1]]
addNum(3) → [[1,1],[3,3]]
addNum(7) → [[1,1],[3,3],[7,7]]
addNum(2) → [[1,3],[7,7]]     (1, 2, 3 merge into one range)
addNum(6) → [[1,3],[6,7]]

Constraints

0 ≤ value ≤ 10⁴
At most 3·10⁴ calls split between addNum and getIntervals.

Intuition

Use binary search to locate where the new value fits in the sorted interval list, then check up to two neighbours:

Merge left when value − 1 ≤ left.end (value extends or sits inside the left interval).
Merge right when value + 1 ≥ right.start (value extends or sits inside the right interval).

Four cases fall out — merge both, merge left only, merge right only, or insert a new singleton [value, value].

Four cases at a glance

Case A — both   [..x] <- value -> [y..]   →  collapse into [.., y..]
Case B — left   [..x] <- value              →  extend end of left
Case C — right             value -> [y..]   →  extend start of right
Case D — none              value            →  insert [value, value]

Solution

data_stream.py

import bisect
 
class SummaryRanges:
    def __init__(self):
        self.intervals = []
 
    def addNum(self, value: int) -> None:
        intervals = self.intervals
        idx = bisect.bisect_left(intervals, [value, value])
 
        merge_l = idx > 0 and intervals[idx-1][1] >= value - 1
        merge_r = idx < len(intervals) and intervals[idx][0] <= value + 1
 
        if merge_l and merge_r:
            intervals[idx-1][1] = max(intervals[idx-1][1], intervals[idx][1])
            intervals.pop(idx)
        elif merge_l:
            intervals[idx-1][1] = max(intervals[idx-1][1], value)
        elif merge_r:
            intervals[idx][0] = min(intervals[idx][0], value)
        else:
            intervals.insert(idx, [value, value])
 
    def getIntervals(self):
        return self.intervals

data_stream.ts

class SummaryRanges {
    private intervals: number[][] = [];
 
    addNum(value: number): void {
        const iv = this.intervals;
        // Binary search for insertion point
        let lo = 0, hi = iv.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (iv[mid][0] < value) lo = mid + 1;
            else hi = mid;
        }
        const idx = lo;
 
        const mergeL = idx > 0 && iv[idx - 1][1] >= value - 1;
        const mergeR = idx < iv.length && iv[idx][0] <= value + 1;
 
        if (mergeL && mergeR) {
            iv[idx - 1][1] = Math.max(iv[idx - 1][1], iv[idx][1]);
            iv.splice(idx, 1);
        } else if (mergeL) {
            iv[idx - 1][1] = Math.max(iv[idx - 1][1], value);
        } else if (mergeR) {
            iv[idx][0] = Math.min(iv[idx][0], value);
        } else {
            iv.splice(idx, 0, [value, value]);
        }
    }
 
    getIntervals(): number[][] {
        return this.intervals;
    }
}

Complexity

Metric	Value	Reason
`addNum`	`O(n)`	Binary search is `O(log n)`, but `insert` / `pop` is `O(n)`. Replace the list with a `SortedList` for `O(log n)` per call.
`getIntervals`	`O(n)`	Returns the stored list directly

Edge Case Thinking

Scenario	Handling
Duplicate values — `addNum(5)` twice	Second call finds 5 already inside an existing interval → no change.
Sequential values — `1, 2, 3`	Each merges with the previous → final state is `[[1,3]]`.
Bridging a gap — state `[[1,1],[3,3]]` + `addNum(2)`	Both neighbours merge into `[[1,3]]`.
Insert at the very start or end	Only one of `merge_l` / `merge_r` is even reachable; the other branch short-circuits safely.
Empty list on first `addNum`	`idx = 0`, both neighbours out of bounds → Case D inserts the singleton.