LeetCode 0352. Data Stream as Disjoint Intervals Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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.

 

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]]

 

Constraints:

• 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?

Solutions

Solution 1

PythonJavaC++

class SummaryRanges: def __init__(self): self.mp = SortedDict() def addNum(self, val: int) -> None: n = len(self.mp) ridx = self.mp.bisect_right(val) lidx = n if ridx == 0 else ridx - 1 keys = self.mp.keys() values = self.mp.values() if ( lidx != n and ridx != n and values[lidx][1] + 1 == val and values[ridx][0] - 1 == val ): self.mp[keys[lidx]][1] = self.mp[keys[ridx]][1] self.mp.pop(keys[ridx]) elif lidx != n and val <= values[lidx][1] + 1: self.mp[keys[lidx]][1] = max(val, self.mp[keys[lidx]][1]) elif ridx != n and val >= values[ridx][0] - 1: self.mp[keys[ridx]][0] = min(val, self.mp[keys[ridx]][0]) else: self.mp[val] = [val, val] def getIntervals(self) -> List[List[int]]: return list(self.mp.values()) # # Your SummaryRanges object will be instantiated and called as such: # # obj = SummaryRanges() # # obj.addNum(val) # # param_2 = obj.getIntervals()(code-box)

class SummaryRanges { private TreeMap<Integer, int[]> mp; public SummaryRanges() { mp = new TreeMap<>(); } public void addNum(int val) { Integer l = mp.floorKey(val); Integer r = mp.ceilingKey(val); if (l != null && r != null && mp.get(l)[1] + 1 == val && mp.get(r)[0] - 1 == val) { mp.get(l)[1] = mp.get(r)[1]; mp.remove(r); } else if (l != null && val <= mp.get(l)[1] + 1) { mp.get(l)[1] = Math.max(val, mp.get(l)[1]); } else if (r != null && val >= mp.get(r)[0] - 1) { mp.get(r)[0] = Math.min(val, mp.get(r)[0]); } else { mp.put(val, new int[] {val, val}); } } public int[][] getIntervals() { int[][] res = new int[mp.size()][2]; int i = 0; for (int[] range : mp.values()) { res[i++] = range; } return res; } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */(code-box)

class SummaryRanges { private: map<int, vector<int>> mp; public: SummaryRanges() { } void addNum(int val) { auto r = mp.upper_bound(val); auto l = r == mp.begin() ? mp.end() : prev(r); if (l != mp.end() && r != mp.end() && l->second[1] + 1 == val && r->second[0] - 1 == val) { l->second[1] = r->second[1]; mp.erase(r); } else if (l != mp.end() && val <= l->second[1] + 1) l->second[1] = max(val, l->second[1]); else if (r != mp.end() && val >= r->second[0] - 1) r->second[0] = min(val, r->second[0]); else mp[val] = {val, val}; } vector<vector<int>> getIntervals() { vector<vector<int>> res; for (auto& range : mp) res.push_back(range.second); return res; } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */(code-box)