Min Stack

Problem

Design a stack that supports push, pop, top, and getMin in constant time.

getMin must return the minimum element currently in the stack.

Intuition

The trick is not to search for the minimum after the fact. That would make getMin linear.

Instead, cache the minimum at each depth of the stack. Every time you push a value, also push the minimum seen so far. Then the current minimum is always the top of the auxiliary stack.

This is the same design move you use in production systems when a derived value is queried often: pay the cost once on mutation, then read it in O(1).

Approach

pub struct MinStack {
    values: Vec<i32>,
    mins: Vec<i32>,
}

impl MinStack {
    pub fn new() -> Self {
        Self {
            values: Vec::new(),
            mins: Vec::new(),
        }
    }

    pub fn push(&mut self, x: i32) {
        let min_so_far = match self.mins.last().copied() {
            Some(curr) => curr.min(x),
            None => x,
        };
        self.values.push(x);
        self.mins.push(min_so_far);
    }

    pub fn pop(&mut self) {
        self.values.pop();
        self.mins.pop();
    }

    pub fn top(&self) -> i32 {
        *self.values.last().unwrap()
    }

    pub fn get_min(&self) -> i32 {
        *self.mins.last().unwrap()
    }
}

class MinStack {
  private values: number[] = [];
  private mins: number[] = [];

  push(x: number): void {
    const minSoFar =
      this.mins.length > 0 ? Math.min(this.mins[this.mins.length - 1], x) : x;
    this.values.push(x);
    this.mins.push(minSoFar);
  }

  pop(): void {
    this.values.pop();
    this.mins.pop();
  }

  top(): number {
    return this.values[this.values.length - 1];
  }

  getMin(): number {
    return this.mins[this.mins.length - 1];
  }
}

Trace

Push -2, 0, -3, then ask for the minimum:

The key invariant is visible in the second column: the top of mins always matches the minimum of values up to that depth.

Edge cases

• Duplicate minima — push the same minimum again when the new value ties the current minimum.
• Negative values — no special handling; the minimum logic is purely comparative.
• Popping the last element — both stacks shrink together, so the data structure stays aligned.

Takeaway

If a query depends on all items currently in a stack, ask whether that answer can be cached on the way in. That is the whole trick here.

The implementation is tiny, but the design pattern is important: build the expensive part into the mutation path so the read path stays O(1).