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 <= 1043 * 104 calls will be made to addNum and getIntervals.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?
In this approach, maintain a sorted array of intervals and merge them appropriately as new numbers are added. When adding a new number, iterate through the intervals to find the potential merging points and update the intervals accordingly.
This Python solution maintains a list of intervals and updates it as new numbers are added. Each number is checked against existing intervals for possible merges.
JavaScript
Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)
This approach uses a data structure like TreeMap in Java or SortedDict in Python to maintain the intervals in sorted order. This provides efficient query and update operations which is essential for managing intervals dynamically.
The Java solution uses a TreeMap to efficiently maintain and update intervals. Each time a number is added, it checks for possible merges with adjacent intervals and updates the map accordingly.
C++
Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)
| Approach | Complexity |
|---|---|
| Approach 1: Using a Sorted Array to Merge Intervals | Time Complexity: O(N), where N is the number of intervals (after all numbers are added). |
| Approach 2: Using a TreeMap (or SortedMap) for Interval Management | Time Complexity: O(log N) for add, where N is the number of intervals. |
Data Stream as Disjoint Intervals - Leetcode 352 - Python • NeetCodeIO • 8,040 views views
Watch 9 more video solutions →Practice Data Stream as Disjoint Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor