Skip to main content
Talentd

Data Stream as Disjoint Intervals - Solution & Explanation

HardBinary SearchDesignOrdered Set9 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

Given a data stream input of non-negative integers a1, a2, ..., an, 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 [starti, endi]. The answer should be sorted by starti.

 

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:

  • 0 <= value <= 104
  • At most 3 * 104 calls will be made to addNum and getIntervals.
  • At most 102 calls will be made to getIntervals.

 

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Approach Overview

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).

Approach 1: Approach 1: Using a Sorted Array to Merge Intervals

In this approach, maintain a sorted array of intervals and merge them appropriately as new numbers are added. When adding a new number, iterate through the intervals to find the potential merging points and update the intervals accordingly.

This Python solution maintains a list of intervals and updates it as new numbers are added. Each number is checked against existing intervals for possible merges.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)

Try this approach in the editor →

Approach 2: Approach 2: Using a TreeMap (or SortedMap) for Interval Management

This approach uses a data structure like TreeMap in Java or SortedDict in Python to maintain the intervals in sorted order. This provides efficient query and update operations which is essential for managing intervals dynamically.

The Java solution uses a TreeMap to efficiently maintain and update intervals. Each time a number is added, it checks for possible merges with adjacent intervals and updates the map accordingly.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using a Sorted Array to Merge Intervals

Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)

Approach 2: Using a TreeMap (or SortedMap) for Interval Management

Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorted Array with Interval MergingAdd: O(n), Get: O(1)O(n)Good for simple implementations or when interval count is small
TreeMap / SortedMap Interval ManagementAdd: O(log n), Get: O(n)O(n)Best for large streams where efficient insertions are required

Video Solution

Data Stream as Disjoint Intervals - Leetcode 352 - Python • NeetCodeIO • 10,464 views views

Watch 9 more video solutions →

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Data Stream as Disjoint Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Integers in Intervals

Next

Find Right Interval