Last updated on January 29th, 2025 at 02:12 am
Here, we see a Data Stream as Disjoint Intervals LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Binary Search, Ordered Map
Level of Question
Hard

Data Stream as Disjoint Intervals LeetCode Solution
Table of Contents
1. 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 integervalue
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 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]]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Merge Intervals”. This pattern is used to manage and merge overlapping or adjacent intervals efficiently. The goal is to maintain a collection of disjoint intervals and update them dynamically as new numbers are added.
3. Code Implementation in Different Languages
3.1 Data Stream as Disjoint Intervals C++
class SummaryRanges { public: SummaryRanges() { } void addNum(int value) { auto it = _map.lower_bound(value); bool merged = false; if(it != _map.begin()) { auto prev = it; --prev; if(prev->second + 1 >= value) { merged = true; prev->second = max(prev->second, value); } } if(it != _map.end()) { if(it->first - 1 <= value) { if(merged) { auto prev = it; --prev; if(prev->second >= it->first - 1) { prev->second = max(prev->second, it->second); _map.erase(it); } } else { merged = true; if(it->first != value) { pair<int, int> p = *it; p.first = min(p.first, value); it = _map.insert(it, p); ++it; if(it != _map.end()) _map.erase(it); } } } } if(!merged) _map.insert(it, {value, value}); } vector<vector<int>> getIntervals() { vector<vector<int>> intervals; for(auto const & p : _map) intervals.push_back({p.first, p.second}); return intervals; } map<int, int> _map; };
3.2 Data Stream as Disjoint Intervals Java
class SummaryRanges { public SummaryRanges() { } public void addNum(int val) { if (map.containsKey(val)) return; final Integer lo = map.lowerKey(val); final Integer hi = map.higherKey(val); if (lo != null && hi != null && map.get(lo)[1] + 1 == val && val + 1 == hi) { map.get(lo)[1] = map.get(hi)[1]; map.remove(hi); } else if (lo != null && map.get(lo)[1] + 1 >= val) { map.get(lo)[1] = Math.max(map.get(lo)[1], val); } else if (hi != null && val + 1 == hi) { map.put(val, new int[] {val, map.get(hi)[1]}); map.remove(hi); } else { map.put(val, new int[] {val, val}); } } public int[][] getIntervals() { List<int[]> intervals = new ArrayList<>(map.values()); return intervals.toArray(new int[intervals.size()][]); } // {start: {start, end}} private TreeMap<Integer, int[]> map = new TreeMap<>(); }
3.3 Data Stream as Disjoint Intervals JavaScript
var SummaryRanges = function() { this.arr = [] }; SummaryRanges.prototype.addNum = function(val) { let valIsInside = false; for(let i =0; i<this.arr.length;i++){ let [x,y] = this.arr[i]; if(val >=x && val<=y){ valIsInside = true; break; } else if(val === y + 1){ this.arr[i][1] = val; if(val + 1 === this.arr[i+1]?.[0]){ this.arr[i][1] = this.arr[i+1][1] this.arr.splice(i+1,1) } valIsInside = true; break; } else if(val < x){ if(val + 1 == x){ this.arr[i][0] = val; } else this.arr.splice(i,0,[val,val]) valIsInside = true; break; } } if(!valIsInside) this.arr.push([val,val]) }; SummaryRanges.prototype.getIntervals = function() { return this.arr };
3.4 Data Stream as Disjoint Intervals Python
class SummaryRanges: def __init__(self): self.nums = set() def addNum(self, value): self.nums.add(value) def getIntervals(self): intervals = [] start = None end = None for val in self.nums: if start is None: start = val end = val elif val - end == 1: end = val else: intervals.append([start, end]) start = end = val if start is not None: intervals.append([start, end]) return intervals
4. Time and Space Complexity
Space Complexity | |
C++ | O(n) |
Java | O(n) |
JavaScript | O(n) |
Python | O(n) |
- The C++ and Java implementations are the most efficient for
addNum
due to the use of balanced binary search trees (map
andTreeMap
). - The Python implementation is the least efficient for
getIntervals
due to the need to sort the set of numbers. - The JavaScript implementation is less efficient for
addNum
due to the linear search in the array.