352. Data Stream as Disjoint Intervals

352

HardIntervals and Sweep LineBalanced BST / SortedDict keyed by interval startOrdered interval merge

Data Stream as Disjoint Intervals

Design a SummaryRanges data structure that ingests a stream of non-negative integers one at a time. addNum(value) records a seen integer, and getIntervals() returns the current set of seen numbers compressed into a sorted list of disjoint inclusive intervals [start, end].

Open official problem prompt ↗

In plain English

Keep a growing set of integers compressed at all times into the minimum number of disjoint sorted intervals, and answer that compressed view on demand.

Picture it like this

Think of booking seats in a row one by one. Each new seat either extends a block of already-taken seats, joins two blocks into one, or begins a new block. You never rescan the whole row; you just look at the seats immediately beside the one you took.

Example

Input: addNum(1), addNum(3), addNum(7), addNum(2), addNum(6), then getIntervals()
Output: [[1, 3], [6, 7]]
Why: Seen numbers are {1,2,3,6,7}; consecutive runs 1..3 and 6..7 collapse into two intervals.

Constraints

0 <= value <= 10^4At most 3 * 10^4 calls to addNum and getIntervalsgetIntervals may be called frequently, so keep it cheap

Pattern lesson

See the pattern, then code

Ordered interval merge

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Store intervals keyed by their start in sorted order. A new value can only touch its immediate left and right neighbors, so a single O(log n) lookup tells you whether to extend left, extend right, bridge both, or start a fresh singleton.

New words, made simpleKnow these before the algorithm

Disjoint intervals: Ranges that do not overlap and are not even adjacent, so they cannot be merged further
SortedDict: A dictionary kept in sorted key order, giving O(log n) neighbor lookups via bisect
Adjacency: Two integers a and b are adjacent when b == a + 1, which lets separate intervals fuse

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Boolean seen-set, rebuild on query

Too slow when getIntervals is called often, which the problem explicitly warns about.

Store every value in a set; on getIntervals, sort all values and coalesce runs.

Time O(1) addNum but O(n log n) per getIntervalsSpace O(n)

Best choiceSortedDict of intervals, merge on insert

Keeps the structure always-merged so queries are a cheap walk; this is the intended design.

Maintain merged intervals keyed by start; each addNum inspects only the two neighbors and merges in place.

Time O(log n) addNum, O(k) getIntervalsSpace O(n)

The rule we keep true

Invariant

After every addNum, the stored intervals are sorted, pairwise disjoint, and non-adjacent, meaning no two of them could be merged.

Why this is correct

Reasoning

Because the structure is always fully merged, a new value can only interact with the interval immediately to its left (does it end at value-1 or already contain value?) and the interval immediately to its right (does it start at value+1?). Handling those two neighbors restores the invariant, so correctness is preserved inductively.

The algorithm in three movesSay these aloud before coding

1Locate the insertion index of value among interval starts

d = {1:3, 7:7} before addNum(6)

2If value already lies inside the left interval or equals an existing start, ignore it

6+1 == 7 -> merge right

3Check adjacency: left interval ending at value-1, right interval starting at value+1

d = {1:3, 6:7}

4Merge with whichever neighbors are adjacent, otherwise insert [value, value]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,3]0

[6,7]3

1 · Readvalue=1

2 · AskAny adjacent interval?

3 · Update stated = {}

4 · ResultInsert singleton -> {1:1}

Key takeaway

Adding 6 fuses with the adjacent right interval [7,7] to form [6,7].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 10-11Locate neighbors
bisect_left finds where value would sit among interval starts, so idx-1 is the left interval and idx is the right one.
2
Lines 13-16Skip redundant values
If the left interval already reaches value, or an interval starts exactly at value, the number is already covered and nothing changes.
3
Lines 17-18Detect adjacency
merge_left is true when the left interval ends at value-1; merge_right when the right interval starts at value+1.
4
Lines 19-24Bridge both sides
When value fills the single-integer gap between two intervals, delete the right one and extend the left to the right's end.
5
Lines 25-34Extend one side or start fresh
Otherwise extend whichever neighbor is adjacent, or insert a brand-new singleton interval.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Repeated value already inside an interval must be a no-op
Value equal to an existing interval start
Value that bridges two intervals into one
First ever value on an empty structure

Common beginner mistakes

Using '>= value - 1' vs '>= value' incorrectly and either missing an adjacency or double-counting a covered value
Reading neighbor start/end after deleting from the SortedDict, since indices shift on deletion
Rebuilding intervals from scratch each getIntervals, which is too slow under heavy query load

Check your understanding

Why is it enough to inspect only the left and right neighbor of value instead of scanning all intervals?

PyPython 3 · solution.py

Optimal

1from sortedcontainers import SortedDict23class SummaryRanges:4    def __init__(self):5        self.d = SortedDict()  # start -> end67    def addNum(self, value: int) -> None:8        d = self.d9        keys = d.keys()10        idx = d.bisect_left(value)11        # Already covered by the interval on the left, or already a start12        if idx > 0 and d[keys[idx - 1]] >= value:13            return14        if idx < len(keys) and keys[idx] == value:15            return16        merge_left = idx > 0 and d[keys[idx - 1]] >= value - 117        merge_right = idx < len(keys) and keys[idx] == value + 118        if merge_left and merge_right:19            ls = keys[idx - 1]20            rs = keys[idx]21            re = d[rs]22            del d[rs]23            d[ls] = re24        elif merge_left:25            d[keys[idx - 1]] = value26        elif merge_right:27            rs = keys[idx]28            re = d[rs]29            del d[rs]30            d[value] = re31        else:32            d[value] = value3334    def getIntervals(self) -> list[list[int]]:35        return [[s, e] for s, e in self.d.items()]

Time complexityO(log n) per addNum, O(k) per getIntervalsOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMicrosoft

Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line