Data Stream as Disjoint Intervals

LeetCode 352: Data Stream as Disjoint Intervals

i recently solved the data stream as disjoint intervals problem on leetcode, and it's a great example of data structure design and interval management. this hard problem tests your understanding of efficient interval operations, data structure selection, and rust's ownership system.

Problem Statement

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.
• 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]]

My Approach

when i first saw this problem, i immediately thought about using a sorted data structure to maintain intervals efficiently. the key insight is using a btree to maintain sorted intervals and efficiently handle insertions and merges.

Initial Thoughts

i started by thinking about different approaches:

• btree approach - use sorted tree for interval management
• array approach - maintain sorted array of intervals
• linked list - use linked list for interval management
• hash set - track individual numbers and build intervals

Solution Strategy

i decided to use a btree approach with the following strategy:

• data structure - use btreeset to maintain sorted intervals
• insertion logic - find overlapping intervals and merge them
• interval management - handle left and right boundary cases
• efficient operations - use rust's btreeset for O(log n) operations
• result building - convert intervals to required format

My Solution

use std::collections::btreeset;

struct summaryranges {
intervals: btreeset<(i32, i32)>,
}

impl summaryranges {
fn new() -> self {
summaryranges {
intervals: btreeset::new(),
}
}

fn addnum(&mut self, value: i32) {
// find the interval that ends just before value
let mut left_bound = value;
let mut right_bound = value;

// check if value is already in an existing interval
if let some(&(start, end)) = self.intervals.range(..(value, i32::max)).next_back() {
if end >= value {
return; // value is already in an interval
}
if end + 1 == value {
left_bound = start;
self.intervals.remove(&(start, end));
}
}

// check if value can extend an interval to the right
if let some(&(start, end)) = self.intervals.range((value, i32::min)..).next() {
if start == value + 1 {
right_bound = end;
self.intervals.remove(&(start, end));
}
}

// insert the new merged interval
self.intervals.insert((left_bound, right_bound));
}

fn getintervals(&self) -&gt; vec<vec<i32>&gt; {
self.intervals
.iter()
.map(|&(start, end)| vec![start, end])
.collect()
}
}

Code Breakdown

let me walk through how this solution works:

1. Data Structure Setup

use std::collections::btreeset;

struct summaryranges {
intervals: btreeset<(i32, i32)>,
}

we use btreeset for efficient interval management:

• btreeset: maintains sorted order automatically
• tuple storage: (start, end) for each interval
• efficient operations: O(log n) for insert/remove/search

2. Constructor

impl summaryranges {
fn new() -> self {
summaryranges {
intervals: btreeset::new(),
}
}
}

the constructor:

• initialize: create empty btreeset
• ownership: rust's ownership system handles memory
• efficiency: O(1) initialization time

3. Add Number Logic

fn addnum(&mut self, value: i32) {
let mut left = value;
let mut right = value;

// find intervals that can be merged
let mut to_remove = vec![];

// check for left neighbor
if let some(&(start, end)) = self.intervals.range(..(value, i32::max)).next_back() {
if end + 1 >= value {
left = start;
to_remove.push((start, end));
}
}

// check for right neighbor
if let some(&(start, end)) = self.intervals.range((value, i32::min)..).next() {
if start <= value + 1 {
right = end;
to_remove.push((start, end));
}
}

// remove old intervals
for interval in to_remove {
self.intervals.remove(&interval);
}

// insert new merged interval
self.intervals.insert((left, right));
}

the add number function:

• initialization: set left and right to value
• left neighbor check: find interval ending before value
• right neighbor check: find interval starting after value
• merging logic: combine overlapping intervals
• cleanup: remove old intervals and insert merged one

4. Left Neighbor Check

if let some(&(start, end)) = self.intervals.range(..(value, i32::max)).next_back() {
if end + 1 >= value {
left = start;
to_remove.push((start, end));
}
}

we check for left neighbor:

• range query: find intervals ending before value
• overlap check: end + 1 >= value means overlap
• merge preparation: mark for removal and update left

5. Right Neighbor Check

if let some(&(start, end)) = self.intervals.range((value, i32::min)..).next() {
if start <= value + 1 {
right = end;
to_remove.push((start, end));
}
}

we check for right neighbor:

• range query: find intervals starting after value
• overlap check: start <= value + 1 means overlap
• merge preparation: mark for removal and update right

6. Get Intervals Function

fn getintervals(&self) -&gt; vec<vec<i32>&gt; {
self.intervals
.iter()
.map(|&(start, end)| vec![start, end])
.collect()
}

the get intervals function:

• iteration: iterate through sorted intervals
• mapping: convert (start, end) tuples to vectors
• collection: collect into result vector
• automatic sorting: btreeset maintains order

Example Walkthrough

let's trace through the example: addnum(1), addnum(3), addnum(7), addnum(2), addnum(6)

step 1: addnum(1)
- intervals = [(1,1)]

step 2: addnum(3)
- intervals = [(1,1), (3,3)]

step 3: addnum(7)
- intervals = [(1,1), (3,3), (7,7)]

step 4: addnum(2)
- left neighbor: (1,1) overlaps with 2
- merge: (1,1) + 2 = (1,2)
- right neighbor: (3,3) overlaps with (1,2)
- final merge: (1,3)
- intervals = [(1,3), (7,7)]

step 5: addnum(6)
- left neighbor: none
- right neighbor: (7,7) overlaps with 6
- merge: 6 + (7,7) = (6,7)
- intervals = [(1,3), (6,7)]

Time and Space Complexity

• time complexity: O(log n) for addnum, O(n) for getintervals
• space complexity: O(n) for storing intervals

the algorithm is efficient because:

• btreeset provides O(log n) operations
• range queries are efficient
• automatic sorting maintenance
• minimal memory overhead

Key Insights

• btree approach - efficient interval management
• range queries - find overlapping intervals quickly
• merging logic - handle left and right neighbors
• rust ownership - automatic memory management

Alternative Approaches

i also considered:

• array approach - maintain sorted array
• O(n) insertion time
• simpler implementation
• less efficient for large inputs
• linked list - use linked list for intervals
• O(n) search time
• more complex implementation
• harder to maintain order
• hash set - track individual numbers
• O(1) insertion time
• O(n) interval building
• inefficient for large ranges
• segment tree - use segment tree
• more complex implementation
• same time complexity
• overkill for this problem

Edge Cases to Consider

• empty stream - return empty intervals
• single number - handle single interval
• consecutive numbers - merge into single interval
• duplicate numbers - handle repeated values
• large ranges - ensure efficient performance
• negative numbers - handle edge cases

Rust-Specific Features

• btreeset - efficient sorted data structure
• ownership system - automatic memory management
• pattern matching - if let some() for option handling
• iterators - efficient collection operations
• type safety - compile-time error checking

Lessons Learned

this problem taught me:

• data structure selection - choosing the right tool
• interval management - efficient merging algorithms
• rust ownership - understanding ownership system
• algorithmic thinking - optimizing for specific operations

Real-World Applications

this problem has applications in:

• database systems - range queries and indexing
• time series analysis - interval-based data processing
• calendar systems - appointment scheduling
• network routing - ip address range management

Conclusion

the data stream as disjoint intervals problem is an excellent exercise in data structure design and interval management. the key insight is using a btreeset for efficient interval operations and leveraging rust's ownership system for safe memory management.

this is part of my leetcode problem-solving series. i'm documenting my solutions to help others learn and to track my own progress.