Skip to content
16-Week DSA Roadmap
LeetCode #155MediumProblem 2 of 8

Min Stack

Build a stack that can also tell you its smallest value in one step, at any moment.

  • Auxiliary stack (running min)
  • Design a data structure

Before this, know: What a stack is (push, pop, peek), Classes and methods (class in JavaScript and Python)

The problem in plain English

This one is different from most problems: instead of writing one function, you write a whole class. A class is a blueprint for an object that keeps its own data between calls (here, the stack) and has several methods (functions that belong to the object). This kind of problem is called a design problem.

Your MinStack class needs five things:

  • MinStack(): the constructor. It runs once, when the object is created, and sets up empty storage.
  • push(val): put val on top of the stack.
  • pop(): remove the top item. It returns nothing.
  • top(): return the top item without removing it.
  • getMin(): return the smallest value currently in the stack.

The catch: every one of them must take O(1) time, meaning a fixed number of steps no matter how many items are on the stack. That’s easy for the first four. getMin is the hard part.

How LeetCode tests a design problem

LeetCode doesn’t call a function once. It gives you two lists: the method names to call, in order, and the arguments for each call:

["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"][[],         [-2],   [0],    [-3],   [],       [],    [],    []]

Its test code reads them in pairs and does this:

const obj = new MinStack(); // "MinStack", []obj.push(-2);               // "push", [-2]obj.push(0);                // "push", [0]obj.push(-3);               // "push", [-3]obj.getMin();               // returns -3obj.pop();obj.top();                  // returns 0obj.getMin();               // returns -2

It collects what each call returns (null for calls that return nothing) and compares with the expected output: [null, null, null, null, -3, null, 0, -2].

after 3 pushes
  1. -2
  2. 0
  3. -3
after pop()
  1. -2
  2. 0
After push(-2), push(0), push(-3): the smallest value is -3. After one pop, -3 is gone and the smallest is -2 again.

LeetCode promises pop, top and getMin are only called on a non-empty stack, and there are at most 30,000 calls.

Before you code: think it through

The trick is that a stack only changes at the top. So the “smallest value so far” at each height never changes once it’s written: removing the top can never change what was true about the items underneath.

Pause and think

Push 4, then 6, then 1, then 6. What is the minimum after each push? Now pop twice. What is the minimum now, and did you have to look at the remaining items to know it?

Approach 1: Brute force

Keep one normal stack. push, pop and top are easy. For getMin, walk through every item and remember the smallest one.

Brute force: getMin scans the whole stack

push(5), push(2), push(8), push(3), getMin(), pop(), getMin()

stack
  1. 5
variables
call
push(5)
smallest
—
returns
—
items looked at (total)
0
  • Looking at
  • Smallest so far

push(5): put it on top. Fast.

Step 1 / 14

Which line is running?

class MinStack {  constructor() {    this.stack = [];  }  push(val) {Running now:     this.stack.push(val);  }  pop() {    this.stack.pop();  }  top() {    return this.stack.at(-1);  }  getMin() {    let smallest = Infinity;    for (const x of this.stack) {      smallest = Math.min(smallest, x); // look at EVERY item    }    return smallest;  }}

Brute force: getMin scans everything

class MinStack {  constructor() {    this.stack = [];  }  push(val) {    this.stack.push(val);  }  pop() {    this.stack.pop();  }  top() {    return this.stack.at(-1);  }  getMin() {    let smallest = Infinity;    for (const x of this.stack) {      smallest = Math.min(smallest, x); // look at EVERY item    }    return smallest;  }}
class MinStack:    def __init__(self):        self.stack = []    def push(self, val):        self.stack.append(val)    def pop(self):        self.stack.pop()    def top(self):        return self.stack[-1]    def getMin(self):        smallest = float("inf")        for x in self.stack:            smallest = min(smallest, x)  # look at EVERY item        return smallest

this.stack.at(-1) (JavaScript) and self.stack[-1] (Python) both mean “the last item”, which is the top of the stack.

Why is it slow?

getMin looks at every item, every time it’s called. With 4 items that’s 4 looks. With 15,000 items pushed and then 15,000 getMin calls, that’s 15,000 × 15,000 = 225,000,000 looks. A single getMin is O(n), and the problem explicitly asks for O(1).

The pattern: auxiliary stack for a running minimum

An auxiliary stack is a helper stack that rides along with the main one. For every value we push, we also push a note on the helper: “the smallest value from the bottom up to here”.

Pattern

Auxiliary stack (running min or max)

Template

Use it when: you need the minimum or maximum of a stack (or anything that only changes at one end) at any moment, in O(1).

Signal words

  • “design a stack”
  • “retrieve the minimum in constant time”
  • “getMin”
  • “max stack”
  • “O(1) each operation”

Approach 2: Two stacks side by side

  1. In the constructor, create two empty stacks: stack for the values and mins for the running minimum.
  2. push(val): push val on stack. Work out the new minimum: the smaller of val and the old minimum (the top of mins). If mins is empty, the new minimum is just val. Push that on mins.
  3. pop(): pop both stacks. They always stay the same height.
  4. top(): return the top of stack.
  5. getMin(): return the top of mins.

Press Play. Watch the two stacks grow and shrink together, and notice that getMin never searches: it just reads the top of mins. The “repeated minimum” example shows why we push a copy of the minimum even when it doesn’t change.

Two stacks side by side

push(5), push(2), push(8), getMin(), pop(), pop(), getMin()

stackthe values
  1. empty
minsmin so far
  1. empty
this call
call
new MinStack()
returns
—
output (what LeetCode collects)
  1. null
  • Just pushed
  • Previous minimum
  • Value returned

LeetCode first creates the object. Our MinStack starts with two empty stacks: "stack" holds the values, "mins" holds the smallest value seen so far at each height.

Step 1 / 15

Which line is running?

class MinStack {  constructor() {    this.stack = [];Running now:     this.mins = []; // mins[i] = smallest value in stack[0..i]  }  push(val) {    this.stack.push(val);    const prevMin = this.mins.length > 0 ? this.mins.at(-1) : val;    this.mins.push(Math.min(val, prevMin));  }  pop() {    this.stack.pop();    this.mins.pop(); // the two stacks always shrink together  }  top() {    return this.stack.at(-1);  }  getMin() {    return this.mins.at(-1);  }}

The code, line by line

Two stacks

class MinStack {  constructor() {    this.stack = [];    this.mins = []; // mins[i] = smallest value in stack[0..i]  }  push(val) {    this.stack.push(val);    const prevMin = this.mins.length > 0 ? this.mins.at(-1) : val;    this.mins.push(Math.min(val, prevMin));  }  pop() {    this.stack.pop();    this.mins.pop(); // the two stacks always shrink together  }  top() {    return this.stack.at(-1);  }  getMin() {    return this.mins.at(-1);  }}
class MinStack:    def __init__(self):        self.stack = []        self.mins = []  # mins[i] = smallest value in stack[0..i]    def push(self, val):        self.stack.append(val)        prev_min = self.mins[-1] if self.mins else val        self.mins.append(min(val, prev_min))    def pop(self):        self.stack.pop()        self.mins.pop()  # the two stacks always shrink together    def top(self):        return self.stack[-1]    def getMin(self):        return self.mins[-1]

The two versions have the same shape. JavaScript’s closing } lines make its line numbers run a little ahead; we give both when they differ.

  • Line 1: class MinStack starts the blueprint. LeetCode gives you exactly this skeleton with empty methods; you fill them in.
  • Lines 2–4: the constructor (constructor() in JavaScript, __init__(self) in Python) runs once when LeetCode does new MinStack() / MinStack(). this. / self. means “this object’s own”, so the two arrays live as long as the object.
  • Line 8 (JS) / line 7 (Py): a normal push onto the value stack.
  • Line 9 (JS) / line 8 (Py): the previous minimum is the top of mins. If mins is empty (this is the first push), there is no previous minimum, so we use val itself. cond ? a : b (JS) and a if cond else b (Py) both mean “if cond then a, otherwise b”.
  • Line 10 (JS) / line 9 (Py): push the smaller of the two. Math.min / min return the smaller of their arguments.
  • Lines 14–15 (JS) / 12–13 (Py): pop both stacks. Forgetting the second pop is the classic bug: the stacks drift apart and getMin starts lying.
  • Line 19 (JS) / 16 (Py): top reads the last item of stack.
  • Line 23 (JS) / 19 (Py): getMin reads the last item of mins. One step.

Dry run

Calls: push(5), push(2), push(8), getMin(), pop(), pop(), getMin(). Stacks are written bottom → top.

callstack aftermins afterreturns
push(5)[5][5]null
push(2)[5, 2][5, 2]null
push(8)[5, 2, 8][5, 2, 2]null
getMin()[5, 2, 8][5, 2, 2]2
pop()[5, 2][5, 2]null
pop()[5][5]null
getMin()[5][5]5
push 5, push 2, push 8, getMin, pop, pop, getMin

Look at the push(8) row: 8 is not a new minimum, so mins gets another 2. That copy is what keeps the two stacks the same height, and it’s why the last row can answer 5 instantly after the 2 is popped.

Complexity

Brute force (scan on getMin)

Time

O(1) push/pop/top, O(n) getMin

getMin looks at every item on the stack, every time.

Space

O(n)

One stack holding up to n values.

Two stacks

Time

O(1) for every method

Each method does a fixed number of pushes, pops or reads, however tall the stack is.

Space

O(n)

Two stacks of n items each: 2n, which still grows in a straight line with n.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Clarify the API and the O(1) requirement for every method, including getMin.
  2. Mention the naive version: “scan on getMin is O(n), so it fails the requirement.”
  3. Spot the key fact: “a stack only changes at the top, so the minimum at each height never changes after it’s pushed.”
  4. Propose the auxiliary mins stack, and say that both stacks are always the same height.
  5. Walk through a pop of the current minimum to show the old minimum comes back for free.

Likely follow-up questions:

  • “Max stack?” Same idea with Math.max / max.
  • “Can you use less memory?” Push to mins only when val <= mins.top (note the <=, for duplicates).
  • “Min of a queue?” Harder: a queue changes at both ends. Two stacks can simulate a queue, each with its own min stack.

Related problems:

  • Valid Parentheses (this week): the stack basics.
  • Daily Temperatures (this week): another stack that keeps extra order information to answer questions fast.
  • The week 3 overview has the template.