min-stack.ts

/**
 * 155. Min Stack  (Medium)
 * Link: https://leetcode.com/problems/min-stack/
 *
 * Design a stack that supports push, pop, top, and retrieving the minimum
 * element — all in O(1).
 *
 * Example:
 *   push(-2); push(0); push(-3);
 *   getMin() -> -3;  pop();  top() -> 0;  getMin() -> -2
 *
 * Approach:
 *   Alongside the main stack keep a parallel "min stack" whose top is always the
 *   minimum of the current elements. On push, store min(value, currentMin); on
 *   pop, remove from both. Every operation is O(1).
 *
 * Time:  O(1) per operation.
 * Space: O(n)  — the auxiliary min stack.
 */
export class MinStack {
  private readonly stack: number[] = [];
  private readonly mins: number[] = [];

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

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

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

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