leetcode-textbook

0155 - Min Stack

Difficulty: Medium Pattern: Stack LeetCode: https://leetcode.com/problems/min-stack/

Concepts used

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time.

Signature (the class is named MinStack):

MinStack()                    // constructor
void push(int val)
void pop()
int top()
int getMin()

Methods pop, top, and getMin will always be called on a non-empty stack.

Example (verbatim from LeetCode):

Input:
  ["MinStack","push","push","push","getMin","pop","top","getMin"]
  [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

Intuition

Picture a stack of index cards, each with a number, where you can only see or take the top card. You also want to always know the smallest number in the pile without flipping through every card. The trick: every time you add a card, jot down “the smallest value seen so far” on a sticky note and place that note on a second pile. The second pile’s top always reports the current minimum, and when you remove a card you remove its sticky note too — the two piles move in sync.

Walk through the smallest case, pushing -2, then 0, then -3:

The general rule: keep a second stack that, at every depth, holds the minimum among all values at that depth or below. The two stacks always have the same size, so getMin just reads the top of the min stack. Why a second stack at all, instead of scanning for the min on demand? Scanning is time complexity O(n) per getMin, but the problem demands O(1); the second stack buys O(1) speed by spending O(n) extra memory.

Checkpoint A – Two stacks

Pause and answer before expanding. Wrong guesses teach more than fast right ones.

Q1 (recall). In this design, what does the second stack (mins) hold at every depth?

Show answer **(b)** -- `mins` mirrors `values` one-for-one, so its top is always the minimum of everything currently in the stack.

Q2 (comprehend). On push, when val is NOT a new minimum the code pushes a COPY of the current mins top instead of val. Why?

Show answer **(a)** -- carrying the running min forward makes every push add exactly one entry to `mins`, so `pop` can remove exactly the right partner and `getMin` never scans.

Pseudocode

structure MinStack:
    values = new stack      # the real elements
    mins   = new stack      # parallel: minimum for each prefix

function push(val):
    push val onto values
    if mins is empty or val < top of mins:
        push val onto mins
    else:
        push (top of mins) onto mins      # carry the current min forward

function pop():
    pop from values
    pop from mins

function top():
    return top of values

function getMin():
    return top of mins

Java Solution

import java.util.*;

class MinStack {
    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public void push(int val) {
        values.push(val);
        mins.push(mins.isEmpty() || val < mins.peek() ? val : mins.peek());
    }

    public void pop() {
        values.pop();
        mins.pop();
    }

    public int top() {
        return values.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}

Two ArrayDeques back the design: values holds the real elements and mins holds the running minimum, one entry per element so the two stacks always have the same size. On push we write val to values, and to mins we write val when it is a new minimum, otherwise we copy the current top — that copy is the key invariant: “the top of mins is always the minimum of all live values.” pop removes one entry from each, so getMin is a single O(1) peek. This mirroring costs O(n) extra space but keeps every operation constant time, which is the explicit requirement.

Complexity

Time:  O(1) per operation  -- push/pop/top/getMin each do a constant number of stack ops.
Space: O(n)                 -- the min stack mirrors the main stack, one entry per element.

Dry-Run

Replaying the LeetCode example: push -2, push 0, push -3, getMin, pop, top, getMin.

Operation values (bottom -> top) mins (bottom -> top) return
push(-2) -2 -2 —
push(0) -2, 0 -2, -2 —
push(-3) -2, 0, -3 -2, -2, -3 —
getMin -2, 0, -3 -2, -2, -3 -3
pop -2, 0 -2, -2 —
top -2, 0 -2, -2 0
getMin -2, 0 -2, -2 -2

After popping -3 the top of mins drops back to -2 automatically — no scan required.

Checkpoint B – Trace and stress it

Q1 (apply). Trace: push(5), push(2), push(7), then getMin. What is returned?

Show answer **(a)** -- values = `[5, 2, 7]`, mins = `[5, 2, 2]` (7 is not below 2, so 2 is copied); `getMin` peeks the mins top = 2.

Q2 (analyze). What breaks if you forget to call mins.pop() inside pop()?

Show answer **(b)** -- the two stacks must move in lockstep; skipping `mins.pop` leaves a stale entry on top, so `getMin` reports a value no longer in the stack.

Q3 (transfer). How would you extend the design to also support getMax() in O(1)?

Show answer Add a third parallel stack `maxs` with the same mirroring logic, but push `val` when it is a new MAXIMUM, otherwise copy the current top. All operations stay O(1); the cost is more memory.

Common mistakes