Min Stack | O(1) Min/Max Operations | Stack

Overview

A min stack (or max stack) supports the usual push/pop/peek and also getMin() (or getMax()) in O(1) time. The idea: keep a second stack that tracks the minimum (or maximum) among all elements currently in the main stack. When you push, if the new value is ≤ current min, push it onto the min stack too. When you pop, if the popped value equals the top of the min stack, pop from the min stack. getMin() is peek at the min stack.

Why it works: The min stack stays non-increasing (each new min pushes). Popping the current minimum from the main stack triggers a pop from the min stack, so the top remains the minimum of what is left.

When to Use

Get min/max in O(1) while supporting push/pop.
Sliding window min/max can use a deque; min stack is the single-stack variant for "all elements so far."

How It Works

Main stack: stores all values.
Min stack: push only when new value ≤ current min (non-increasing). Pop from min stack when main stack pops that value.
getMin: return top of min stack.

Example 1: Min Stack (Standard)

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];
  push(val: number): void {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1])
      this.minStack.push(val);
  }
  pop(): void {
    const x = this.stack.pop()!;
    if (this.minStack[this.minStack.length - 1] === x) this.minStack.pop();
  }
  top(): number { return this.stack[this.stack.length - 1]; }
  getMin(): number { return this.minStack[this.minStack.length - 1]; }
}

Use ≤ so duplicate minimums are stored; popping one duplicate does not break getMin. Time: O(1) per op. Space: O(n).

Example 2: Max Stack

Same pattern: auxiliary stack stays non-decreasing. Push to max stack when val ≥ current max; pop from max stack when main stack pops that value.

class MaxStack {
  private stack: number[] = [];
  private maxStack: number[] = [];
  push(val: number): void {
    this.stack.push(val);
    if (this.maxStack.length === 0 || val >= this.maxStack[this.maxStack.length - 1])
      this.maxStack.push(val);
  }
  pop(): void {
    const x = this.stack.pop()!;
    if (this.maxStack[this.maxStack.length - 1] === x) this.maxStack.pop();
  }
  top(): number { return this.stack[this.stack.length - 1]; }
  getMax(): number { return this.maxStack[this.maxStack.length - 1]; }
}

Example 3: Min Stack with (value, count) for Duplicates

When the same minimum appears many times, store (minValue, count) on the min stack to avoid repeating the value. Push (val, 1) when val < current min; when val === current min, increment count. Pop from min stack only when count becomes 0 after decrementing.

class MinStackCompact {
  private stack: number[] = [];
  private minStack: [number, number][] = [];
  push(val: number): void {
    this.stack.push(val);
    if (this.minStack.length === 0 || val < this.minStack[this.minStack.length - 1][0])
      this.minStack.push([val, 1]);
    else if (val === this.minStack[this.minStack.length - 1][0])
      this.minStack[this.minStack.length - 1][1]++;
  }
  pop(): void {
    const x = this.stack.pop()!;
    const top = this.minStack[this.minStack.length - 1];
    if (x === top[0]) { top[1]--; if (top[1] === 0) this.minStack.pop(); }
  }
  getMin(): number { return this.minStack[this.minStack.length - 1][0]; }
}

Example 4: Stack with Both getMin and getMax

Use two auxiliary stacks: one non-increasing (min), one non-decreasing (max). Push/pop main stack and update both min and max stacks by the same rules as above.

class MinMaxStack {
  private stack: number[] = [];
  private minStack: number[] = [];
  private maxStack: number[] = [];
  push(val: number): void {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1])
      this.minStack.push(val);
    if (this.maxStack.length === 0 || val >= this.maxStack[this.maxStack.length - 1])
      this.maxStack.push(val);
  }
  pop(): void {
    const x = this.stack.pop()!;
    if (this.minStack[this.minStack.length - 1] === x) this.minStack.pop();
    if (this.maxStack[this.maxStack.length - 1] === x) this.maxStack.pop();
  }
  getMin(): number { return this.minStack[this.minStack.length - 1]; }
  getMax(): number { return this.maxStack[this.maxStack.length - 1]; }
}

Example 5: Step-by-Step Trace

Push 5, 3, 4, 1, 2. Main: [5,3,4,1,2]. Min stack: push 5; push 3 (3 ≤ 5); skip 4 (4 > 3); push 1 (1 ≤ 3); skip 2 (2 > 1). So min stack: [5,3,1]. getMin() = 1. pop() removes 2 from main, min unchanged. pop() removes 1 from main, so pop from min stack → min stack [5,3]. getMin() = 3. top() = 4.

Edge Cases

Duplicate minimum: Push same min again → push onto min stack too (or use count); pop only when main stack pops that value.
Empty stack: getMin/top undefined; document or throw.

Summary

Min stack: auxiliary stack non-increasing; push when val ≤ current min; pop when main stack pops that min. Max stack: same with ≥ and non-decreasing. See Stack Basics and Monotonic Stack.

Min Stack / Max Stack