Scale Engineer

Data Stream as Disjoint Intervals

Hard
#0339Time: `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: 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`.1 company
Patterns
Design
Algorithms
Binary Search
Data structures
Ordered Set
Companies
Databricks

Prompt

Given a data stream input of non-negative integers a1, a2, ..., an, 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 [starti, endi]. The answer should be sorted by starti.

 

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 <= 104
  • At most 3 * 104 calls will be made to addNum and getIntervals.
  • At most 102 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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

`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

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`.

Trade-offs

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.

Solutions

class SummaryRanges { private TreeMap < Integer , int []> mp ; public SummaryRanges () { mp = new TreeMap <>(); } public void addNum ( int val ) { Integer l = mp . floorKey ( val ); Integer r = mp . ceilingKey ( val ); if ( l != null && r != null && mp . get ( l )[ 1 ] + 1 == val && mp . get ( r )[ 0 ] - 1 == val ) { mp . get ( l )[ 1 ] = mp . get ( r )[ 1 ]; mp . remove ( r ); } else if ( l != null && val <= mp . get ( l )[ 1 ] + 1 ) { mp . get ( l )[ 1 ] = Math . max ( val , mp . get ( l )[ 1 ]); } else if ( r != null && val >= mp . get ( r )[ 0 ] - 1 ) { mp . get ( r )[ 0 ] = Math . min ( val , mp . get ( r )[ 0 ]); } else { mp . put ( val , new int [] { val , val }); } } public int [][] getIntervals () { int [][] res = new int [ mp . size ()][ 2 ]; int i = 0 ; for ( int [] range : mp . values ()) { res [ i ++] = range ; } return res ; } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem