352. Data Stream as Disjoint Intervals LeetCode Solution
In this guide, you will get 352. Data Stream as Disjoint Intervals LeetCode Solution with the best time and space complexity. The solution to Data Stream as Disjoint Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Data Stream as Disjoint Intervals
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.
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?
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
352. Data Stream as Disjoint Intervals LeetCode Solution in C++
class SummaryRanges {
public:
void addNum(int val) {
if (intervals.contains(val))
return;
const int lo = lowerKey(val);
const int hi = higherKey(val);
// {lo, intervals[lo][1]} + val + {hi, intervals[hi][1]} = {lo,
// intervals[hi][1]}
if (lo >= 0 && hi >= 0 && intervals[lo][1] + 1 == val && val + 1 == hi) {
intervals[lo][1] = intervals[hi][1];
intervals.erase(hi);
// {lo, intervals[lo][1]} + val = {lo, val}
// Prevent adding duplicate entry by using '>=' instead of '=='.
} else if (lo >= 0 && intervals[lo][1] + 1 >= val) {
intervals[lo][1] = max(intervals[lo][1], val);
} else if (hi >= 0 && val + 1 == hi) {
// val + {hi, intervals[hi][1]} = {val, intervals[hi][1]}
intervals[val] = {val, intervals[hi][1]};
intervals.erase(hi);
} else {
intervals[val] = {val, val};
}
}
vector<vector<int>> getIntervals() {
vector<vector<int>> res;
for (const auto& [_, interval] : intervals)
res.push_back(interval);
return res;
}
private:
map<int, vector<int>> intervals; // {start: (start, end)}
// Returns the maximum key in `intervals` < `key`.
int lowerKey(int key) {
auto it = intervals.lower_bound(key);
if (it == intervals.begin())
return -1;
return (--it)->first;
}
// Returns the minimum key in `intervals` > `key`.
int higherKey(int key) {
const auto it = intervals.upper_bound(key);
if (it == intervals.cend())
return -1;
return it->first;
}
}; /* code provided by PROGIEZ */
352. Data Stream as Disjoint Intervals LeetCode Solution in Java
class SummaryRanges {
public void addNum(int val) {
if (intervals.containsKey(val))
return;
// the maximum key in `intervals` < `key`
final Integer lo = intervals.lowerKey(val);
// the minimum key in `intervals` > `key`
final Integer hi = intervals.higherKey(val);
// {lo, intervals.get(lo)[1]} + val + {hi, intervals.get(hi)[1]} = {lo, intervals.get(hi)[1]}
if (lo != null && hi != null && intervals.get(lo)[1] + 1 == val && val + 1 == hi) {
intervals.get(lo)[1] = intervals.get(hi)[1];
intervals.remove(hi);
// {lo, intervals.get(lo)[1]} + val = {lo, val}
// Prevent adding duplicate entry by using '>=' instead of '=='.
} else if (lo != null && intervals.get(lo)[1] + 1 >= val) {
intervals.get(lo)[1] = Math.max(intervals.get(lo)[1], val);
// val + {hi, intervals.get(hi)[1]} = {val, intervals.get(hi)[1]}
} else if (hi != null && val + 1 == hi) {
intervals.put(val, new int[] {val, intervals.get(hi)[1]});
intervals.remove(hi);
} else {
intervals.put(val, new int[] {val, val});
}
}
public int[][] getIntervals() {
return intervals.values().stream().toArray(int[][] ::new);
}
// {start: (start, end)}
private TreeMap<Integer, int[]> intervals = new TreeMap<>();
} // code provided by PROGIEZ
352. Data Stream as Disjoint Intervals LeetCode Solution in Python
from sortedcontainers import SortedDict
class SummaryRanges:
def __init__(self):
self.intervals = SortedDict() # {start: (start, end)}
def addNum(self, val: int) -> None:
if val in self.intervals:
return
lo = self._lowerKey(val)
hi = self._higherKey(val)
# {lo, map[lo][1]} + val + {hi, map[hi][1]} = {lo, map[hi][1]}
if lo >= 0 and hi >= 0 and self.intervals[lo][1] + 1 == val and val + 1 == hi:
self.intervals[lo][1] = self.intervals[hi][1]
del self.intervals[hi]
# {lo, map[lo][1]} + val = {lo, val}
# Prevent adding duplicate entry by using '>=' instead of '=='.
elif lo >= 0 and self.intervals[lo][1] + 1 >= val:
self.intervals[lo][1] = max(self.intervals[lo][1], val)
elif hi >= 0 and val + 1 == hi:
# val + {hi, map[hi][1]} = {val, map[hi][1]}
self.intervals[val] = [val, self.intervals[hi][1]]
del self.intervals[hi]
else:
self.intervals[val] = [val, val]
def getIntervals(self) -> list[list[int]]:
return list(self.intervals.values())
def _lowerKey(self, key: int):
"""Returns the maximum key in `self.intervals` < `key`."""
i = self.intervals.bisect_left(key)
if i == 0:
return -1
return self.intervals.peekitem(i - 1)[0]
def _higherKey(self, key: int):
"""Returns the minimum key in `self.intervals` < `key`."""
i = self.intervals.bisect_right(key)
if i == len(self.intervals):
return -1
return self.intervals.peekitem(i)[0] # code by PROGIEZ
