We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Data Stream as Disjoint Intervals

Difficulty: Hard

Problem 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 with methods to add numbers to the stream and return the summary of the integers in the stream as a list of disjoint intervals.

Key Insights

  • The problem requires maintaining a dynamic list of intervals as numbers are added.
  • Intervals must merge when consecutive numbers are added.
  • Efficiently managing the intervals is crucial due to the potential size of the data stream.

Space and Time Complexity

Time Complexity: O(log n) for adding a number and O(n) for retrieving intervals in the worst case. Space Complexity: O(n) for storing the intervals.

Solution

To solve the problem, we can use a sorted data structure (like a balanced binary search tree) to keep track of the intervals. When a new number is added:

  1. We check if it can extend existing intervals or create a new one.
  2. If it merges with existing intervals, we adjust the start and end points accordingly.
  3. The getIntervals method simply retrieves the intervals in their current state.

This approach ensures that we maintain disjoint intervals efficiently as new numbers are added.

Code Solutions

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

    def addNum(self, value: int) -> None:
        # Insert value into intervals
        new_intervals = []
        i = 0
        while i < len(self.intervals) and self.intervals[i][1] < value - 1:
            new_intervals.append(self.intervals[i])
            i += 1
        
        # Check for merging intervals
        if i < len(self.intervals) and self.intervals[i][0] <= value <= self.intervals[i][1] + 1:
            value = min(value, self.intervals[i][0])  # merge with the current interval
        else:
            new_intervals.append([value, value])  # create a new interval
            
        while i < len(self.intervals) and self.intervals[i][0] <= value + 1:
            value = max(value, self.intervals[i][1])  # merge with next intervals
            i += 1
        
        # Add merged interval
        new_intervals[-1][1] = value
        new_intervals.extend(self.intervals[i:])
        self.intervals = new_intervals

    def getIntervals(self) -> List[List[int]]:
        return self.intervals
← Back to All Questions