# Data Stream as Disjoint Intervals
**Difficulty:** HARD
[External](https://leetcode.com/problems/data-stream-as-disjoint-intervals)
Canonical: https://scaleengineer.com/dsa/problems/data-stream-as-disjoint-intervals
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Ordered Set
**Companies:** [Databricks](https://scaleengineer.com/companies/databricks)
---
## Problem
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
## 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.
**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`.
**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.
### Explanation
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.

```java
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()][]);
    }
}
```
### 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.

## Boolean Array
This approach leverages the small and fixed range of the input values. By using a boolean array (or a bitset) to mark which numbers have been seen, we can make both `addNum` and `getIntervals` operations very fast and independent of the number of elements in the stream.
**Time:** `addNum`: O(1).
`getIntervals`: O(M), where M is the maximum possible value. This is constant time relative to the number of elements in the stream. · **Space:** O(M), where M is the maximum possible value of an input number (10001 in this case). The space is constant and does not depend on the number of calls.
**Pros:** Both `addNum` and `getIntervals` have constant time complexity with respect to the number of elements added.; The implementation is relatively simple.
**Cons:** The space complexity is O(M), where M is the maximum possible value. This is not feasible if the range of values is very large.; The `getIntervals` method always iterates through the entire range of possible values (M), which can be inefficient if the number of actual intervals (K) is much smaller than M.
### Explanation
Since the input values are non-negative and capped at 10000, we can allocate a boolean array `seen` of size 10001. Each index in this array corresponds to a number.

For `addNum(value)`, we simply perform a direct lookup and set the corresponding flag: `seen[value] = true`. This is an O(1) operation.

For `getIntervals()`, we can iterate through the entire `seen` array once. When we find an index `i` where `seen[i]` is true, we know this is the start of an interval. We then scan forward to find the end of this contiguous block of `true` values. This gives us one disjoint interval. We then continue our scan from where the interval ended. The total time for this is proportional to the size of the boolean array, which is constant.

```java
import java.util.ArrayList;
import java.util.List;

class SummaryRanges {
    private boolean[] seen;

    public SummaryRanges() {
        // Constraints: 0 <= value <= 10^4
        seen = new boolean[10001];
    }

    public void addNum(int value) {
        seen[value] = true;
    }

    public int[][] getIntervals() {
        List<int[]> intervals = new ArrayList<>();
        int i = 0;
        while (i < seen.length) {
            if (seen[i]) {
                int start = i;
                int j = i;
                while (j < seen.length && seen[j]) {
                    j++;
                }
                intervals.add(new int[]{start, j - 1});
                i = j;
            } else {
                i++;
            }
        }
        return intervals.toArray(new int[intervals.size()][]);
    }
}
```
### Algorithm
- **Data Structure**: Use a boolean array `seen` of size `10001`, given the constraint `0 <= value <= 10000`. `seen[i]` will be `true` if the number `i` has been added to the stream.
- **`addNum(value)`**:
  - Set `seen[value] = true`. This is an O(1) operation.
- **`getIntervals()`**:
  1. Initialize an empty list `intervals` to store the results.
  2. Iterate through the `seen` array with an index `i` from 0 to 10000.
  3. If `seen[i]` is `true`, it signifies the start of an interval.
  4. Set `start = i`.
  5. Find the end of this interval by advancing a second pointer `j` from `i` as long as `j` is within bounds and `seen[j]` is `true`.
  6. The interval is `[start, j - 1]`. Add it to the `intervals` list.
  7. Continue the main loop by setting `i = j` to avoid re-checking the numbers within the interval just found.
  8. If `seen[i]` is `false`, simply increment `i`.
  9. Convert the `intervals` list to a 2D array and return.

## Balanced Binary Search Tree (TreeMap)
This is the most efficient and scalable approach, especially for the follow-up scenario where the number of disjoint intervals is small. It maintains the intervals directly in a sorted map (`TreeMap`), allowing for efficient insertion and merging.
**Time:** `addNum`: O(log K), where K is the number of disjoint intervals.
`getIntervals`: O(K). · **Space:** O(K), where K is the number of disjoint intervals. This is optimal as we must store the intervals.
**Pros:** Highly efficient `addNum` operation with O(log K) time complexity.; Efficient `getIntervals` with O(K) time complexity.; Space complexity O(K) is optimal, as it only stores the necessary intervals.; It's a general solution that works for any range of input values, not just small ones.; Perfectly addresses the follow-up question about frequent merges and a small number of intervals.
**Cons:** The implementation is more complex than the other approaches due to handling multiple merge cases.; There is a slight overhead for `addNum` (O(log K)) compared to O(1) approaches, though it's negligible in practice.
### Explanation
This approach directly manages the list of disjoint intervals. By storing them in a `TreeMap`, we can leverage its ability to keep keys (interval start points) sorted and perform efficient lookups, insertions, and deletions in O(log K) time, where K is the current number of disjoint intervals.

When `addNum(value)` is called, we first check if the value is already contained within an existing interval. If not, we look for adjacent intervals. We find the interval that ends just before `value` and the one that starts just after `value`. Based on whether `value` is consecutive to one or both of these, we perform a merge. 
- If `value` connects two existing intervals, we merge them into one.
- If it's adjacent to only one, we extend that interval.
- If it's isolated, we create a new interval of `[value, value]`.

Each `addNum` call involves a few O(log K) operations on the `TreeMap`. The `getIntervals` method is very efficient as it just needs to dump the values from the `TreeMap` into an array, which takes O(K) time.

```java
import java.util.TreeMap;

class SummaryRanges {
    private TreeMap<Integer, int[]> treeMap;

    public SummaryRanges() {
        treeMap = new TreeMap<>();
    }

    public void addNum(int value) {
        if (treeMap.containsKey(value)) {
            return;
        }
        // Find intervals that are just lower and higher than value
        Integer lowerKey = treeMap.lowerKey(value);
        Integer higherKey = treeMap.higherKey(value);

        // Check if value is already covered by an interval starting at or before value
        if (lowerKey != null && treeMap.get(lowerKey)[1] >= value) {
            return;
        }

        boolean mergeWithLower = (lowerKey != null && treeMap.get(lowerKey)[1] + 1 == value);
        boolean mergeWithHigher = (higherKey != null && higherKey == value + 1);

        if (mergeWithLower && mergeWithHigher) {
            // Merge lower and higher intervals
            int[] lowerInterval = treeMap.get(lowerKey);
            int[] higherInterval = treeMap.get(higherKey);
            lowerInterval[1] = higherInterval[1];
            treeMap.remove(higherKey);
        } else if (mergeWithLower) {
            // Extend lower interval
            treeMap.get(lowerKey)[1] = value;
        } else if (mergeWithHigher) {
            // Extend higher interval by creating a new one and removing the old
            int[] higherInterval = treeMap.remove(higherKey);
            treeMap.put(value, new int[]{value, higherInterval[1]});
        } else {
            // Add a new interval
            treeMap.put(value, new int[]{value, value});
        }
    }

    public int[][] getIntervals() {
        return treeMap.values().toArray(new int[treeMap.size()][]);
    }
}
```
### Algorithm
- **Data Structure**: Use a `TreeMap<Integer, int[]>` where the key is the start of an interval and the value is the interval itself (`int[]{start, end}`). `TreeMap` keeps the intervals sorted by their start times and provides efficient logarithmic time lookups.
- **`addNum(value)`**:
  1. Find the interval whose start is just lower than or equal to `value` (`lowerKey`) and the interval whose start is just higher than `value` (`higherKey`). These are O(log K) operations.
  2. Check if `value` is already covered by an existing interval. If `lowerKey` exists and its interval's end is greater than or equal to `value`, do nothing.
  3. Determine if the new `value` can merge with the lower interval (`lowerInterval.end + 1 == value`) and/or the higher interval (`higherKey == value + 1`).
  4. **Case 1: Merge with both.** If it merges with both lower and higher intervals, extend the lower interval to cover the higher one's end, and remove the higher interval from the map.
  5. **Case 2: Merge with lower only.** Extend the lower interval's end to `value`.
  6. **Case 3: Merge with higher only.** Remove the higher interval and insert a new one starting at `value` and ending at the higher interval's original end.
  7. **Case 4: No merge.** Insert a new interval `[value, value]` into the map.
- **`getIntervals()`**:
  - The `TreeMap`'s values view (`treeMap.values()`) provides a collection of the intervals, already sorted by their start times. Convert this collection to a 2D array. This takes O(K) time.

# Solutions
### Java

```java
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(); */
```

### CPP

```cpp
class SummaryRanges { private: map < int , vector < int >> mp ; public: SummaryRanges () { } void addNum ( int val ) { auto r = mp . upper_bound ( val ); auto l = r == mp . begin () ? mp . end () : prev ( r ); if ( l != mp . end () && r != mp . end () && l -> second [ 1 ] + 1 == val && r -> second [ 0 ] - 1 == val ) { l -> second [ 1 ] = r -> second [ 1 ]; mp . erase ( r ); } else if ( l != mp . end () && val <= l -> second [ 1 ] + 1 ) l -> second [ 1 ] = max ( val , l -> second [ 1 ]); else if ( r != mp . end () && val >= r -> second [ 0 ] - 1 ) r -> second [ 0 ] = min ( val , r -> second [ 0 ]); else mp [ val ] = { val , val }; } vector < vector < int >> getIntervals () { vector < vector < int >> res ; for ( auto & range : mp ) res . push_back ( range . second ); return res ; } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */
```

### Python

```python
# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e # better and easier, manual filter() via while # I like this one the most class SummaryRanges : def __init__ ( self ): self . intervals = [] def addNum ( self , val : int ) -> None : new_interval = [ val , val ] merged_intervals = [] i = 0 # before overlap part while i < len ( self . intervals ) and self . intervals [ i ][ 1 ] < val - 1 : merged_intervals . append ( self . intervals [ i ]) i += 1 # process overlap while i < len ( self . intervals ) and self . intervals [ i ][ 0 ] <= val + 1 : new_interval [ 0 ] = min ( new_interval [ 0 ], self . intervals [ i ][ 0 ]) new_interval [ 1 ] = max ( new_interval [ 1 ], self . intervals [ i ][ 1 ]) i += 1 merged_intervals . append ( new_interval ) # after overlap part while i < len ( self . intervals ): merged_intervals . append ( self . intervals [ i ]) i += 1 # also passed OJ, instead of while loop: # merged_intervals.extend(self.intervals[i:]) self . intervals = merged_intervals def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals ############ class SummaryRanges : # passed OJ, optimized below solution def __init__ ( self ): self . intervals = [] def insert ( self , newInterval : List [ int ]): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ intervals = self . intervals # print intervals if not intervals : intervals . append ( newInterval ) return s , e = newInterval [ 0 ], newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] + 1 < newInterval [ 0 ], intervals )) right = list ( filter ( lambda x : x [ 0 ] - 1 > newInterval [ 1 ], intervals )) if left + right != intervals : s = min ( intervals [ len ( left )][ 0 ], s ) e = max ( intervals [ ~ len ( right )][ 1 ], e ) # +1 or -1 check: included in lambda's '+1<' and '-1>' self . intervals = left + [ [ s , e ] ] + right def addNum ( self , val : int ) -> None : self . insert ([ val , val ]) def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals ############ class SummaryRanges : # above is optimized version def __init__ ( self ): self . intervals = [] def insert ( self , newInterval : List [ int ]): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ intervals = self . intervals # print intervals if not intervals : intervals . append ( newInterval ) return s , e = newInterval [ 0 ], newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] < newInterval [ 0 ], intervals )) right = list ( filter ( lambda x : x [ 0 ] > newInterval [ 1 ], intervals )) # print left, right, (s, e) if left + right != intervals : s = min ( intervals [ len ( left )][ 0 ], s ) e = max ( intervals [ ~ len ( right )][ 1 ], e ) newIntv = [ s , e ] # merging piece is different from above solution if left and left [ - 1 ][ 1 ] + 1 == s : newIntv [ 0 ] = left [ - 1 ][ 0 ] left = left [: - 1 ] # cut out last one, which is merged with newIntv if right and right [ 0 ][ 0 ] - 1 == e : newIntv [ 1 ] = right [ 0 ][ 1 ] right = right [ 1 :] # cut out first one, which is merged with newIntv self . intervals = left + [ newIntv ] + right def addNum ( self , val : int ) -> None : self . insert ([ val , val ]) def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals # Your SummaryRanges object will be instantiated and called as such: # obj = SummaryRanges() # obj.addNum(val) # param_2 = obj.getIntervals() ############ ''' >>> mp = SortedDict() >>> mp.bisect_right(3) 0 >>> mp = SortedDict() >>> mp[1]=[1,1] >>> mp[3]=[3,3] >>> mp[5]=[5,5] >>> >>> mp SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]}) >>> mp.bisect_right(-10) 0 >>> mp.bisect_right(100) 3 >>> mp.bisect_right(2) 1 >>> mp.values() SortedValuesView(SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]})) >>> list(mp.values()) [[1, 1], [3, 3], [5, 5]] >>> ''' from sortedcontainers import SortedDict class SummaryRanges : def __init__ ( self ): self . mp = SortedDict () def addNum ( self , val : int ) -> None : n = len ( self . mp ) ridx = self . mp . bisect_right ( val ) lidx = n if ridx == 0 else ( ridx - 1 ) # n is similar to java treemap returning null keys = self . mp . keys () values = self . mp . values () if ( lidx != n and ridx != n and values [ lidx ][ 1 ] + 1 == val and values [ ridx ][ 0 ] - 1 == val ): self . mp [ keys [ lidx ]][ 1 ] = self . mp [ keys [ ridx ]][ 1 ] self . mp . pop ( keys [ ridx ]) elif lidx != n and val <= values [ lidx ][ 1 ] + 1 : # <= because, it could be [1 -> 10], and new add is [5,5] self . mp [ keys [ lidx ]][ 1 ] = max ( val , self . mp [ keys [ lidx ]][ 1 ]) elif ridx != n and val >= values [ ridx ][ 0 ] - 1 : self . mp [ keys [ ridx ]][ 0 ] = min ( val , self . mp [ keys [ ridx ]][ 0 ]) else : self . mp [ val ] = [ val , val ] def getIntervals ( self ) -> List [ List [ int ]]: return list ( self . mp . values ()) # # Your SummaryRanges object will be instantiated and called as such: # # obj = SummaryRanges() # # obj.addNum(val) # # param_2 = obj.getIntervals()
```