Min Stack

Design a class MinStack that behaves like a normal stack but can also tell you its current minimum at any moment.

Implement:

• MinStack() creates an empty stack.
• push(val) puts val on top of the stack.
• pop() removes the top element. It returns nothing.
• top() returns the top element without removing it.
• getMin() returns the smallest value currently in the stack.

Every operation must run in O(1) time. pop, top and getMin are only ever called when the stack is non-empty.

In the tests, each case is a list of operations and their arguments. The first operation constructs the stack, and the expected output lists what each call returns (null for the constructor, push and pop).

A stack only ever changes at the top. That means the minimum of the stack is fully determined by which elements are below the top, and those never change while the top element is sitting there.

So when you push a value, you already know the answer getMin should give for as long as that value is on top: the smaller of the new value and the minimum just below it. Store that number alongside the value. Popping then automatically "restores" the old minimum, because it's sitting in the entry underneath. You never have to search for a new minimum after removing the old one.

class MinStack:
    def __init__(self):
        self.stack = []  # (value, minimum including this value)

    def push(self, val: int) -> None:
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

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

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

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

class MinStack {
  constructor() {
    this.stack = []; // [value, minimum including this value]
  }

  push(val) {
    const n = this.stack.length;
    const currentMin = n === 0 ? val : Math.min(val, this.stack[n - 1][1]);
    this.stack.push([val, currentMin]);
  }

  pop() {
    this.stack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1][0];
  }

  getMin() {
    return this.stack[this.stack.length - 1][1];
  }
}

The key sentence is "the minimum below an element can't change while that element is on the stack, so I can cache it at push time." Say it before you code; it shows you understand why the trick is safe rather than having memorized it.

If you choose the two-stack version, call out the duplicate case explicitly and walk through push 1, push 1, pop, getMin. Interviewers often ask for exactly that trace.