The O(n) Club: Min Stack: The Two-Stack Power Move Explained

The O(n) Club: Min Stack — The Two-Stack Power Move Explained

⚡ TL;DR

This interview isn’t a trust fall: don’t scan the stack to get the min. Use two stacks (one for values, one for minimums) so everything is O(1). Here’s what NOT to do:

// Brute force: O(n) getMin. Seriously, don't.
class DummyStack {
    Stack<Integer> s = new Stack<>();
    void push(int x) { s.push(x); }
    void pop() { s.pop(); }
    int top() { return s.peek(); }
    int getMin() { // Sloooow
        return s.stream().min(Integer::compare).get();
    }
}

🧠 How Devs Usually Mess This Up

Classic rookie move: “I’ll just search for the min whenever I need it.” Welcome to O(n), where dreams (and run-time) go to die. Or people panic over duplicate minimums, trying complicated logic. Spoiler: the min stack loves duplicates, just like recruiters love LinkedIn.

🔍 What’s Actually Going On

Think of your stack as a gourmet burger, and at every layer you want to know which patty is the juiciest (or in tech terms, the smallest). Do you really want to cut the thing open each time? No. Just maintain a second stack of current minimums. Every time something goes on, the min stack gets the smaller of “new” vs. “last min.” Pull them off in pairs, and you’re always synched to the right min—no more, no less.

🛠️ PseudoCode

• push(x):
  • Push x onto mainStack.
  • Push min(x, minStack.peek()) onto minStack. (If minStack empty, just push x.)
  • Now minStack’s top always has the current minimum.

  void push(int x) {
    mainStack.push(x);
    if (minStack.isEmpty()) minStack.push(x);
    else minStack.push(Math.min(x, minStack.peek()));
  }

💻 The Code

import java.util.Stack;
 class MinStack {
    private final Stack<Integer> mainStack = new Stack<>();
    private final Stack<Integer> minStack = new Stack<>();
     public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }
    public void pop() {
        mainStack.pop();
        minStack.pop();
    }
    public int top() {
        return mainStack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates rejoice! Min stack is fine if you push 1 three times. It tracks all, pops all, no ghosts of minimum past.
• Don’t break the chain. Pop both stacks every time, or getMin will show you the wrong movie.
• Space is doubled. It’s O(n) since minStack shadows mainStack. Unless your stack is literally Google, it’s fine.
• Advanced: Some daredevils use a single stack of (value, min-so-far) pairs. Go wild, but two stacks keeps it Chandler-simple.

🧠 Interviewer Brain-Tattoo

“If your getMin is O(n), so is my interest in your resume.”