Skip to content

352. Data Stream As Disjoint Intervals

Binary Search Design Ordered Set

Problem - Data Stream As Disjoint Intervals

Hard

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class SummaryRanges:

    def __init__(self):
        self.map = SortedDict()

    def addNum(self, value: int) -> None:
        n = len(self.map)
        right_index = self.map.bisect_right(value)
        left_index = n if right_index == 0 else right_index - 1

        keys = self.map.keys()
        values = self.map.values()

        if (right_index != n and left_index != n and 
                values[right_index][0] - 1 == value and values[left_index][1] + 1 == value):
            self.map[keys[left_index]][1] = self.map[keys[right_index]][1]
            self.map.pop(keys[right_index])
        elif left_index != n and values[left_index][1] + 1 >= value:
            self.map[keys[left_index]][1] = max(value, self.map[keys[left_index]][1])

        elif right_index != n and values[right_index][0] - 1 <= value:
            self.map[keys[right_index]][0] = min(value, self.map[keys[right_index]][0])

        else:
            self.map[value] = [value, value]

    def getIntervals(self) -> List[List[int]]:
        return list(self.map.values())


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 18 MB (45.11%)