Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals

Master this topic with zero to advance depth.

Data Stream as Disjoint Intervals

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 [start_i, end_i]. The answer should be sorted by start_i.

Visual Representation

addNum(1): [1,1] addNum(3): [1,1], [3,3] addNum(7): [1,1], [3,3], [7,7] addNum(2): [1,3], [7,7] <-- 2 merges [1,1] and [3,3] addNum(6): [1,3], [6,7] <-- 6 merges with [7,7] Key: When adding N, find and merge with adjacent intervals. [L, N-1] + N + [N+1, R] => [L, R]
Hard

Examples

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]]]
Approach 1

Level I: Brute Force - Rebuild on Every getIntervals

Intuition

Simply store all seen numbers in a sorted list. On every getIntervals() call, rebuild the disjoint intervals from scratch by scanning through the sorted list and merging consecutive numbers.

⏱ O(N log N) for `addNum` (insert into sorted structure), O(N) for `getIntervals`💾 O(N) for storing all numbers

Detailed Dry Run

addNum(1), addNum(3), addNum(7), addNum(2) nums = {1, 2, 3, 7} getIntervals(): sorted = [1, 2, 3, 7] Scan: 1->next is 2 (consecutive), 2->next is 3 (consecutive), 3->next is 7 (gap) Intervals: [1,3], [7,7]

java
import java.util.*;

class SummaryRanges {
    private TreeSet<Integer> set;

    public SummaryRanges() {
        set = new TreeSet<>();
    }
    
    public void addNum(int value) {
        set.add(value);
    }
    
    public int[][] getIntervals() {
        List<int[]> result = new ArrayList<>();
        Integer start = null, end = null;
        
        for (int num : set) {
            if (start == null) {
                start = end = num;
            } else if (num == end + 1) {
                end = num;
            } else {
                result.add(new int[]{start, end});
                start = end = num;
            }
        }
        if (start != null) result.add(new int[]{start, end});
        return result.toArray(new int[0][]);
    }
}

public class Main {
    public static void main(String[] args) {
        SummaryRanges sr = new SummaryRanges();
        sr.addNum(1); sr.addNum(3); sr.addNum(7); sr.addNum(2); sr.addNum(6);
        System.out.println(java.util.Arrays.deepToString(sr.getIntervals())); // [[1,3],[6,7]]
    }
}
Approach 2

Level II: Maintenance of Sorted Intervals

Intuition

Instead of rebuilding the intervals every time, we can maintain a sorted list of disjoint intervals. When adding a new number, we use binary search to find where it would fit among existing intervals, then check if it can be merged with its left or right neighbors. This significantly speeds up getIntervals at the cost of O(N)O(N) for addNum due to array shifts.

⏱ O(N) for `addNum` (binary search + possible array insertion/deletion), O(1) for `getIntervals` (if returning the internal list)💾 O(N) for storing the intervals

Detailed Dry Run

addNum(1): [[1,1]] addNum(3): [[1,1], [3,3]] addNum(2): 2 is between [1,1] and [3,3]. Merges both -> [[1,3]] addNum(7): [[1,3], [7,7]]

java
import java.util.*;

class SummaryRanges {
    private List<int[]> intervals;

    public SummaryRanges() {
        intervals = new ArrayList<>();
    }
    
    public void addNum(int value) {
        int n = intervals.size();
        int left = 0, right = n - 1;
        // Binary search for insertion point
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int[] iv = intervals.get(mid);
            if (iv[0] <= value && value <= iv[1]) return;
            if (iv[0] > value) right = mid - 1;
            else left = mid + 1;
        }
        
        int pos = left;
        boolean mergeLeft = pos > 0 && intervals.get(pos - 1)[1] + 1 == value;
        boolean mergeRight = pos < n && intervals.get(pos)[0] - 1 == value;
        
        if (mergeLeft && mergeRight) {
            intervals.get(pos - 1)[1] = intervals.get(pos)[1];
            intervals.remove(pos);
        } else if (mergeLeft) {
            intervals.get(pos - 1)[1] = value;
        } else if (mergeRight) {
            intervals.get(pos)[0] = value;
        } else {
            intervals.add(pos, new int[]{value, value});
        }
    }
    
    public int[][] getIntervals() {
        return intervals.toArray(new int[0][]);
    }
}
Approach 3

Level III: TreeMap / Sorted Map for O(log N) addNum

Intuition

Instead of re-sorting each time, maintain intervals in a sorted map (TreeMap in Java, SortedDict in Python, etc.) keyed by start. When adding a new number val:

  1. Find the interval that might start right after val+1 (right neighbor).
  2. Find the interval whose start <= val (left neighbor), and check if it ends at val-1.
  3. Based on overlapping/adjacency with left and right neighbors, merge intervals accordingly.

This gives O(log N) per addNum and O(N) per getIntervals.

⏱ O(log N) for `addNum`, O(N) for `getIntervals`💾 O(N) for storing the intervals in the sorted map

Detailed Dry Run

addNum(1): map = {1:[1,1]} addNum(3): map = {1:[1,1], 3:[3,3]} addNum(7): map = {1:[1,1], 3:[3,3], 7:[7,7]} addNum(2): val=2. Right neighbor start=3 (3 == 2+1). Left neighbor: key=1, [1,1]. end=1 == 2-1. Merge both: [min(1,2)=1, max(1,3)=3] = [1,3]. Remove key 3. map = {1:[1,3], 7:[7,7]} addNum(6): val=6. Right neighbor start=7 (7 == 6+1). Check left: key=1, [1,3]. end=3 != 5. Only merge with right: [6, 7]. Remove key 7. map = {1:[1,3], 6:[6,7]} getIntervals: [[1,3],[6,7]]

java
import java.util.*;

class SummaryRanges {
    private TreeMap<Integer, Integer> map; // start -> end

    public SummaryRanges() {
        map = new TreeMap<>();
    }
    
    public void addNum(int val) {
        if (map.containsKey(val)) return;

        Integer lo = map.lowerKey(val);   // start of potential left interval
        Integer hi = map.higherKey(val);  // start of potential right interval
        
        boolean mergeLeft = lo != null && map.get(lo) + 1 >= val;  // [lo, lo.end] adjacent or covering
        boolean mergeRight = hi != null && hi == val + 1;           // [val+1, ...] is right adjacent
        
        if (mergeLeft && mergeRight) {
            // Merge val into [lo, hi.end]
            map.put(lo, map.get(hi));
            map.remove(hi);
        } else if (mergeLeft) {
            // Extend left interval
            map.put(lo, Math.max(map.get(lo), val));
        } else if (mergeRight) {
            // Extend right interval leftward
            int end = map.get(hi);
            map.remove(hi);
            map.put(val, end);
        } else {
            map.put(val, val);
        }
    }
    
    public int[][] getIntervals() {
        int[][] result = new int[map.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            result[i][0] = e.getKey();
            result[i][1] = e.getValue();
            i++;
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        SummaryRanges sr = new SummaryRanges();
        for (int n : new int[]{1, 3, 7, 2, 6}) sr.addNum(n);
        System.out.println(java.util.Arrays.deepToString(sr.getIntervals())); // [[1,3],[6,7]]
    }
}
← Previous QuestionMaximum Number of Events
Next Question →Smallest Range Covering Elements from K Lists