SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Min Stack Visualizer

Keep a second stack beside the first. Each push also pushes the minimum so far onto it. Popping both keeps them in step, so the top of the second stack is always the current minimum.

Start the Min Stack simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(1)
Worst timeO(1)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Two stacks side by side: the values, and the minimum at each height.
  2. push(5). The minimum so far is 5, so push 5 onto the min stack too.
  3. push(3). The minimum so far is 3, so push 3 onto the min stack too.
  4. push(7). The minimum so far is 3, so push 3 onto the min stack too.
  5. pop() removes 7 and its minimum 3 together.
  6. getMin() is now 3, read straight from the top.
  7. push(2). The minimum so far is 2, so push 2 onto the min stack too.
  8. pop() removes 2 and its minimum 2 together.
  9. getMin() is now 2, read straight from the top.
  10. pop() removes 2 and its minimum 2 together.
  11. getMin() is now 3, read straight from the top.
  12. pop() removes 3 and its minimum 3 together.
  13. getMin() is now 5, read straight from the top.
  14. Done. Every operation was O(1): no search for the minimum ever happened.

Try it with your own input →

Min stack in Java, Python, C++, C and JavaScript

class MinStack {
  Deque<Integer> st = new ArrayDeque<>(), mins = new ArrayDeque<>();
  void push(int x) {
    st.push(x);
    mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
  }
  void pop() { st.pop(); mins.pop(); }
  int getMin() { return mins.peek(); }
}
class MinStack:
    def __init__(self):
        self.st, self.mins = [], []
    def push(self, x):
        self.st.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self):
        self.st.pop(); self.mins.pop()
    def get_min(self):
        return self.mins[-1]
class MinStack {
  stack<int> st, mins;
public:
  void push(int x) {
    st.push(x);
    mins.push(mins.empty() ? x : min(x, mins.top()));
  }
  void pop() { st.pop(); mins.pop(); }
  int getMin() { return mins.top(); }
};
#define CAP 1000
typedef struct {
  int st[CAP], mins[CAP], top;
} MinStack;

void push(MinStack* s, int x) {
  s->st[s->top] = x;
  int m = s->top == 0 ? x : s->mins[s->top - 1];
  s->mins[s->top++] = x < m ? x : m;
}
void pop(MinStack* s) { s->top--; }
int getMin(MinStack* s) { return s->mins[s->top - 1]; }
class MinStack {
  st = []; mins = [];
  push(x) {
    this.st.push(x);
    this.mins.push(this.mins.length === 0 ? x : Math.min(x, this.mins[this.mins.length - 1]));
  }
  pop() { this.st.pop(); this.mins.pop(); }
  getMin() { return this.mins[this.mins.length - 1]; }
}

In an interview

LeetCode 155, Min Stack: push, pop, top and getMin, all in O(1).

The min stack can store a copy only when the new value is ≤ the current minimum, saving space; then pop it only when the popped value equals its top. Use ≤, not <, or duplicates break.

More lists, stacks & queues