⚡Flashcard Drill➔
NeetCode #848LC-352HardIntervals
← Back to All Problems

#848 · #352 · Data Stream as Disjoint Intervals(将数据流变为多个不相交区间)

📌 Problem Statement & Constraints

Given a data stream of non-negative integers, design a structure that summarises the numbers seen so far as a list of disjoint sorted intervals. Implement addNum(value) and getIntervals(). Constraints: 0 <= value <= 10^4, at most 3 * 10^4 calls in total.

💡 Core Algorithmic Approaches

  1. Maintain the summary as a list of disjoint intervals sorted by start.
  2. On addNum, binary search for the position just after the last interval whose start is at most value.
  3. If the previous interval's end is at least value - 1, extend it to include value; otherwise insert a new singleton interval.
  4. Then repeatedly merge with the following interval while the gap is at most one, keeping the invariant intact.

💻 Benchmark Python3 Implementation

class Solution:
    def __init__(self):
        self.intervals = []                     # sorted disjoint [start, end]

    def addNum(self, value: int) -> None:
        from bisect import bisect_right
        intervals = self.intervals
        i = bisect_right(intervals, [value, float("inf")])   # first start > value
        if i > 0 and intervals[i - 1][1] >= value - 1:
            i -= 1
            intervals[i][1] = max(intervals[i][1], value)
        else:
            intervals.insert(i, [value, value])
        while i + 1 < len(intervals) and intervals[i][1] + 1 >= intervals[i + 1][0]:
            intervals[i][1] = max(intervals[i][1], intervals[i + 1][1])
            intervals.pop(i + 1)

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) per addNum in the worst case due to the list insertion; the merge itself is amortised O(1) per interval.
💾 Space Complexity
O(n): the interval list.

⚠️ Interview Pitfalls & Follow-ups

  • Merging only with the immediate neighbour: adding a value can bridge two intervals at once (for example [1,2] and [4,5] with 3), which the while loop handles.
  • Using >= value instead of >= value - 1: adjacent intervals merge, so a gap of exactly one must be bridged.
  • Forgetting the merge with the previous interval: the binary search lands after all intervals with start at most value, so the previous one may need extending.
  • Returning internal references: getIntervals returns the live list; callers that mutate it would corrupt the structure, but LeetCode's checker only reads it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems