Here, We see Data Stream as Disjoint Intervals LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Data Stream as Disjoint Intervals LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Data Stream as Disjoint Intervals LeetCode Solution
Table of Contents
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]]
Data Stream as Disjoint Intervals LeetCode Solution 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;
};
Code language: PHP (php)
Data Stream as Disjoint Intervals LeetCode Solution 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<>();
}
Code language: PHP (php)
Data Stream as Disjoint Intervals LeetCode Solution 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
};
Code language: JavaScript (javascript)
Data Stream as Disjoint Intervals LeetCode Solution 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