NUHMAN.com

🧩 Problem Statement

Given a data stream of non-negative integers nums coming in non-decreasing order, your task is to summarize the numbers seen so far as a list of disjoint intervals.

Implement a class SummaryRanges:

• void addNum(int value) adds a new number to the data stream.
• int[][] getIntervals() returns a list of disjoint intervals [start, end] in sorted order.

🔢 Example

python

Input:
["SummaryRanges", "addNum", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [3], [], [2], []]

Output:
[null, null, null, [[1, 1], [3, 3]], null, [[1, 3]]]

✅ Constraints

• 0 <= value <= 10⁴
• At most 3 * 10⁴ calls will be made to addNum and getIntervals.

💡 Intuition

The core idea is to merge intervals on-the-fly:

• When adding a number, we must:
• Check if it extends an existing interval.
• Check if it bridges two intervals.
• Otherwise, create a new interval.

A balanced BST or sorted list structure is ideal for this.

✅ Python Solution Using SortedDict from sortedcontainers

This approach uses a sorted map (start → [start, end]) for efficient merging and lookups.

📦 You’ll need to install the sortedcontainers library:

pip install sortedcontainers

🐍 Python Code

python

from sortedcontainers import SortedDict

class SummaryRanges:

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

    def addNum(self, value: int) -> None:
        intervals = self.intervals
        if value in intervals:
            return

        # Find neighboring intervals
        left = intervals.bisect_left(value) - 1
        right = intervals.bisect_right(value)

        # Merge logic
        leftInterval = intervals.peekitem(left)[1] if left >= 0 else None
        rightInterval = intervals.peekitem(right)[1] if right < len(intervals) else None

        if leftInterval and leftInterval[1] + 1 >= value and (not rightInterval or rightInterval[0] > value + 1):
            # Extend left interval
            leftInterval[1] = max(leftInterval[1], value)
        elif rightInterval and rightInterval[0] - 1 == value and (not leftInterval or leftInterval[1] < value - 1):
            # Extend right interval
            new_start = value
            new_end = rightInterval[1]
            del intervals[rightInterval[0]]
            intervals[new_start] = [new_start, new_end]
        elif leftInterval and rightInterval and leftInterval[1] + 1 == value and rightInterval[0] - 1 == value:
            # Merge left and right intervals
            new_start = leftInterval[0]
            new_end = rightInterval[1]
            del intervals[rightInterval[0]]
            intervals[new_start][1] = new_end
        else:
            # Insert new interval
            intervals[value] = [value, value]

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

🔍 Step-by-Step Example

python

sr = SummaryRanges()
sr.addNum(1)      # -> [[1, 1]]
sr.addNum(3)      # -> [[1, 1], [3, 3]]
sr.getIntervals() # -> [[1, 1], [3, 3]]
sr.addNum(2)      # -> [[1, 3]]
sr.getIntervals() # -> [[1, 3]]

🔧 Internal Logic Summary

• Use a SortedDict to maintain sorted intervals.
• When value is added:
• Check left/right neighbors.
• Merge accordingly:
• Extend left
• Extend right
• Merge both
• Or insert as new

⏱️ Time & Space Complexity

OperationComplexityaddNumO(log n)getIntervalsO(n)SpaceO(n)

✅ Conclusion

LeetCode 352: Data Stream as Disjoint Intervals is a classic online interval merging problem. It trains you in:

• Maintaining sorted structures efficiently
• Handling overlapping/adjacent ranges
• Real-time data stream processing

This approach is highly useful in scenarios like:

• Merging video segments
• Ranges of active users
• Detecting activity spikes over time