Module 5 · Advanced Intervals

Data Stream as Disjoint Intervals

HardProblem 12 of 12 10 min read ~35 min to solve LeetCode

IntervalsDesignTreeMapData StreamOrdered Set

Asked atGoogleAmazonMicrosoftMetaApple

Problem Statement

Design a SummaryRanges data structure that receives non-negative integers from a data stream. addNum(value) inserts one value. getIntervals() returns the current disjoint intervals covering all inserted values, sorted by start time.

Input

A constructor call SummaryRanges() followed by a sequence of addNum(value) and getIntervals() calls.

Output

For the constructor and addNum, output null. For getIntervals, output a two-dimensional array of disjoint intervals sorted by start.

Constraints

•0 <= value <= 10^4
•At most 3 * 10^4 calls will be made to addNum and getIntervals
•The output intervals must be disjoint and sorted by start

Examples

Example 1

Input:

operations = [SummaryRanges, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals], arguments = [[], [1], [], [3], [], [7], [], [2], [], [6], []]

Output: [null, null, [[1,1]], null, [[1,1],[3,3]], null, [[1,1],[3,3],[7,7]], null, [[1,3],[7,7]], null, [[1,3],[6,7]]]

Explanation: Adding 2 bridges [1,1] and [3,3] into [1,3]. Adding 6 extends left into [7,7], producing [6,7].

Example 2

Input:

operations = [SummaryRanges, addNum, addNum, addNum, getIntervals, addNum, getIntervals], arguments = [[], [5], [5], [4], [], [6], []]

Output: [null, null, null, null, [[4,5]], null, [[4,6]]]

Explanation: The duplicate 5 changes nothing. Adding 4 merges with the right-adjacent [5,5], and adding 6 extends the interval to [4,6].

Learning Objectives

Maintain a dynamic set of disjoint intervals as individual values arrive.
Use **TreeMap** predecessor and successor entries to detect containment and adjacency.
Coalesce left and right neighbours when a new value bridges two intervals.
Return intervals in sorted order directly from the ordered map.

Intuition

Pattern Recognition

The data stream signal means values arrive online, so sorting all values and rebuilding intervals after every insertion is wasteful. The interval signal means the stored state should be compressed: contiguous values become one [start,end] range, and the ranges must stay disjoint.

A TreeMap keyed by interval start gives exactly the neighbour queries needed for insertion. For a new value, the floor entry tells whether the value is already covered or touches the interval on the left. The ceiling entry tells whether it touches the interval on the right. Those two neighbours are the only intervals that can merge with a single inserted value.

Common mistakes

×Storing every value in a set and rebuilding all intervals on each **getIntervals()** call.
×Forgetting to ignore a duplicate value already covered by the floor interval.
×Extending the left interval but failing to merge the right interval when the value bridges both sides.
×Returning intervals in insertion order instead of sorted start order.

Algorithm Explanation

Key idea

Store disjoint intervals in a TreeMap as start -> end. On addNum(value), first check the floor interval. If its end is at least value, the value is already covered. Otherwise, the value may be adjacent to the floor interval, adjacent to the ceiling interval, both, or neither. Remove any adjacent neighbours and insert the coalesced interval.

Interval walkthrough

Start empty. After addNum(1), store {1 -> 1}. After addNum(3), the value is not adjacent to the left interval because 1 + 1 != 3, so store {1 -> 1, 3 -> 3}. Now addNum(2) sees floor [1,1] and ceiling [3,3]. Since 1 + 1 == 2 and 3 == 2 + 1, the new value bridges both neighbours. Remove starts 1 and 3, then insert 1 -> 3. Later addNum(7) creates {1 -> 3, 7 -> 7}, and addNum(6) merges with the right neighbour into {1 -> 3, 6 -> 7}.

Algorithm

Keep a TreeMap named intervals from start to end.
For addNum(value), read left = intervals.floorEntry(value).
If left exists and left.end >= value, the value is already covered, so return.
Read right = intervals.ceilingEntry(value).
Start a new interval [value,value].
If left.end + 1 == value, merge left by using left.start as the new start and removing the old left interval.
If right.start == value + 1, merge right by using right.end as the new end and removing the old right interval.
Insert the final coalesced interval.
For getIntervals(), iterate over intervals.entrySet() in order and copy each pair into the result array.

Solutions

Solution: TreeMap coalescing intervals

When to prefer this:

Use this when inserts are online and the output must remain a compact sorted set of disjoint intervals.

The TreeMap stores only interval boundaries, not every inserted value. Each insertion consults the immediate left and right intervals, because a single value can only connect to neighbours ending at value - 1 or starting at value + 1.

Step-by-step

Find the floor entry for value to detect duplicates or left adjacency.
If the floor interval already covers value, return without changing state.
Find the ceiling entry for possible right adjacency.
Begin with the singleton interval [value,value].
If the left interval ends at value - 1, remove it and reuse its start.
If the right interval starts at value + 1, remove it and reuse its end.
Insert the merged interval and let getIntervals() iterate the map in sorted order.

Time

addNum: O(log n), getIntervals: O(n)

Space

O(n)

n is the number of disjoint intervals. Each insertion performs constant many **TreeMap** neighbour queries, removals, and one insert.

Java implementation

Loading…

Dry Run

Sample input

Sequence of calls: addNum(1), addNum(3), addNum(7), addNum(2), getIntervals(), addNum(6), getIntervals().

call	TreeMap before	merge decision	output or state
addNum(1)	{}	no neighbours, insert singleton	{1 -> 1}
addNum(3)	{1 -> 1}	not adjacent to left, insert singleton	{1 -> 1, 3 -> 3}
addNum(7)	{1 -> 1, 3 -> 3}	no adjacent neighbours, insert singleton	{1 -> 1, 3 -> 3, 7 -> 7}
addNum(2)	{1 -> 1, 3 -> 3, 7 -> 7}	bridges [1,1] and [3,3]	{1 -> 3, 7 -> 7}
getIntervals()	{1 -> 3, 7 -> 7}	iterate in start order	[[1,3],[7,7]]
addNum(6)	{1 -> 3, 7 -> 7}	touches right interval [7,7]	{1 -> 3, 6 -> 7}
getIntervals()	{1 -> 3, 6 -> 7}	iterate in start order	[[1,3],[6,7]]

The inserted value can merge with at most two intervals: the one immediately to its left and the one immediately to its right. That is why a TreeMap neighbour query is enough to keep the whole summary compact.

Interview Tips

Make the invariant explicit: intervals in the map are always disjoint, sorted by start, and never adjacent after insertion, because adjacent intervals are immediately coalesced. When coding, handle duplicate containment before adjacency; otherwise adding a value already inside an interval can accidentally split or duplicate state.

Likely follow-ups

How would you support removing a number from the stream summary?
How would the design change if intervals were over long values instead of int values?
How would you optimize **getIntervals()** if it is called far more often than **addNum()**?
How would you make the structure safe for concurrent inserts and reads?

Key Takeaways

A stream of values can be compressed into disjoint intervals instead of stored as isolated points.
The floor interval detects duplicates and left adjacency.
The ceiling interval detects right adjacency.
A single inserted value can only merge with its immediate neighbours.

Reusable template: Dynamic interval coalescing: store disjoint ranges by start, use predecessor and successor to find containment or adjacency, then replace neighbours with one merged interval.