Design an ordered stream

Array Hash Table Design Data Stream

82.6% acceptance

Feb 23, 2026

572

3630

There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. Implement the OrderedStream class: OrderedStream(int n) Constructs the stream to take n values. String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order. Example: Input: ["OrderedStream","insert","insert","insert","insert","insert"] [[5],[3,"ccccc"],[1,"aaaaa"],[2,"bbbbb"],[5,"eeeee"],[4,"ddddd"]] Output: [null,[],["aaaaa"],["bbbbb","ccccc"],[],["ddddd","eeeee"]]

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

pub struct OrderedStream {
  data: Vec<Option<String>>,
  ptr: usize,
}

impl OrderedStream {
  pub fn new(n: i32) -> Self {
    OrderedStream {
      data: vec![None; n as usize + 1],
      ptr: 1,
    }
  }

  pub fn insert(&mut self, id_key: i32, value: String) -> Vec<String> {
    self.data[id_key as usize] = Some(value);
    let mut result = Vec::new();
    while self.ptr < self.data.len() && self.data[self.ptr].is_some() {
      result.push(self.data[self.ptr].take().unwrap());
      self.ptr += 1;
    }
    result
  }
}