Data Stream as Disjoint Intervals

HARD

Description

Given a data stream input of non-negative integers a₁, a₂, ..., a_n, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

SummaryRanges() Initializes the object with an empty stream.
void addNum(int value) Adds the integer value to the stream.
int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [start_i, end_i]. The answer should be sorted by start_i.

Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Constraints:

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

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Approaches

Checkout 3 different approaches to solve Data Stream as Disjoint Intervals. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Using a Set and Sorting

This approach uses a simple strategy: collect all unique numbers from the stream and process them only when getIntervals() is called. A HashSet is used to store the numbers, which makes the addNum operation very fast.

Algorithm

Data Structure: Use a HashSet<Integer> to store the numbers from the data stream. This automatically handles duplicates.
addNum(value):
- Add the value to the HashSet. This is an O(1) average time operation.
getIntervals():
1. If the set is empty, return an empty array.
2. Create a List from the elements of the HashSet.
3. Sort the list in ascending order. This is the most time-consuming step, taking O(N log N) time, where N is the number of unique numbers.
4. Initialize an empty list of intervals, result.
5. Iterate through the sorted list to form intervals. Keep track of the start and end of the current interval.
6. If the current number is end + 1, it's part of the current interval, so update end.
7. If it's not consecutive, the previous interval [start, end] is complete. Add it to result and start a new interval with the current number.
8. After the loop, add the last formed interval to result.
9. Convert the result list to a 2D array and return it.

In this method, we prioritize making the addNum operation as fast as possible. We use a HashSet to store all unique numbers encountered in the stream. Adding a number is an O(1) operation on average.

The main work is deferred to the getIntervals method. When it's called, we first convert the set of numbers into a list, then sort it. This sorting step takes O(N log N) time, where N is the number of unique numbers seen so far. After sorting, we can iterate through the list in a single pass (O(N) time) to identify and merge consecutive numbers into disjoint intervals. The overall performance is thus dominated by the sorting step.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class SummaryRanges {
    private Set<Integer> numbers;

    public SummaryRanges() {
        numbers = new HashSet<>();
    }

    public void addNum(int value) {
        numbers.add(value);
    }

    public int[][] getIntervals() {
        if (numbers.isEmpty()) {
            return new int[0][];
        }

        List<Integer> sortedNums = new ArrayList<>(numbers);
        Collections.sort(sortedNums);

        List<int[]> intervals = new ArrayList<>();
        int start = sortedNums.get(0);
        int end = sortedNums.get(0);

        for (int i = 1; i < sortedNums.size(); i++) {
            int current = sortedNums.get(i);
            if (current == end + 1) {
                end = current;
            } else {
                intervals.add(new int[]{start, end});
                start = current;
                end = current;
            }
        }
        intervals.add(new int[]{start, end});

        return intervals.toArray(new int[intervals.size()][]);
    }
}

Complexity Analysis

Time Complexity: `addNum`: O(1) on average. `getIntervals`: O(N log N), where N is the number of unique integers. The sorting step is the bottleneck.Space Complexity: O(N), where N is the number of unique integers added to the stream. This space is used to store the numbers in the `HashSet`.

Pros and Cons

Pros:

The addNum operation is very fast, with an average time complexity of O(1).
The implementation is straightforward and easy to understand.

Cons:

getIntervals() has a high time complexity of O(N log N), which can be slow if N is large.
This approach recomputes all intervals from scratch every time getIntervals() is called, which is inefficient if this method is called frequently.

Code Solutions

Checking out 3 solutions in different languages for Data Stream as Disjoint Intervals. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Data Stream as Disjoint Intervals

Algorithms:

Binary Search

Patterns:

Design

Data Structures:

Ordered Set

Companies:

Databricks |