Last updated on October 9th, 2024 at 06:11 pm
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
Topics
Binary Search, Ordered Map
Level of Question
Hard
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]]
1. 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; };
2. 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<>(); }
3. 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 };
4. 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