practice · easy · from Stacks

Min Stack

time: O(1)
space: O(n)
tags: stacks · design

in the wild Robot recovery rollback — keep the cheapest known-safe state reachable in O(1) at any depth of a planning stack.

Problem

Design a stack that supports push, pop, top, and a new getMin — all in O(1) time. getMin returns the minimum value currently in the stack.

Examples

push 3      → stack [3]                getMin = 3
push 5      → stack [3, 5]              getMin = 3
push 2      → stack [3, 5, 2]           getMin = 2
push 1      → stack [3, 5, 2, 1]        getMin = 1
pop         → stack [3, 5, 2]           getMin = 2
pop         → stack [3, 5]              getMin = 3

Why this is the canonical stack-design problem

The naïve getMin walks the entire stack to find the smallest value — O(n). That's the obvious answer; making it O(1) is the puzzle.

The trick: maintain a second stack that tracks the running minimum. Each entry on this auxiliary stack is "what is the minimum up through this depth?" When you push x, you push min(x, currentMin) onto the aux stack. When you pop, you pop both. getMin is just the top of the aux stack.

It's a beautiful demonstration of the "remember the past efficiently" idea that recurs in stack problems — every entry carries forward summary state that the LIFO discipline keeps in sync automatically.

Hints

Hint 1 — the obvious O(n) approach

Scan the entire stack to find the minimum. Why is this O(n) per call, and what state would let you avoid the scan?

Hint 2 — auxiliary state

What if, in parallel with the main stack, you maintained a stack of "minimum seen up to and including this point"? Pushing and popping the two stacks together keeps them in sync.

Hint 3 — the auxiliary push rule

When pushing x, push min(x, aux.top) onto aux. (For the first element, push x itself.) When popping, pop both stacks. getMin returns aux.top.

Solution

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.mins:  list[int] = []   # parallel stack of running mins

    def push(self, x: int) -> None:
        self.stack.append(x)
        # New min is whichever is smaller — the new value or the previous min.
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.mins[-1]

# Tests
s = MinStack()
ops = [("push", 3), ("push", 5), ("push", 2), ("push", 1)]
for op, v in ops: s.push(v); print(f"after push {v}: top={s.top()} min={s.get_min()}")
print("---")
for _ in range(2):
    s.pop()
    print(f"after pop:    top={s.top()} min={s.get_min()}")

class MinStack {
  constructor() { this.stack = []; this.mins = []; }
  push(x) {
    this.stack.push(x);
    this.mins.push(this.mins.length === 0 ? x : Math.min(x, this.mins[this.mins.length - 1]));
  }
  pop()    { this.stack.pop(); this.mins.pop(); }
  top()    { return this.stack[this.stack.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

const s = new MinStack();
for (const v of [3, 5, 2, 1]) {
  s.push(v);
  console.log(`after push ${v}: top=${s.top()} min=${s.getMin()}`);
}
console.log("---");
s.pop(); console.log(`after pop:    top=${s.top()} min=${s.getMin()}`);
s.pop(); console.log(`after pop:    top=${s.top()} min=${s.getMin()}`);

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

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

    pub fn push(&mut self, x: i32) {
        self.stack.push(x);
        let new_min = self.mins.last().copied().map_or(x, |m| m.min(x));
        self.mins.push(new_min);
    }

    pub fn pop(&mut self) { self.stack.pop(); self.mins.pop(); }
    pub fn top(&self)    -> i32 { *self.stack.last().unwrap() }
    pub fn get_min(&self) -> i32 { *self.mins.last().unwrap() }
}

fn main() {
    let mut s = MinStack::new();
    for v in [3, 5, 2, 1] {
        s.push(v);
        println!("after push {}: top={} min={}", v, s.top(), s.get_min());
    }
    println!("---");
    s.pop(); println!("after pop:    top={} min={}", s.top(), s.get_min());
    s.pop(); println!("after pop:    top={} min={}", s.top(), s.get_min());
}

#include <iostream>
#include <stack>
#include <algorithm>

class MinStack {
    std::stack<int> stack_;
    std::stack<int> mins_;
public:
    void push(int x) {
        stack_.push(x);
        mins_.push(mins_.empty() ? x : std::min(x, mins_.top()));
    }
    void pop()    { stack_.pop(); mins_.pop(); }
    int  top()     { return stack_.top(); }
    int  getMin()  { return mins_.top(); }
};

int main() {
    MinStack s;
    for (int v : {3, 5, 2, 1}) {
        s.push(v);
        std::cout << "after push " << v << ": top=" << s.top() << " min=" << s.getMin() << "\n";
    }
    std::cout << "---\n";
    s.pop(); std::cout << "after pop:    top=" << s.top() << " min=" << s.getMin() << "\n";
    s.pop(); std::cout << "after pop:    top=" << s.top() << " min=" << s.getMin() << "\n";
}

// C — array-backed with manual capacity. Two parallel stacks.
#include <stdio.h>
#include <stdlib.h>

#define CAP 1024
static int stack_data[CAP];
static int mins_data [CAP];
static int sp = 0;   // shared depth — both stacks grow/shrink together

static int  min2(int a, int b) { return a < b ? a : b; }
static void push(int x) {
    stack_data[sp] = x;
    mins_data [sp] = (sp == 0) ? x : min2(x, mins_data[sp - 1]);
    sp++;
}
static void pop_()      { if (sp > 0) sp--; }
static int  top()       { return stack_data[sp - 1]; }
static int  get_min()   { return mins_data [sp - 1]; }

int main(void) {
    int ops[] = {3, 5, 2, 1};
    for (int i = 0; i < 4; i++) {
        push(ops[i]);
        printf("after push %d: top=%d min=%d\n", ops[i], top(), get_min());
    }
    printf("---\n");
    pop_(); printf("after pop:    top=%d min=%d\n", top(), get_min());
    pop_(); printf("after pop:    top=%d min=%d\n", top(), get_min());
    return 0;
}

idle

The pattern is identical in every language: a second stack, lock-stepped with the first, holding the running minimum at each depth. Push together, pop together — the LIFO discipline keeps them in sync automatically.

Complexity

Time: O(1) for every operation — push, pop, top, getMin. Two array operations per push/pop instead of one.
Space: O(n) — the auxiliary mins-stack doubles the memory footprint. A constant factor of 2; still O(n).
Optimization: You can sometimes save space by only pushing to mins when x ≤ current_min, then on pop only popping mins if stack.top == mins.top. Trades constant memory for branch complexity.

In the wild

Sliding-minimum on a stream is structurally the same — pair every element with the running min up to that point.
Recovery / undo with "best safe state". A robot planner keeps a stack of states; at any depth it can ask "what's the safest state in this branch?" — that's getMin with a cost-comparator.
Compiler scope tracking. When traversing nested scopes, you often want to know "what's the most-restrictive constraint currently in scope?" — parallel-stack pattern again.

Variations

Max stack. Symmetric — replace min with max everywhere.
Median stack (O(log n)). Pure stacks can't do this in O(1); you need a balanced tree or two heaps.
Stack that supports sum. Parallel running-sum stack — same idea, additive instead of comparative.