Min Stack

Why it belongs on this sheet

This is a very common "augment a data structure" question and a nice interview design exercise.

Pattern

Stack of value plus running minimum

Approach

Store pairs: the pushed value and the minimum value seen up to that point. Then getMin is always the top pair's minimum.

Java solution

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
  private final Deque<int[]> stack = new ArrayDeque<>();

  public void push(int val) {
    int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
    stack.push(new int[] {val, min});
  }

  public void pop() {
    stack.pop();
  }

  public int top() {
    return stack.peek()[0];
  }

  public int getMin() {
    return stack.peek()[1];
  }
}

Complexity

• push, pop, top, getMin: O(1)
• Space: O(n)

Interview note

The separate min-stack version is also valid, but the paired-node approach is compact.