Is Data Stream as Disjoint Intervals easy or hard?

Data Stream as Disjoint Intervals is classified as a Hard problem on LeetCode. The difficulty comes from designing a dynamic structure that supports incremental updates while keeping intervals sorted and merged efficiently.

Data Stream as Disjoint Intervals Python/Java solution

Python solutions typically maintain a sorted list of intervals and use binary search to locate the insertion point, followed by merging logic. Java and C++ solutions often use TreeMap or std::map to store interval boundaries, allowing efficient O(log n) updates and straightforward retrieval of intervals.

How to solve Data Stream as Disjoint Intervals in O(log n)?

Store intervals inside a balanced ordered map such as TreeMap. For each incoming value, find the closest interval on the left and right using floorKey or lower_bound. Merge intervals if the value connects them, extend one interval if adjacent, or insert a new interval entry. Each operation relies on O(log n) tree lookups and updates.

What is the best approach for Data Stream as Disjoint Intervals?

The most efficient approach uses a TreeMap or ordered map to store intervals by their starting value. Each insertion locates neighboring intervals using O(log n) operations such as floorKey or lower_bound. This allows you to merge or extend intervals without scanning the entire list, keeping updates efficient even for large streams.

Is Data Stream as Disjoint Intervals asked at Google/Amazon/Meta?

Data stream design and interval merging problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests knowledge of ordered maps, interval merging logic, and designing efficient update operations for streaming data structures.

What data structure is used in Data Stream as Disjoint Intervals?

The optimal solution uses an ordered map such as TreeMap in Java or std::map in C++. These structures maintain sorted keys and support logarithmic lookups for neighboring intervals. A simpler alternative stores intervals in a sorted array or list and merges them during insertion.

What is the time complexity of Data Stream as Disjoint Intervals?

Using a sorted array approach, addNum can take O(n) time because inserting or merging intervals may require shifting elements. With a TreeMap or balanced ordered map, insertion runs in O(log n) time while getIntervals requires O(n) to iterate through stored intervals. Space complexity for both approaches is O(n).

Description Solution Video 9:10

352. Data Stream as Disjoint Intervals

Hard60.8% acceptance2 companies

Given a data stream input of non-negative integers a₁, a₂, ..., a_n, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

SummaryRanges() Initializes the object with an empty stream.
void addNum(int value) Adds the integer value to the stream.
int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [start_i, end_i]. The answer should be sorted by start_i.

Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [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
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Constraints: