LeetCode #352 — HARD

Data Stream as Disjoint Intervals

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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?

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Hash Map · Binary Search · Union-Find · Design · Segment Tree

Example 1

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

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #352: Data Stream as Disjoint Intervals
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();
 */

// Accepted solution for LeetCode #352: Data Stream as Disjoint Intervals
package main

import "sort"

type SummaryRanges struct {
	numSet map[int]bool
}

func Constructor() SummaryRanges {
	return SummaryRanges{numSet: map[int]bool{}}
}

func (this *SummaryRanges) AddNum(value int) {
	this.numSet[value] = true
}

func (this *SummaryRanges) GetIntervals() [][]int {
	nums := []int{}
	for num, _ := range this.numSet {
		nums = append(nums, num)
	}
	sort.Ints(nums)

	res := [][]int{}

	i := 0

	for i < len(nums) {
		start := nums[i]

		for i +1 < len(nums) && nums[i] +1 == nums[i+1] {
			i++
		}

		res = append(res, []int{start, nums[i]})
		i++
	}

	return res
}

func main() {
	
}

# Accepted solution for LeetCode #352: Data Stream as Disjoint Intervals
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
        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:
            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()

// Accepted solution for LeetCode #352: Data Stream as Disjoint Intervals
// BTreeSet Solution

use std::collections::BTreeSet;

struct SummaryRanges {
    tree_map: BTreeSet<i32>,
}

impl SummaryRanges {
    fn new() -> Self {
        Self {
            tree_map: BTreeSet::new(),
        }
    }

    fn add_num(&mut self, value: i32) {
        self.tree_map.insert(value);
    }

    fn get_intervals(&self) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = vec![];

        for n in &self.tree_map {
            if !res.is_empty() && res.last().unwrap()[1] + 1 == *n {
                let mut last = res.pop().unwrap();
                last[1] = *n;
                res.push(last);
            } else {
                res.push(vec![*n, *n]);
            }
        }

        res
    }
}

// HashSet Solution
use std::collections::HashSet;
struct SummaryRanges {
    ranges: Vec<Vec<i32>>,
    num_set: HashSet<i32>,
}

impl SummaryRanges {
    fn new() -> Self {
        Self {
            ranges: vec![],
            num_set: HashSet::new(),
        }
    }

    fn add_num(&mut self, value: i32) {
        self.num_set.insert(value);
    }

    fn get_intervals(&self) -> Vec<Vec<i32>> {
        let mut nums: Vec<i32> = self.num_set.iter().cloned().collect();
        nums.sort();
        let mut res = vec![];
        let mut i = 0;

        while i < nums.len() {
            let start = nums[i];

            while i + 1 < nums.len() && nums[i] + 1 == nums[i + 1] {
                i += 1;
            }
            res.push(vec![start, nums[i]]);
            i += 1;
        }
        res
    }
}

// Accepted solution for LeetCode #352: Data Stream as Disjoint Intervals
class SummaryRanges {
    numSet: Set<number>;

    constructor() {
        this.numSet = new Set();
    }

    addNum(value: number): void {
        this.numSet.add(value);
    }

    getIntervals(): number[][] {
        let nums = Array.from(this.numSet.keys());
        nums.sort((a, b) => a - b);
        let res: number[][] = [];

        let i = 0;

        while (i < nums.length) {
            const start = nums[i];

            while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) {
                i++;
            }

            res.push([start, nums[i]]);
            i++;
        }

        return res;
    }
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.