Dinner plate stacks

Hash Table Stack Design Heap (Priority Queue)

33.5% acceptance

Feb 22, 2026

516

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity. Implement the DinnerPlates class: DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks capacity. void push(int val) Pushes the given integer val into the leftmost stack with a size less than capacity. int pop() Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all the stacks are empty. int popAtStack(int index) Returns the value at the top of the stack with the given index index and removes it from that stack or returns -1 if the stack with that given index is empty.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

pub struct DinnerPlates {
  capacity: usize,
  stacks: Vec<Vec<i32>>,
  non_full: BTreeSet<usize>, // indices of stacks that aren't full
}

impl DinnerPlates {
  pub fn new(capacity: i32) -> Self {
    DinnerPlates {
      capacity: capacity as usize,
      stacks: Vec::new(),
      non_full: BTreeSet::new(),
    }
  }

  pub fn push(&mut self, val: i32) {
    let idx = if let Some(&i) = self.non_full.iter().next() {
      i
    } else {
      let i = self.stacks.len();
      self.stacks.push(Vec::new());
      self.non_full.insert(i);
      i
    };
    self.stacks[idx].push(val);
    if self.stacks[idx].len() == self.capacity {
      self.non_full.remove(&idx);
    }
  }

  pub fn pop(&mut self) -> i32 {
    // Find rightmost non-empty stack
    while let Some(last) = self.stacks.last() {
      if last.is_empty() { self.stacks.pop(); self.non_full.remove(&self.stacks.len()); }
      else { break; }
    }
    if self.stacks.is_empty() { return -1; }
    let idx = self.stacks.len() - 1;
    let val = self.stacks[idx].pop().unwrap();
    self.non_full.insert(idx);
    while self.stacks.last().map_or(false, |s| s.is_empty()) {
      let i = self.stacks.len() - 1;
      self.stacks.pop();
      self.non_full.remove(&i);
    }
    val
  }

  pub fn pop_at_stack(&mut self, index: i32) -> i32 {
    let idx = index as usize;
    if idx >= self.stacks.len() || self.stacks[idx].is_empty() { return -1; }
    let val = self.stacks[idx].pop().unwrap();
    self.non_full.insert(idx);
    val
  }
}