Data Stream as Disjoint Intervals

How it works

The brute force approach stores duplicates, which wastes space and processing time during sorting. By using a hash set instead of a list, we automatically eliminate duplicates. This makes the interval computation cleaner since we only deal with unique values.

Steps

1. Initialize a hash set to store unique numbers.
2. For addNum(value), add the value to the set (duplicates are ignored).
3. For getIntervals():
   • If the set is empty, return an empty result.
   • Convert the set to a sorted list.
   • Initialize start with the first element.
   • Iterate through the sorted list. When consecutive elements differ by more than 1, close the current interval and start a new one.
   • Add the final interval after the loop.
4. Return the list of intervals.

Complexity

• Time complexity:
  • O(1) time for initialization.
  • O(1) time for each addNum() function call.
  • O(n log n) time for each getIntervals() function call.
• Space complexity: O(n)

Things to watch for

Not Handling Duplicates

When adding numbers to the data stream, duplicates may appear. If using a list-based approach, duplicates cause intervals like [1, 1] to appear multiple times or create incorrect interval boundaries. Using a set automatically handles this.

Off-by-One in Consecutive Check

When merging intervals, two numbers are consecutive if they differ by exactly 1. A common mistake is using >= instead of > when checking for gaps, which incorrectly merges non-consecutive numbers.

Forgetting the Final Interval

When iterating through sorted numbers to build intervals, the loop only closes intervals when a gap is found. The last interval is never closed inside the loop and must be added after.

Incorrect Interval Extension Logic

When using ordered structures and extending intervals on the fly, the condition to extend must check if the current number is exactly one more than the interval end, not just greater.

Empty Input Edge Case

When getIntervals() is called before any numbers are added, or when all numbers have been processed, the function should return an empty list. Forgetting this check causes index errors.

from typing import List

class SummaryRanges:

    def __init__(self):
        self.arr = set()

    def addNum(self, value: int) -> None:
        self.arr.add(value)

    def getIntervals(self) -> List[List[int]]:
        if not self.arr:
            return []

        lst = sorted(list(self.arr))
        n = len(lst)
        start = lst[0]
        res = []
        for i in range(1, n):
            if lst[i] - lst[i - 1] > 1:
                res.append([start, lst[i - 1]])
                start = lst[i]

        res.append([start, lst[n - 1]])
        return res

class SummaryRanges {
private:
    set<int> arr;

public:
    SummaryRanges() {}

    void addNum(int value) {
        arr.insert(value);
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        if (arr.empty()) return res;

        vector<int> lst(arr.begin(), arr.end());
        int start = lst[0];

        for (int i = 1; i < lst.size(); i++) {
            if (lst[i] - lst[i - 1] > 1) {
                res.push_back({start, lst[i - 1]});
                start = lst[i];
            }
        }
        res.push_back({start, lst.back()});
        return res;
    }
};