Data Stream as Disjoint Intervals — LeetCode 352 Python Solution
HardUnion FindDesignHash TableBinary SearchData StreamOrdered Set
- Problem
- #352
- Pattern
- Union-Find
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
- 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();
Python solution
Python
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()Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 352. Data Stream as Disjoint Intervals is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 352. Data Stream as Disjoint Intervals?
- LeetCode 352. Data Stream as Disjoint Intervals is rated Hard on LeetCode.
- What is the time complexity of LeetCode 352. Data Stream as Disjoint Intervals?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 352. Data Stream as Disjoint Intervals?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 352. Data Stream as Disjoint Intervals cover?
- LeetCode 352. Data Stream as Disjoint Intervals is tagged Union Find, Design, Hash Table, Binary Search, Data Stream and Ordered Set on LeetCode.