Design an array statistics tracker

Hash Table Binary Search Design Queue Heap (Priority Queue) Data Stream Ordered Set

35.6% acceptance

Mar 31, 2026

Design a data structure that keeps track of the values in it and answers some queries regarding their mean, median, and mode. Implement the StatisticsTracker class. StatisticsTracker(): Initialize the StatisticsTracker object with an empty array. void addNumber(int number): Add number to the data structure. void removeFirstAddedNumber(): Remove the earliest added number from the data structure. int getMean(): Return the floored mean of the numbers in the data structure. int getMedian(): Return the median of the numbers in the data structure. int getMode(): Return the mode of the numbers in the data structure. If there are multiple modes, return the smallest one. Note: The mean of an array is the sum of all the values divided by the number of values in the array. The median of an array is the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the larger of the two values is taken. The mode of an array is the element that appears most often in the array.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::{BTreeMap, VecDeque};

struct StatisticsTracker {
  queue: VecDeque<i32>,
  sum: i64,
  seq: u64,
  // For median: two BTreeMaps acting as sorted halves
  // Keys are (value, seq) for uniqueness
  // Invariant: upper.len() == ceil(n/2), lower.len() == floor(n/2)
  // median = min of upper
  lower: BTreeMap<(i32, u64), ()>,
  upper: BTreeMap<(i32, u64), ()>,
  // Track which seq each value got, in insertion order
  val_seqs: BTreeMap<i32, VecDeque<u64>>,
  // For mode
  freq: BTreeMap<i32, i32>,
  mode_set: BTreeMap<(i32, i32), ()>, // (-freq, value)
}

impl StatisticsTracker {

  fn new() -> Self {
    StatisticsTracker {
      queue: VecDeque::new(),
      sum: 0,
      seq: 0,
      lower: BTreeMap::new(),
      upper: BTreeMap::new(),
      val_seqs: BTreeMap::new(),
      freq: BTreeMap::new(),
      mode_set: BTreeMap::new(),
    }
  }
  
  fn add_number(&mut self, number: i32) {
    self.queue.push_back(number);
    self.sum += number as i64;
    
    let s = self.seq;
    self.seq += 1;
    self.val_seqs.entry(number).or_default().push_back(s);
    
    // Update mode
    let old_freq = *self.freq.get(&number).unwrap_or(&0);
    if old_freq > 0 {
      self.mode_set.remove(&(-old_freq, number));
    }
    let new_freq = old_freq + 1;
    *self.freq.entry(number).or_insert(0) = new_freq;
    self.mode_set.insert((-new_freq, number), ());
    
    // Add to median structure
    let key = (number, s);
    // Add to upper first, then rebalance
    self.upper.insert(key, ());
    self.rebalance();
  }
  
  fn remove_first_added_number(&mut self) {
    if let Some(number) = self.queue.pop_front() {
      self.sum -= number as i64;
      
      let seqs = self.val_seqs.get_mut(&number).unwrap();
      let s = seqs.pop_front().unwrap();
      if seqs.is_empty() {
        self.val_seqs.remove(&number);
      }
      
      // Update mode
      let old_freq = *self.freq.get(&number).unwrap();
      self.mode_set.remove(&(-old_freq, number));
      let new_freq = old_freq - 1;
      if new_freq > 0 {
        *self.freq.get_mut(&number).unwrap() = new_freq;
        self.mode_set.insert((-new_freq, number), ());
      } else {
        self.freq.remove(&number);
      }
      
      // Remove from median structure  
      let key = (number, s);
      if self.upper.contains_key(&key) {
        self.upper.remove(&key);
      } else {
        self.lower.remove(&key);
      }
      self.rebalance();
    }
  }
  
  fn rebalance(&mut self) {
    // Invariant: upper.len() == ceil(n/2), lower.len() == floor(n/2)
    let n = self.lower.len() + self.upper.len();
    let target_upper = (n + 1) / 2;
    let target_lower = n / 2;
    
    while self.upper.len() > target_upper {
      // Move min of upper to lower
      let &key = self.upper.keys().next().unwrap();
      self.upper.remove(&key);
      self.lower.insert(key, ());
    }
    while self.lower.len() > target_lower {
      // Move max of lower to upper
      let &key = self.lower.keys().next_back().unwrap();
      self.lower.remove(&key);
      self.upper.insert(key, ());
    }
    
    // Ensure ordering: max(lower) <= min(upper)
    if !self.lower.is_empty() && !self.upper.is_empty() {
      let &lower_max = self.lower.keys().next_back().unwrap();
      let &upper_min = self.upper.keys().next().unwrap();
      if lower_max > upper_min {
        self.lower.remove(&lower_max);
        self.upper.remove(&upper_min);
        self.lower.insert(upper_min, ());
        self.upper.insert(lower_max, ());
      }
    }
  }
  
  fn get_mean(&self) -> i32 {
    let n = self.queue.len() as i64;
    (self.sum / n) as i32
  }
  
  fn get_median(&self) -> i32 {
    // median = min of upper (which is the ceil(n/2)-th element)
    self.upper.keys().next().unwrap().0
  }
  
  fn get_mode(&self) -> i32 {
    self.mode_set.keys().next().unwrap().1
  }
}

/*
 * Your StatisticsTracker object will be instantiated and called as such:
 * let obj = StatisticsTracker::new();
 * obj.add_number(number);
 * obj.remove_first_added_number();
 * let ret_3: i32 = obj.get_mean();
 * let ret_4: i32 = obj.get_median();
 * let ret_5: i32 = obj.get_mode();
 */