LeetCode 352: Data Stream as Disjoint Intervals Solution in Python – A Step-by-Step Guide

What Is LeetCode 352: Data Stream as Disjoint Intervals?

LeetCode 352: Data Stream as Disjoint Intervals is a problem where you build a class to handle a stream of integers. You add numbers one by one, and the class tracks them as non-overlapping (disjoint) intervals. For example, adding 1 creates [1,1], adding 4 creates [1,1],[4,4], and adding 3 merges into [1,1],[3,4]. At any point, you can request the current intervals. It’s a real-time range-tracking puzzle!

Problem Statement

• Class: SummaryRanges
• Methods:
• __init__(): Initialize the data structure.
• addNum(val): Add integer val to the stream, updating intervals.
• getIntervals(): Return a list of current disjoint intervals.
• Rules:
• Intervals are sorted and non-overlapping.
• Each interval is a list [start, end] where start <= end.

Constraints

• 0 <= val <= 10⁴
• At most 3 * 10⁴ calls to addNum and getIntervals.
• Total values in stream ≤ 3 * 10⁴.

Examples

• Input: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"], [[], [1], [], [3], [], [4], []]
• Output: [null, null, [[1,1]], null, [[1,1],[3,3]], null, [[1,1],[3,4]]]
• Input: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals"], [[], [1], [], [2], []]
• Output: [null, null, [[1,1]], null, [[1,2]]]

These show how intervals form and merge—let’s solve it!

Understanding the Problem: Tracking Disjoint Intervals

To tackle LeetCode 352 in Python, we need a class that: 1. Stores numbers as disjoint intervals. 2. Updates intervals when a new number arrives (merging if needed). 3. Returns the current intervals on demand.

A simple idea might be to keep a list of numbers and sort them each time, but that’s slow. Instead, we’ll use:

• Best Solution: Sorted dictionary—O(log n) per addNum, O(n) for getIntervals—fast and scalable.
• Alternative Solution: List with merging—O(n) per addNum, O(1) for getIntervals—simpler but slower.

Let’s explore the sorted dictionary solution—it’s the efficiency champ!

Best Solution: Sorted Dictionary

Why This Is the Best Solution

The sorted dictionary approach (using Python’s SortedDict from the sortedcontainers library) is the best because it offers O(log n) time for addNum—thanks to binary search-like operations—and O(n) for getIntervals. It keeps intervals sorted by start value, making it easy to find and merge overlapping ranges. It’s like having a smart organizer for your intervals!

How It Works

Think of this as managing a filing cabinet:

• Setup: Use a SortedDict where keys are interval start values, and values are end values.
• Add Number:
• Find the closest intervals before and after the new value.
• Merge with them if they overlap or are adjacent (e.g., [1,2] and 3 become [1,3]).
• Update the dictionary.
• Get Intervals: Convert the dictionary into a list of [start, end] pairs.

It’s like slotting numbers into the right folders and combining them when they touch!

Step-by-Step Example

For calls: addNum(1), getIntervals(), addNum(3), getIntervals(), addNum(4), getIntervals():

• Init: intervals = SortedDict()
• addNum(1):
• No intervals yet, add [1,1], intervals = {1: 1}.
• getIntervals(): [[1,1]].
• addNum(3):
• Check before (1:1), after (none).
• 1 to 3 gap > 1, no merge, add [3,3], intervals = {1: 1, 3: 3}.
• getIntervals(): [[1,1],[3,3]].
• addNum(4):
• Before (3:3), after (none).
• 3 to 4 gap = 1, merge, update to [3,4], intervals = {1: 1, 3: 4}.
• getIntervals(): [[1,1],[3,4]].

Let’s code it with a clear breakdown!

Code with Explanation

Here’s the Python code using SortedDict:

Copy codefrom sortedcontainers import SortedDict

class SummaryRanges:
    def __init__(self):
        # Initialize a sorted dictionary to store intervals
        # Key = start of interval, Value = end of interval
        self.intervals = SortedDict()

    def addNum(self, val: int) -> None:
        # Find intervals just before and after val
        keys = list(self.intervals.keys())
        left_idx = -1
        right_idx = len(keys)

        # Binary search to find left neighbor
        for i, key in enumerate(keys):
            if key > val:
                right_idx = i
                break
            left_idx = i

        # Get left and right interval boundaries
        left_end = self.intervals[keys[left_idx]] if left_idx >= 0 else -2
        right_start = keys[right_idx] if right_idx < len(keys) else val + 2

        # Case 1: Val fits inside an existing interval
        if left_idx >= 0 and left_end >= val:
            return  # No change needed

        # Case 2: Merge with left, right, or both
        new_start = val
        new_end = val

        # Merge with left if adjacent or overlapping
        if left_end + 1 >= val:
            new_start = keys[left_idx]
            del self.intervals[keys[left_idx]]
        else:
            new_start = val

        # Merge with right if adjacent or overlapping
        if val + 1 >= right_start:
            new_end = self.intervals[keys[right_idx]]
            del self.intervals[keys[right_idx]]
        else:
            new_end = val

        # Add the merged (or new) interval
        self.intervals[new_start] = new_end

    def getIntervals(self) -> List[List[int]]:
        # Convert dictionary to list of [start, end] pairs
        return [[start, end] for start, end in self.intervals.items()]

Explanation

• Lines 1-2: Import SortedDict—a dictionary that keeps keys sorted.
• Lines 5-7: __init__
• Create intervals, a SortedDict. Keys are interval starts, values are ends (e.g., {1: 2} means [1,2]).

• Lines 9-38: addNum
• Lines 11-17: Find neighbors:
• Get all start keys as a list.
• Loop to find the first key > val (right neighbor) and the last key ≤ val (left neighbor).
• left_idx is the index of the left neighbor, right_idx is the right neighbor (or beyond).
• Lines 19-20: Get boundaries:
• left_end: End of left interval (or -2 if none).
• right_start: Start of right interval (or val+2 if none).
• Lines 23-24: If val is already in an interval (e.g., [1,3] and val=2), do nothing.
• Lines 27-38: Merge or add:
• Start with new_start = val, new_end = val (solo interval).
• If left_end + 1 >= val (e.g., [1,2] and 3), merge left: use left’s start, delete old interval.
• If val + 1 >= right_start (e.g., 3 and [4,5]), merge right: use right’s end, delete old interval.
• Add the new or merged interval to intervals.

• Lines 40-42: getIntervals
• Loop over intervals items, return each [start, end] as a list.

• Time Complexity:
• addNum: O(log n) for dictionary operations (insert/delete).
• getIntervals: O(n) to list all intervals.
• Space Complexity: O(n)—stores at most n/2 intervals.

This is like a dynamic interval organizer—fast and neat!

Alternative Solution: List with Merging

Why an Alternative Approach?

The list-based solution keeps intervals in a sorted list and merges them manually. It’s O(n) per addNum due to scanning and merging, and O(1) for getIntervals. It’s simpler to understand but slower for frequent additions—good for learning the basics!

How It Works

• Setup: Store intervals as a list of [start, end] pairs.
• Add Number:
• Insert the new value as [val, val].
• Sort and merge overlapping/adjacent intervals.
• Get Intervals: Return the list directly.

It’s like sorting and combining cards each time!

Step-by-Step Example

For addNum(1), addNum(3), addNum(4):

• Init: intervals = []
• addNum(1): Add [1,1], intervals = [[1,1]].
• addNum(3): Add [3,3], sort, no merge, intervals = [[1,1],[3,3]].
• addNum(4): Add [4,4], sort, merge [3,3] and [4,4], intervals = [[1,1],[3,4]].

Code with Explanation

Copy codeclass SummaryRanges:
    def __init__(self):
        # Initialize a list to store intervals
        self.intervals = []

    def addNum(self, val: int) -> None:
        # Add new value as a single-point interval
        self.intervals.append([val, val])
        # Sort by start value
        self.intervals.sort(key=lambda x: x[0])

        # Merge overlapping or adjacent intervals
        merged = []
        for interval in self.intervals:
            if not merged or merged[-1][1] + 1 < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        self.intervals = merged

    def getIntervals(self) -> List[List[int]]:
        # Return the current intervals
        return self.intervals

Explanation

• Lines 3-4: __init__
• intervals is a list of [start, end] pairs.
• Lines 6-15: addNum
• Add [val, val] to the list.
• Sort by start value (first element of each pair).
• Merge: Loop through intervals, add to merged if no overlap, or extend the last interval if adjacent/overlapping.
• Lines 17-19: getIntervals
• Return the list as is.
• Time: addNum O(n log n) due to sorting, getIntervals O(1).
• Space: O(n) for the list.

It’s a straightforward interval combiner!

Comparing the Two Solutions

• Sorted Dictionary (Best):
• Time: addNum O(log n), getIntervals O(n).
• Space: O(n).
• Pros: Fast additions, scalable.
• Cons: Requires external library.
• List with Merging (Alternative):
• Time: addNum O(n log n), getIntervals O(1).
• Space: O(n).
• Pros: Simple, no dependencies.
• Cons: Slower additions.

Sorted dictionary wins for efficiency!

Additional Examples and Edge Cases

• addNum(1), addNum(1): [[1,1]]—duplicates ignored.
• addNum(5), addNum(2), addNum(3): [[2,3],[5,5]]—merges correctly.
• Empty stream: []—handles no calls.

Both solutions manage these well.

Complexity Breakdown

• Sorted Dictionary:
• addNum: O(log n).
• getIntervals: O(n).
• Space: O(n).
• List:
• addNum: O(n log n).
• getIntervals: O(1).
• Space: O(n).

Dictionary excels for frequent updates.

Key Takeaways

• Sorted Dictionary: Fast merges—perfect for streams!
• List: Simple merging—great for learning!
• Intervals: Dynamic ranges are fun.
• Python Tip: Dictionaries and lists rock—see [Python Basics](/python/basics).

Final Thoughts: Stream Those Intervals

LeetCode 352: Data Stream as Disjoint Intervals in Python is a dynamic range challenge. The sorted dictionary solution shines for speed, while the list approach builds a solid foundation. Want more? Try LeetCode 57: Insert Interval or LeetCode 56: Merge Intervals. Ready to stream? Visit Solve LeetCode 352 on LeetCode and track those intervals today!