Data Stream as Disjoint Intervals: Sorted Interval Merging

LeetCode 352, Data Stream as Disjoint Intervals, asks you to design a data structure that accepts integers one at a time and can return the full list of covered intervals at any point. The addNum method takes a single integer from the stream. The getIntervals method returns all intervals covered so far as a sorted, disjoint list. For example, if you call addNum with 1, 3, 7, 2, 6 in that order, calling getIntervals afterward returns [[1,3],[6,7]]. What makes this problem interesting is the combination of streaming input and the merge-on-insert requirement: each new value can potentially collapse two separate intervals into one.

The approach

The core idea is to maintain a sorted list of disjoint intervals at all times. When a new number arrives, you need to check whether it overlaps or is adjacent to any existing intervals. Two intervals are considered adjacent if they share a boundary or are within 1 of each other. For example, if you have [1,3] and you add 4, the result is [1,4] because 4 is directly adjacent to 3.

To implement addNum(val), you start by treating the incoming number as a point interval [val, val]. Then you scan the sorted interval list for any interval that should be merged with the new point. An existing interval iv should be merged if iv[1] >= val - 1 (it ends at or after the value minus one) and iv[0] <= val + 1 (it starts at or before the value plus one). Any interval matching both conditions gets absorbed: you expand the new interval to cover the union, and remove the old one from the list.

Using SortedList from the sortedcontainers library (sorted by interval start) gives you an ordered structure you can iterate through efficiently. When scanning, you can break early once iv[0] exceeds val + 1, because all subsequent intervals start even further right and cannot overlap.

The code

from sortedcontainers import SortedList

class SummaryRanges:
    def __init__(self):
        self.intervals = SortedList(key=lambda x: x[0])

    def addNum(self, val: int) -> None:
        new = [val, val]
        to_remove = []
        for iv in self.intervals:
            if iv[0] > new[1] + 1:
                break
            if iv[1] >= new[0] - 1:
                new[0] = min(new[0], iv[0])
                new[1] = max(new[1], iv[1])
                to_remove.append(iv)
        for iv in to_remove:
            self.intervals.remove(iv)
        self.intervals.add(new)

    def getIntervals(self) -> list[list[int]]:
        return list(self.intervals)

Step-by-step walkthrough

Let's trace through the first few insertions to see exactly how the interval list evolves after each call.

The critical step is addNum(2). At that point the list contains [[1,1],[3,3]]. The value 2 is adjacent to both 1 (since 1 >= 2-1) and 3 (since 3 <= 2+1), so both existing intervals get collected in to_remove. The new merged interval becomes [min(2,1,3), max(2,1,3)] = [1,3]. Both point intervals are removed and [1,3] is inserted. That single insertion replaces two intervals with one.

Complexity analysis

The worst-case O(n) for addNum comes from the linear scan plus the removal of up to n intervals. In practice, each interval can only be merged and removed once across all insertions, so the total work across n calls is amortized O(n log n). Space is O(n) to store the interval list.

Building blocks

This problem is a natural extension of the classic Merge Intervals problem (LeetCode 56). In that problem, you receive the full list of intervals up front and merge them in a single sort-and-sweep pass. Here, intervals arrive one value at a time, so you cannot sort the whole input. Instead, you keep the merged list sorted at all times and merge on each insertion.

The key shift is from batch merging to incremental merging. Merge Intervals processes the whole list once and produces a result. Data Stream as Disjoint Intervals produces a valid result after every single insertion. That requires the sorted invariant to hold continuously, which is what SortedList provides.

The adjacency check (iv[1] >= val - 1) is also slightly different from the overlap check in Merge Intervals (start <= last[1]). Here you are also merging intervals that touch but do not overlap, so the threshold widens by one on each side.

Edge cases

• Duplicate values: if you add a number that is already covered by an existing interval, the scan finds that interval, the merge produces the same interval, the old one is removed, and the identical new one is inserted. The result is unchanged.
• Values that extend an interval on one side only: adding 8 to a list that contains [6,7] extends it to [6,8]. Only one interval matches the adjacency check, so only one merge happens.
• Values that bridge two previously separate intervals: adding 5 to a list that contains [1,4] and [6,9] merges both into [1,9]. Both intervals match the adjacency check (4 >= 5-1 and 6 <= 5+1), so both are collected and absorbed.
• Single value added: if the list is empty, the loop finds nothing to merge, and [val, val] is added as a point interval.

From understanding to recall

There are two decisions that determine whether you can reproduce this solution under pressure. The first is how to find adjacent intervals efficiently. A naive approach scans the whole list every time, which works but misses the early-break optimization. The insight is that once an interval starts past val + 1, no later interval in the sorted list can possibly overlap or be adjacent, so you can stop scanning immediately.

The second decision is how to merge in place. Modifying the list while iterating it is a common source of bugs. The pattern here collects candidates in to_remove, exits the loop, removes them one by one, then inserts the merged result. That sequence avoids mutation during iteration and keeps the SortedList consistent at every step.

These two decisions are the entire algorithm. Once you can articulate them, the code flows naturally. Spaced repetition helps you internalize both so you can reconstruct the solution from first principles rather than trying to remember specific lines of code. CodeBricks schedules reps at the right intervals so the pattern stays sharp without over-drilling.

Related posts

• Merge Intervals — batch merging of interval lists; the same merge logic in one pass
• Find Median from Data Stream — another stream design problem requiring an efficient sorted structure
• Summary Ranges — converting a sorted array into compact interval notation