352. Data Stream as Disjoint Intervals

352. Data Stream as Disjoint Intervals

Solved

Hard

Topics

Companies

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?

Accepted

101.6K

Submissions

169.7K

Acceptance Rate

59.8%

---

Seen this question in a real interview before?

1/4

Yes

No

---

Discussion (55)

---

Similar Questions

Summary Ranges

Easy

Find Right Interval

Medium

Range Module

Hard

Count Integers in Intervals

Hard

Copyright ©️ 2023 LeetCode All rights reserved

import bisect

class SummaryRanges:

  def __init__(self):
    self.intervals = []

  def addNum(self, val: int) -> None:
    idx = bisect.bisect_left(self.intervals, [val, val])
    
    # Assign start and end to val initially
    start, end = val, val

    # Check and merge with the previous interval if possible
    # [1, 2] <- [3, 3] (val = 3) => [1, 3]
    if (
      idx > 0 # (val, val) isn't gonna be the left-most interval
      and self.intervals[idx - 1][1] + 1 >= val # [1, *2/3/4*] + 1 >= 3
    ):
      idx -= 1 
      start = self.intervals[idx][0] # [*1*, 2]  => 1
      end = max(self.intervals[idx][1], val) # [1, *2*] vs (val = 3)  => 3
      self.intervals.pop(idx)  # remove the merged interval

    # Check and merge with the next interval(s) if possible
    # [1, 3] -> [4, 5] => [1, 5]
    while (
      idx < len(self.intervals) # (val, val) isn't gonna be the right-most interval
      and end + 1 >= self.intervals[idx][0] # [1, *3/4/5*] + 1 >= [*4*, 5]
    ):
      end = max(end, self.intervals[idx][1]) # [1, 3] -> [1, 5]
      self.intervals.pop(idx) # del [4, 5]
    
    # Insert the merged interval
    self.intervals.insert(idx, [start, end]) # add [1, 5]

  def getIntervals(self) -> list[list[int]]:
    return self.intervals