Data Stream as Disjoint Intervals - Video Solutions

Problem Overview: You receive integers one by one from a data stream and must continuously summarize them as a list of disjoint sorted intervals. Each call to addNum(val) inserts a number, and getIntervals() returns the merged interval list representing all numbers seen so far.

Approach 1: Using a Sorted Array to Merge Intervals (Add: O(n), Get: O(1))

Maintain a sorted list of intervals such as [start, end]. When a new number arrives, use binary search to locate the position where the number belongs relative to existing intervals. After locating the position, check the neighboring intervals to see if the value should extend the left interval, merge two adjacent intervals, or form a new interval. Since arrays require shifting elements during insertion or merging, the worst-case time for addNum becomes O(n). Space complexity is O(n) for storing intervals.

This approach is straightforward and works well when the number of intervals is relatively small. The key insight is that the intervals remain sorted and disjoint at all times, so only adjacent intervals need to be inspected during insertion.

Approach 2: Using a TreeMap (or SortedMap) for Interval Management (Add: O(log n), Get: O(n))

A more scalable solution uses an ordered map where the key represents the interval start and the value represents the interval end. Structures like TreeMap in Java or map in C++ maintain sorted order automatically. For each incoming value, search for the closest intervals using map operations such as floorKey or lower_bound. These operations identify the nearest interval on the left and right.

Once those neighbors are located, decide whether the new value extends the left interval, connects two intervals, or creates a new interval entry. Map updates and lookups run in O(log n) time due to the balanced tree structure. Space complexity remains O(n). Retrieving intervals simply iterates over the map entries.

This design-focused solution leverages an ordered set or ordered map to maintain sorted intervals dynamically. It avoids costly array shifts and is more suitable when the stream grows large or updates are frequent.

Recommended for interviews: Interviewers typically expect the ordered map solution because it demonstrates understanding of design problems and balanced tree structures. Starting with the sorted-array merging idea shows clear reasoning about interval merging, but the TreeMap approach demonstrates stronger algorithmic maturity by reducing insertion cost from O(n) to O(log n).