Data Stream as Disjoint Intervals — Problem & Solution
Data Stream as Disjoint Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Data Stream as Disjoint Intervals is a hard coding problem on binary search and ordered set, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Binary Search, Ordered Set
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Non-negative integers arrive one at a time. At any moment, summarise the distinct numbers seen so far as a list of disjoint intervals: each interval [start, end] covers every integer from start to end, and no two intervals touch or overlap (so [1, 2] and [3, 3] would be one interval [1, 3]).
Write the class SummaryRanges:
SummaryRanges()starts with no numbers.void addNum(int value)addsvalueto the stream (it may have been seen before).int[][] getIntervals()returns the summary as a list of[start, end]pairs sorted bystart.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"]
[[],[4],[],[6],[],[10],[],[5],[],[9],[]]
Output: [null,null,[[4,4]],null,[[4,4],[6,6]],null,[[4,4],[6,6],[10,10]],null,[[4,6],[10,10]],null,[[4,6],[9,10]]]
Explanation: 4, 6 and 10 start as separate intervals. 5 joins [4, 4] and [6, 6] into [4, 6]; 9 extends [10, 10] to [9, 10].
Example 2
Input: ["SummaryRanges","getIntervals","addNum","addNum","addNum","getIntervals"]
[[],[],[10000],[0],[10000],[]]
Output: [null,[],null,null,null,[[0,0],[10000,10000]]]
Explanation: Before any number arrives the summary is empty. Adding 10000 a second time changes nothing.
Constraints
0 <= value <= 10^4At most 3 * 10^4 calls are made in total to addNum and getIntervalsAt most 10^2 calls are 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 stream?
Hints for Data Stream as Disjoint Intervals
Hint 1
Keep the intervals themselves, sorted by start, rather than the raw numbers.
Hint 2
A new value can only interact with two intervals: the last one starting at or before it, and the first one starting after it. Find them by binary search (or an ordered map's floor and higher entries).
Hint 3
Four cases: the value is already covered; it is adjacent to both neighbours (merge them); adjacent to one (extend it); or to neither (insert
[value, value]).
How to solve Data Stream as Disjoint Intervals
Maintain the summary itself — a sorted list of disjoint, non-adjacent intervals — and update it locally on each addition. Only the interval just before the value and the one just after it can absorb or be merged by the value.
Approach
- Let
ibe the index of the first interval whose start is greater thanvalue; the interval before it,i - 1, is the last one starting at or beforevalue. - If interval
i - 1exists and its end is>= value, the value is already covered — stop. - Let
leftbe whether intervali - 1ends atvalue - 1, andrightwhether intervalistarts atvalue + 1. - Both: set interval
i - 1's end to intervali's end and delete intervali. Onlyleft: set intervali - 1's end tovalue. Onlyright: set intervali's start tovalue. Neither: insert[value, value]at positioni. getIntervals()returns the list as it is.
Why it works
The list stays sorted, disjoint and non-adjacent: a covered value changes nothing; otherwise value lies strictly between the end of interval i - 1 and the start of interval i, so only those two can be adjacent to it, and each case joins exactly the intervals that value connects. Every other interval is at least two away from value and is untouched.
Complexity
- Time —
O(log k) to locate plus O(k) for an array insertion or deletion (O(log k) with a balanced ordered map), where k is the number of intervals; getIntervals is O(k) - Space —
O(k)
Pitfalls
- Repeated values must not create duplicate intervals — check whether the value is already covered first.
- Intervals that become adjacent (end + 1 == next start) must be merged; they are not allowed to sit side by side.
Reference solution
Python
from bisect import bisect_right
class SummaryRanges:
def __init__(self):
self.starts = [] # disjoint, non-adjacent intervals, sorted
self.ends = []
def addNum(self, value: int) -> None:
s, e = self.starts, self.ends
i = bisect_right(s, value) # first interval starting after value
if i > 0 and e[i - 1] >= value:
return # already covered
left = i > 0 and e[i - 1] == value - 1
right = i < len(s) and s[i] == value + 1
if left and right:
e[i - 1] = e[i]
del s[i]
del e[i]
elif left:
e[i - 1] = value
elif right:
s[i] = value
else:
s.insert(i, value)
e.insert(i, value)
def getIntervals(self) -> List[List[int]]:
return [[a, b] for a, b in zip(self.starts, self.ends)]Java
class SummaryRanges {
private TreeMap<Integer, Integer> iv = new TreeMap<>(); // start -> end, disjoint and non-adjacent
public SummaryRanges() {
}
public void addNum(int value) {
Map.Entry<Integer, Integer> lo = iv.floorEntry(value), hi = iv.higherEntry(value);
if (lo != null && lo.getValue() >= value) return; // already covered
boolean left = lo != null && lo.getValue() == value - 1;
boolean right = hi != null && hi.getKey() == value + 1;
if (left && right) {
iv.put(lo.getKey(), hi.getValue());
iv.remove(hi.getKey());
} else if (left) {
iv.put(lo.getKey(), value);
} else if (right) {
iv.remove(hi.getKey());
iv.put(value, hi.getValue());
} else {
iv.put(value, value);
}
}
public int[][] getIntervals() {
int[][] out = new int[iv.size()][];
int k = 0;
for (Map.Entry<Integer, Integer> e : iv.entrySet()) out[k++] = new int[]{e.getKey(), e.getValue()};
return out;
}
}C++
class SummaryRanges {
map<int, int> iv; // start -> end, disjoint and non-adjacent
public:
SummaryRanges() {}
void addNum(int value) {
auto hi = iv.upper_bound(value); // first interval starting after value
auto lo = hi == iv.begin() ? iv.end() : prev(hi);
if (lo != iv.end() && lo->second >= value) return; // already covered
bool left = lo != iv.end() && lo->second == value - 1;
bool right = hi != iv.end() && hi->first == value + 1;
if (left && right) {
lo->second = hi->second;
iv.erase(hi);
} else if (left) {
lo->second = value;
} else if (right) {
int e = hi->second;
iv.erase(hi);
iv[value] = e;
} else {
iv[value] = value;
}
}
vector<vector<int>> getIntervals() {
vector<vector<int>> out;
for (auto& p : iv) out.push_back({p.first, p.second});
return out;
}
};JavaScript
var SummaryRanges = function() {
this.starts = []; // disjoint, non-adjacent intervals, sorted
this.ends = [];
};
SummaryRanges.prototype.addNum = function(value) {
var s = this.starts, e = this.ends;
var lo = 0, hi = s.length; // first interval starting after value
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (s[mid] <= value) lo = mid + 1; else hi = mid;
}
var i = lo;
if (i > 0 && e[i - 1] >= value) return; // already covered
var left = i > 0 && e[i - 1] === value - 1;
var right = i < s.length && s[i] === value + 1;
if (left && right) { e[i - 1] = e[i]; s.splice(i, 1); e.splice(i, 1); }
else if (left) e[i - 1] = value;
else if (right) s[i] = value;
else { s.splice(i, 0, value); e.splice(i, 0, value); }
};
SummaryRanges.prototype.getIntervals = function() {
var out = [];
for (var i = 0; i < this.starts.length; i++) out.push([this.starts[i], this.ends[i]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search