Data Stream as Disjoint Intervals

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.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


**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]]

Solution

Method 1 – Ordered Set / TreeMap (Merge Intervals)

Intuition

To efficiently merge and maintain disjoint intervals as numbers are added, we can use a balanced BST (like TreeMap in Java, or std::set in C++). This allows us to quickly find and merge overlapping or adjacent intervals.

Approach

Store intervals in a sorted structure (by start).
When adding a number, check if it can merge with previous or next intervals, or if it creates a new interval.
Merge intervals as needed to keep them disjoint.
Return the list of intervals in sorted order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class SummaryRanges {
    set<pair<int, int>> intervals;
public:
    SummaryRanges() {}
    void addNum(int val) {
        auto it = intervals.lower_bound({val, val});
        int l = val, r = val;
        if (it != intervals.begin() && prev(it)->second + 1 >= val) {
            --it;
            l = it->first;
            r = max(r, it->second);
            intervals.erase(it);
        }
        it = intervals.lower_bound({val, val});
        while (it != intervals.end() && it->first <= r + 1) {
            r = max(r, it->second);
            it = intervals.erase(it);
        }
        intervals.insert({l, r});
    }
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for (auto& p : intervals) ans.push_back({p.first, p.second});
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


import "sort"
type Interval struct{l, r int}
type SummaryRanges struct{arr []Interval}
func Constructor() SummaryRanges {return SummaryRanges{}}
func (s *SummaryRanges) AddNum(val int) {
    arr := s.arr
    n := len(arr)
    i := sort.Search(n, func(i int) bool {return arr[i].l >= val})
    l, r := val, val
    if i > 0 && arr[i-1].r+1 >= val {
        i--
        l = arr[i].l
        r = max(r, arr[i].r)
        arr = append(arr[:i], arr[i+1:]...)
        n--
    }
    for i < n && arr[i].l <= r+1 {
        r = max(r, arr[i].r)
        arr = append(arr[:i], arr[i+1:]...)
        n--
    }
    arr = append(arr, Interval{l, r})
    sort.Slice(arr, func(i, j int) bool {return arr[i].l < arr[j].l})
    s.arr = arr
}
func (s *SummaryRanges) GetIntervals() [][]int {
    ans := [][]int{}
    for _, v := range s.arr {
        ans = append(ans, []int{v.l, v.r})
    }
    return ans
}
func max(a, b int) int {if a > b {return a} else {return b}}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class SummaryRanges {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public SummaryRanges() {}
    public void addNum(int val) {
        Integer l = map.floorKey(val), r = map.ceilingKey(val);
        if (l != null && map.get(l) + 1 >= val) {
            if (r != null && r == val + 1) {
                map.put(l, map.get(r));
                map.remove(r);
            } else {
                map.put(l, Math.max(map.get(l), val));
            }
        } else if (r != null && r == val + 1) {
            map.put(val, map.get(r));
            map.remove(r);
        } else {
            map.put(val, val);
        }
    }
    public int[][] getIntervals() {
        int[][] ans = new int[map.size()][2];
        int i = 0;
        for (var e : map.entrySet()) {
            ans[i][0] = e.getKey();
            ans[i++][1] = e.getValue();
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class SummaryRanges {
    private val map = java.util.TreeMap<Int, Int>()
    fun addNum(val: Int) {
        val l = map.floorKey(val)
        val r = map.ceilingKey(val)
        if (l != null && map[l]!! + 1 >= val) {
            if (r != null && r == val + 1) {
                map[l] = map[r]!!
                map.remove(r)
            } else {
                map[l] = maxOf(map[l]!!, val)
            }
        } else if (r != null && r == val + 1) {
            map[val] = map[r]!!
            map.remove(r)
        } else {
            map[val] = val
        }
    }
    fun getIntervals(): Array<IntArray> = map.map { intArrayOf(it.key, it.value) }.toTypedArray()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class SummaryRanges:
    def __init__(self):
        self.intervals = []
    def addNum(self, val: int) -> None:
        arr = self.intervals
        n = len(arr)
        i = 0
        while i < n and arr[i][1] + 1 < val:
            i += 1
        l, r = val, val
        if i < n and arr[i][0] - 1 <= val <= arr[i][1] + 1:
            l = min(l, arr[i][0])
            r = max(r, arr[i][1])
            arr.pop(i)
            n -= 1
        while i < n and arr[i][0] <= r + 1:
            r = max(r, arr[i][1])
            arr.pop(i)
            n -= 1
        arr.insert(i, [l, r])
    def getIntervals(self) -> list[list[int]]:
        return self.intervals

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


use std::collections::BTreeMap;
struct SummaryRanges {
    map: BTreeMap<i32, i32>,
}
impl SummaryRanges {
    fn new() -> Self {
        SummaryRanges { map: BTreeMap::new() }
    }
    fn add_num(&mut self, val: i32) {
        let mut l = val;
        let mut r = val;
        if let Some((&start, &end)) = self.map.range(..=val).next_back() {
            if end + 1 >= val {
                l = start;
                r = end.max(val);
                self.map.remove(&start);
            }
        }
        while let Some((&start, &end)) = self.map.range(val+1..).next() {
            if start <= r + 1 {
                r = r.max(end);
                self.map.remove(&start);
            } else {
                break;
            }
        }
        self.map.insert(l, r);
    }
    fn get_intervals(&self) -> Vec<Vec<i32>> {
        self.map.iter().map(|(&l, &r)| vec![l, r]).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class SummaryRanges {
    private arr: number[][] = [];
    addNum(val: number): void {
        let arr = this.arr, n = arr.length, i = 0;
        while (i < n && arr[i][1] + 1 < val) i++;
        let l = val, r = val;
        if (i < n && arr[i][0] - 1 <= val && val <= arr[i][1] + 1) {
            l = Math.min(l, arr[i][0]);
            r = Math.max(r, arr[i][1]);
            arr.splice(i, 1);
            n--;
        }
        while (i < n && arr[i][0] <= r + 1) {
            r = Math.max(r, arr[i][1]);
            arr.splice(i, 1);
            n--;
        }
        arr.splice(i, 0, [l, r]);
    }
    getIntervals(): number[][] {
        return this.arr;
    }
}

Complexity

⏰ Time complexity: O(log n) per addNum (with balanced BST), O(n) for getIntervals.
🧺 Space complexity: O(n), for storing intervals.

Problem#

Examples#

Solution#

Method 1 – Ordered Set / TreeMap (Merge Intervals)#

Intuition#

Approach#

Code#

Complexity#