#155 - Min Stack

MediumStack

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

• push(val) – pushes the element onto the stack.
• pop() – removes the element on top of the stack.
• top() – gets the top element.
• getMin() – retrieves the minimum element in the stack.

Input	Output
Operations	Output
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()	[null,null,null,-3,null,0,-2]

Solution Space

Try it

/**
 * Stack supporting O(1) push, pop, top, and getMin.
 * Uses a parallel min-stack that tracks the running minimum.
 */
export class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
    // Push current min (or val if stack was empty)
    const currentMin =
      this.minStack.length === 0
        ? val
        : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(currentMin);
  }

  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }

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

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

Approach: two stacks – the main stack stores all values; the min-stack mirrors it, storing the minimum value at each depth.

Time: O(1) – every operation is constant time.

Space: O(n) – the min-stack doubles the space.

Alternative approaches:

Approach	Idea	Time	Space
Single stack with tuples	Store [val, currentMin] pairs in one stack	O(1)	O(n) (same asymptotic, but one array)
Min-stack with lazy push	Only push onto min-stack when val ≤ currentMin, pop from min-stack only when popped value equals min	O(1)	O(n) worst case, but often less in practice

Why the two-stack method is preferred: It is the most straightforward to implement and reason about, with no edge-case pitfalls compared to the lazy-push variant.

#2352 Equal Row and Column Pairs

#394 Decode String