Marauder Bot

Problem

Design a stack-like data structure that supports the usual push and pop operations and retrieving the top element, and that also retrieves the minimum value currently in the stack, all in constant time, regardless of how many elements are stored.

Example. Push 5, then 2, then 4. The minimum is 2. Pop once, removing 4; the minimum is still 2. Pop again, removing 2; the minimum becomes 5, the only element left.

Key idea

Recomputing the minimum by scanning the whole stack on every query costs O(n) per call, defeating the purpose of a fast data structure. The fix is to stop computing the minimum on demand and instead track it incrementally as the stack changes.

Maintain a second, parallel stack that records the minimum value at each point in the main stack's history. Every push onto the main stack pushes a value onto the min-stack too: either the new value itself, if it is smaller than the min-stack's current top, or a repeat of that top otherwise. This way, the min-stack's top always equals the minimum of everything currently in the main stack. Popping is symmetric: pop from both stacks together, so the min-stack's new top automatically reflects the minimum of what remains, with no rescanning required.

Solution

class MinStack {
  private stack: number[] = [];
  // Parallel stack whose top always holds the min of everything below it in stack.
  private minStack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
    const currentMin = this.minStack.length === 0 ? val : this.minStack[this.minStack.length - 1];
    // Push the smaller of the new value and the running min, so both stacks stay in sync.
    this.minStack.push(Math.min(val, currentMin));
  }

  pop(): void {
    // Pop both stacks together so minStack's new top reflects what remains.
    this.stack.pop();
    this.minStack.pop();
  }

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

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

Complexity

Time: O(1). Every operation (push, pop, top, get-minimum) touches only the tops of the two stacks.
Space: O(n). The auxiliary min-stack grows in step with the main stack.

Watch out for

Keep the two stacks synchronized: every push and pop on the main stack needs a matching push or pop on the min-stack, even when the pushed value is not a new minimum.
When a value ties the current minimum, push the duplicate rather than skipping it, so popping one copy still leaves the correct minimum behind.

Pattern

This is the auxiliary-stack pattern: pairing a primary stack with a shadow stack that tracks a running aggregate. The same trick extends to tracking a running maximum or sum alongside stack operations.

Min Stack