Data stream as disjoint intervals

Hash Table Binary Search Union-Find Design Data Stream Ordered Set

60.0% acceptance

Jan 12, 2026

1817

374

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

struct SummaryRanges {
  intervals: std::cell::RefCell<BTreeMap<i32, i32>>,
}

impl SummaryRanges {
  fn new() -> Self {
    SummaryRanges {
      intervals: std::cell::RefCell::new(BTreeMap::new()),
    }
  }
  
  fn add_num(&self, value: i32) {
    let mut intervals = self.intervals.borrow_mut();
    
    // Check if value already covered
    if let Some((&_start, &end)) = intervals.range(..=value).next_back() {
      if value <= end {
        return;
      }
    }
    
    let mut new_start = value;
    let mut new_end = value;
    
    // Check if we can merge with previous interval
    if let Some((&start, &end)) = intervals.range(..value).next_back() {
      if end + 1 >= value {
        new_start = start;
        intervals.remove(&start);
      }
    }
    
    // Check if we can merge with next interval(s)
    let merge_candidates: Vec<(i32, i32)> = intervals
      .range(value..)
      .take_while(|(start, _end)| **start <= new_end + 1)
      .map(|(&start, &end)| (start, end))
      .collect();
    
    for (start, end) in merge_candidates {
      new_end = new_end.max(end);
      intervals.remove(&start);
    }
    
    intervals.insert(new_start, new_end);
  }
  
  fn get_intervals(&self) -> Vec<Vec<i32>> {
    self.intervals
      .borrow()
      .iter()
      .map(|(&start, &end)| vec![start, end])
      .collect()
  }
}