Data Stream as Disjoint Intervals solution and explanation
Google
9 more videos on this problem
Data Stream as Disjoint Intervals - Leetcode 352 - PythonNeetCodeIO · 9:10 · 10K views
Leetcode 352 Data Stream as Disjoint Intervals | Amazon Google | SDE Sheet belowCoding Decoded · 12:37 · 1K views
352. Data Stream as Disjoint Intervals | English | HardSimple Code - 단순코드 · 14:43 · 1K views
Daily Leetcode #1033: Jan 28, 2023 - 352. Data Stream as Disjoint IntervalsProgramming Live with Larry · 20:12 · 451 views
352. Data Stream as Disjoint Intervals | LeetCode HardDeep Tech · 17:55 · 395 views
352. Data Stream as Disjoint Intervals (Leetcode Hard)Programming Live with Larry · 21:42 · 339 views
Leetcode 352 Data Stream as Disjoint Intervals (Java)TheAnalyticGuy · 10:32 · 319 views
Leetcode Question 352 "Data Stream as Disjoint Intervals" in JavaGhumman Tech · 11:08 · 207 views
LeetCode 352. Data Stream as Disjoint IntervalsJeevan Kumar - Cracckify · 7:12 · 92 views
Data Stream as Disjoint Intervals - Leetcode 352KuraCode · 24:23 · 80 views
The problem
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 integervalueto 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 bystarti.
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 * 104calls will be made toaddNumandgetIntervals. - At most
102calls will be made togetIntervals.
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.
class SummaryRanges:
def __init__(self):
self.intervals = []
def addNum(self, value: int) -> None:
for interval in self.intervals:
if interval[0] <= value <= interval[1]:
return
if interval[0] == value + 1:
interval[0] = value
self._merge()
return
if interval[1] == value - 1:
interval[1] = value
self._merge()
return
self.intervals.append([value, value])
self.intervals.sort()
def getIntervals(self) -> list:
return self.intervals
def _merge(self):
merged = []
for interval in self.intervals:
if not merged or merged[-1][1] < interval[0] - 1:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
self.intervals = mergedclass SummaryRanges {
constructor() {
this.intervals = [];
}
addNum(value) {
for (let interval of this.intervals) {
if (interval[0] <= value && value <= interval[1]) {
return;
}
if (interval[0] === value + 1) {
interval[0] = value;
this.merge();
return;
}
if (interval[1] === value - 1) {
interval[1] = value;
this.merge();
return;
}
}
this.intervals.push([value, value]);
this.intervals.sort((a, b) => a[0] - b[0]);
}
getIntervals() {
return this.intervals;
}
merge() {
let merged = [];
for (let interval of this.intervals) {
if (merged.length === 0 || merged[merged.length - 1][1] < interval[0] - 1) {
merged.push(interval);
} else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
}
}
this.intervals = merged;
}
}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.
Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)
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.
import java.util.TreeMap;
class SummaryRanges {
private TreeMap<Integer, Integer> intervals;
public SummaryRanges() {
intervals = new TreeMap<>();
}
public void addNum(int val) {
if (intervals.containsKey(val)) return;
Integer l = intervals.lowerKey(val);
Integer h = intervals.higherKey(val);
if (l != null && intervals.get(l) >= val - 1 && h != null && h == val + 1) {
intervals.put(l, intervals.get(h));
intervals.remove(h);
} else if (l != null && intervals.get(l) >= val - 1) {
intervals.put(l, Math.max(intervals.get(l), val));
} else if (h != null && h == val + 1) {
intervals.put(val, intervals.get(h));
intervals.remove(h);
} else {
intervals.put(val, val);
}
}
public int[][] getIntervals() {
int[][] res = new int[intervals.size()][2];
int index = 0;
for (int key : intervals.keySet()) {
res[index][0] = key;
res[index][1] = intervals.get(key);
index++;
}
return res;
}
}#include <map>
#include <vector>
using namespace std;
class SummaryRanges {
private:
map<int, int> intervals;
public:
SummaryRanges() {}
void addNum(int val) {
if (intervals.count(val)) return;
auto l = intervals.lower_bound(val);
auto h = intervals.upper_bound(val);
if (l != intervals.begin() && prev(l)->second >= val - 1) {
--l;
}
if (l != intervals.end() && l->second < val - 1) {
l = intervals.end();
}
int start = val, end = val;
if (l != intervals.end() && l->first <= val && l->second >= val) {
return;
}
if (l != intervals.end() && l->first <= val + 1) {
start = l->first;
intervals.erase(l);
}
if (h != intervals.end() && h->first <= val + 1) {
end = h->second;
intervals.erase(h);
}
intervals[start] = end;
}
vector<vector<int>> getIntervals() {
vector<vector<int>> res;
for (const auto& [key, val] : intervals) {
res.push_back({key, val});
}
return res;
}
};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.
Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)
Complexity comparison
| Approach | Complexity |
|---|---|
| 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). |
| Approach 2: Using a TreeMap (or SortedMap) for Interval Management | Time Complexity: O(log N) for add, where N is the number of intervals. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorted Array with Interval Merging | Add: O(n), Get: O(1) | O(n) | Good for simple implementations or when interval count is small |
| TreeMap / SortedMap Interval Management | Add: O(log n), Get: O(n) | O(n) | Best for large streams where efficient insertions are required |
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).