LeetCode Solutions Blog

Data Stream as Disjoint Intervals

Number: 352

Difficulty: Hard

Paid? No

Problem Description

Design a data structure that receives a stream of non-negative integers and maintains a summary of the numbers seen so far as a list of disjoint intervals. You must be able to add a number to the stream and report the current list of intervals, merging intervals when necessary.

Key Insights

Keep intervals sorted by their start values to efficiently locate where a new number fits.
Use binary search (or an ordered container) to quickly find the intervals adjacent to the inserted number.
Carefully merge the new number with neighboring intervals if they are contiguous or overlapping.
Maintaining a sorted structure minimizes the work needed during getIntervals calls.

Space and Time Complexity

Time Complexity:

addNum: O(N) in the worst-case scenario when merging intervals (where N is the number of intervals), but typically much faster using binary search.
getIntervals: O(1) if simply returning the maintained list.

Space Complexity: O(N) for storing the list of intervals.

Solution

The solution involves maintaining a sorted list (or a balanced tree set) of intervals. When a new number is added:

Use binary search to locate the position where the new number would fit.
Check if the new number is already covered by an existing interval.
Determine if it is adjacent to (or can extend) an interval on the left, on the right, or possibly both.
Merge intervals if necessary. The process ensures that at any moment, the intervals list remains non-overlapping and sorted. This approach allows efficient updates as well as fast retrieval of the intervals.

Code Solutions

class SummaryRanges:
    def __init__(self):
        # maintain list of intervals as [start, end]
        self.intervals = []
    
    def addNum(self, value: int) -> None:
        intervals = self.intervals
        n = len(intervals)
        newInterval = [value, value]
        # find the position to insert using binary search
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if intervals[mid][0] < value:
                left = mid + 1
            else:
                right = mid
        pos = left
        # Check if value is already in an interval (merge if inside any current range)
        if pos > 0 and intervals[pos-1][1] >= value:
            return
        # Check if merge with the left interval: adjacent?
        if pos > 0 and intervals[pos-1][1] + 1 == value:
            newInterval[0] = intervals[pos-1][0]
            pos -= 1
        # Merge with right intervals if adjacent or overlapping
        while pos < len(intervals) and intervals[pos][0] - 1 <= value:
            newInterval[1] = max(newInterval[1], intervals[pos][1])
            del intervals[pos]
        # Insert the new merged interval in the proper position
        if pos < len(intervals):
            intervals.insert(pos, newInterval)
        else:
            intervals.append(newInterval)

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

# Example usage:
# summaryRanges = SummaryRanges()
# summaryRanges.addNum(1)
# print(summaryRanges.getIntervals())  # Output: [[1, 1]]
# summaryRanges.addNum(3)
# print(summaryRanges.getIntervals())  # Output: [[1, 1], [3, 3]]
# summaryRanges.addNum(7)
# print(summaryRanges.getIntervals())  # Output: [[1, 1], [3, 3], [7, 7]]
# summaryRanges.addNum(2)
# print(summaryRanges.getIntervals())  # Output: [[1, 3], [7, 7]]
# summaryRanges.addNum(6)
# print(summaryRanges.getIntervals())  # Output: [[1, 3], [6, 7]]