Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Min & Max Stack
DSA

Min & Max Stack

Learn how to design stacks that support retrieving minimum or maximum values efficiently.

A Min/Max Stack is a normal stack that can return the minimum or maximum value in O(1).

Its core advantage:

The top of an auxiliary stack always remembers the answer as of that level — so popping restores the previous min/max automatically.

Focus on recognizing:

“getMin()/getMax()” + O(1) = Track Running State

Pattern Table

PatternTypical QuestionsTrigger
Two StacksDesign MinStackAux stack stores running min
Value + PairMinStack with one stackEach entry carries its own state
Max VariantDesign MaxStackFlip min to max

Mental Trigger

Push → Update state | Pop → Remove state | Query → Peek state.

1. Generic State-Tracking Template (Base)

Watch pushes build [5, 3, 7, 2] while the aux stack snapshots the minimum at each level, then watch pop() restore the previous minimum. Press ▶ to animate, or step through manually.

Min Stack (Two Stacks)

Design a stack that supports push, pop, top, and getMin in O(1). Mirror the main stack with an aux stack that stores the running minimum at each depth, so getMin just peeks the aux top.

Push 5, 3, 7, 2, 3, 7, 2. The MAIN stack is drawn; the AUX stack (running min) is shown in the state chips. Watch both grow together on push and shrink together on pop — popping the top automatically restores the previous minimum. The top pointer marks the current top of both stacks.

STACK VISUALIZER
Steps –
TOP ↓
2
7
3
5
2
7
3
5
STACK (LIFO)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        push(v):  main.push(v)
                      
                        2
                                  minStack.push(min(v, minStack.top()))
                      
                        3
                        pop():    main.pop();  minStack.pop()
                      
                        4
                        getMin(): return minStack.top()
                      
public void push(int val) {
    main.push(val);
    // aux.push( combine(val, aux.peek()) );
}

public void pop() {
    main.pop();
    // aux.pop();  — keep BOTH stacks in sync
}

public int query() {
    return aux.peek();  // O(1), no scanning
}
def push(self, val: int) -> None:
    self.main.append(val)
    # self.aux.append(combine(val, self.aux[-1]))

def pop(self) -> None:
    self.main.pop()
    # self.aux.pop()  — keep BOTH stacks in sync

def query(self) -> int:
    return self.aux[-1]  # O(1), no scanning
void push(int val) {
    main_.push(val);
    // aux_.push(combine(val, aux_.top()));
}

void pop() {
    main_.pop();
    // aux_.pop();  — keep BOTH stacks in sync
}

int query() {
    return aux_.top();  // O(1), no scanning
}
push(val) {
  this.main.push(val);
  // this.aux.push(combine(val, this.aux.at(-1)));
}

pop() {
  this.main.pop();
  // this.aux.pop(); — keep BOTH stacks in sync
}

query() {
  return this.aux[this.aux.length - 1]; // O(1)
}

Everything else in Min/Max Stack is just a modification of this template.

Two rules baked into the base:

  • Every push updates the state — no exceptions.
  • Every pop removes the state — the stacks stay index-aligned.

Pattern 1: Min Stack — Two Stacks

Main holds values; aux snapshots the running min at every depth.

Min Stack (Two Stacks)

Design a stack that supports push, pop, top, and getMin in O(1). Use an auxiliary stack that mirrors the main stack but stores the running minimum at each depth.

Push 5, 3, 7, 2. The aux stack records the minimum at each level. Watch both stacks grow together, then shrink on pop.

STACK VISUALIZER
Steps –
TOP ↓
STACK (LIFO)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        push(x): main.push(x); aux.push(min(x, aux.top))
                      
                        2
                        pop():  main.pop(); aux.pop()
                      
                        3
                        getMin(): return aux.top

Code

class MinStack {
    Stack<Integer> main = new Stack<>();
    Stack<Integer> min = new Stack<>();

    public void push(int val) {
        main.push(val);
        min.push(min.isEmpty()
                ? val
                : Math.min(val, min.peek()));
    }

    public void pop() {
        main.pop();
        min.pop();
    }

    public int top()    { return main.peek(); }
    public int getMin() { return min.peek(); }
}
class MinStack:
    def __init__(self):
        self.main = []
        self.min = []

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

    def pop(self) -> None:
        self.main.pop()
        self.min.pop()

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

    def getMin(self) -> int:
        return self.min[-1]
class MinStack {
    stack<int> main_, min_;
public:
    void push(int val) {
        main_.push(val);
        min_.push(min_.empty()
                  ? val
                  : ::min(val, min_.top()));
    }

    void pop() { main_.pop(); min_.pop(); }
    int top()    { return main_.top(); }
    int getMin() { return min_.top(); }
};
class MinStack {
  constructor() {
    this.main = [];
    this.min = [];
  }

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

  pop() {
    this.main.pop();
    this.min.pop();
  }

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

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

What Changed from the Base Template?

Fill in combine as min

Base:

aux.push(combine(val, aux.peek()));
self.aux.append(combine(val, self.aux[-1]))
aux_.push(combine(val, aux_.top()));
this.aux.push(combine(val, this.aux.at(-1)));

Changed:

min.push(min.isEmpty()
        ? val
        : Math.min(val, min.peek()));
self.min.append(min(val, self.min[-1])
                if self.min else val)
min_.push(min_.empty()
          ? val
          : ::min(val, min_.top()));
this.min.push(
  this.min.length === 0
    ? val
    : Math.min(val, this.min[this.min.length - 1]),
);

because the empty-aux case has no previous minimum to compare against.

Min Stack = Base Template + combine = min + sync both stacks on pop.

Pattern 2: Min Stack — Single Stack (Value + Pair)

Each entry carries its own min — history stored inside the pairs.

Min Stack (Single Stack with Pairs)

Instead of two stacks, store [value, current_min] pairs in a single stack. Each entry remembers the minimum at its depth — pop restores the previous min automatically.

Push 5|5, 3|3, 7|3, 2|2. Each pair carries the running min. Pop discards the top pair and the min falls back.

STACK VISUALIZER
Steps –
TOP ↓
STACK (LIFO)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        push(x): m = min(x, top.min); push [x, m]
                      
                        2
                        pop(): pop [_, m]; return it
                      
                        3
                        getMin(): return top[1]

Same behavior, half the bookkeeping: each entry carries {value, minSoFar}.

Code

class MinStackSingle {
    record Entry(int val, int minSoFar) {}

    Deque<Entry> stack = new ArrayDeque<>();

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

    public void pop()         { stack.pop(); }
    public int top()          { return stack.peek().val(); }
    public int getMin()       { return stack.peek().minSoFar(); }
}
class MinStackSingle:
    def __init__(self):
        self.stack = []  # entries: (val, min_so_far)

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

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

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

    def getMin(self) -> int:
        return self.stack[-1][1]
class MinStackSingle {
    struct Entry { int val; int minSoFar; };
    stack<Entry> st;
public:
    void push(int val) {
        int m = st.empty()
                ? val
                : min(val, st.top().minSoFar);
        st.push({val, m});
    }

    void pop()   { st.pop(); }
    int top()    { return st.top().val; }
    int getMin() { return st.top().minSoFar; }
};
class MinStackSingle {
  constructor() {
    this.stack = []; // entries: [val, minSoFar]
  }

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

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

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

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

What Changed from the Base Template?

One stack instead of two

Base:

Stack<Integer> main;
Stack<Integer> aux;   // separate state stack
self.main = []
self.aux = []   # separate state stack
stack<int> main_;
stack<int> aux_;  // separate state stack
this.main = [];
this.aux = [];  // separate state stack

Changed:

Deque<Entry> stack;  // value + state travel together
self.stack = []  # (val, min_so_far) tuples
stack<Entry> st;  // value + state travel together
this.stack = []; // [val, minSoFar] pairs

because bundling state with each value makes desync impossible by construction.

Single-Stack Min = Base Template + Store {value, state} per entry.

Pattern 3: Max Stack

One flipped comparison turns the whole pattern into a max tracker.

Max Stack

Same as Min Stack but tracks the maximum. The aux stack stores the running max at each depth — pop restores the previous max in O(1).

Push 3, 5, 1, 6. Aux mirrors the main stack but stores max values. Watch the max change as elements are pushed and popped.

STACK VISUALIZER
Steps –
TOP ↓
STACK (LIFO)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        push(x): aux.push(max(x, aux.top))
                      
                        2
                        pop(): main.pop(); aux.pop()
                      
                        3
                        getMax(): return aux.top

Flip one token — combine = max.

Code

public void push(int val) {
    max.push(max.isEmpty()
            ? val
            : Math.max(val, max.peek()));
}
def push(self, val: int) -> None:
    self.max.append(max(val, self.max[-1])
                    if self.max else val)
void push(int val) {
    max_.push(max_.empty()
              ? val
              : ::max(val, max_.top()));
}
push(val) {
  this.max.push(
    this.max.length === 0
      ? val
      : Math.max(val, this.max[this.max.length - 1]),
  );
}

Everything else — pop sync, peek query — is identical to Min Stack.

Min → combine = min | Max → combine = max. Nothing else changes.

Complexity

OperationTime
push()O(1)
pop()O(1)
top()O(1)
getMin()O(1)
getMax()O(1)
SpaceO(n)

Min/Max Stack Pattern Evolution

Base State-Tracking Stack
    ↓
Min Stack — Two Stacks
    (+ combine = min + empty-guard)
    ↓
Min Stack — Single Stack
    (+ bundle {value, state} per entry)
    ↓
Max Stack
    (+ flip combine to max)

Common Mistakes

Not updating state on push.

// Wrong — min goes stale
main.push(val);

// Correct
main.push(val);
min.push(Math.min(val, min.peek()));
# Wrong
self.main.append(val)

# Correct
self.main.append(val)
self.min.append(min(val, self.min[-1]))
// Wrong
main_.push(val);

// Correct
main_.push(val);
min_.push(::min(val, min_.top()));
// Wrong
this.main.push(val);

// Correct
this.main.push(val);
this.min.push(Math.min(val, this.min.at(-1)));

Desyncing the stacks on pop.

Both stacks must pop together — or use the pair layout so desync is impossible.

Querying by scan.

Scanning for the minimum is O(n) and defeats the entire design. The whole point is:

getMin() → aux.peek()     O(1)

Empty-guard on first push.

The first comparison needs a previous state that doesn’t exist yet — guard with isEmpty() before combining.

Recognition Cheat Sheet

If you see…Think…
getMin() in O(1)Aux stack of running minimums
getMax() in O(1)Same, flipped comparator
Pop must restore previous min/maxSnapshot state at every level
Constant memory requestedValue-encoded trick (advanced)

My Private Notes

Notes are auto-saved locally to this device.