min-stack

Difficulty: Easy  ·  Topic: Stack  ·  Practice it on parikshan: /practice/min-stack/start

The story

A backend team at Datadog tracks the lowest latency seen in the most recent execution-context window of a request. As nested function calls enter the context, their latencies are pushed onto a per-request stack. As calls return, latencies are popped. At any moment the team's tracing UI wants two answers: "what is the latency of the deepest call?" and "what is the minimum latency in the entire current call stack?" Both must be O(1), because the tracer runs in the request hot path and cannot afford a linear scan.

That is min-stack. A stack that, beyond push and pop, exposes a constant-time getMin. The technique that solves it (an auxiliary stack of running minima) reappears in countless real systems.

What's actually being asked

Design a class with:

• push(x): push integer x.
• pop(): remove and discard the top.
• top(): return the top.
• getMin(): return the smallest element currently on the stack.

All four operations must be O(1) time.

The naive approach

Use a plain stack for storage and on each getMin, scan the entire stack. O(n) per query. For 10^5 operations many of which are getMin, this is O(n^2) total and times out.

Alternatively, maintain a single min_value variable. Updates on push are easy. But pop: if you just popped the current minimum, what is the new minimum? You have no information; you would have to rescan. Same O(n) per pop in the worst case.

The key insight

Maintain a second, parallel stack of running minima. Whenever you push x onto the main stack, push min(x, top_of_min_stack) onto the min stack (or, if the min stack is empty, push x). Whenever you pop, pop both stacks. getMin reads the top of the min stack.

Invariant: at every moment, the top of the min stack equals the minimum of all values currently in the main stack. The two stacks rise and fall together, so the invariant is preserved through every operation, and every operation is O(1).

Memory: O(n) for the second stack. That is the price of constant-time min over arbitrary insertions and deletions.

A space-optimised variant

You can compress the min stack by only pushing when the new value is <= the current min, and only popping when the popped main value equals the current min. This saves memory on inputs with many non-decreasing pushes, but the worst case is still O(n). The unconditional-push version is simpler and equally correct; the conditional version is a nice optimisation to mention in interviews if asked.

Step-by-step approach

1. stack = [], min_stack = [].
2. push(x):
   • Append x to stack.
   • Append x if min_stack is empty else min(x, min_stack[-1]) to min_stack.
3. pop():
   • Pop from both stack and min_stack.
4. top():
   • Return stack[-1].
5. getMin():
   • Return min_stack[-1].

Worked example

Sequence: push 3, push 5, push 2, push 1, getMin, pop, getMin, pop, getMin.

The min stack tracks the minimum at each prefix depth. When we pop, we automatically revert to the previous depth's minimum. That is the entire trick.

Complexity

• Time: O(1) per operation.
• Space: O(n) total, where n is the maximum stack depth reached.

Common pitfalls

• Using a single min_value variable: works for push and getMin, but pop breaks. A single variable cannot remember the second-smallest.
• Recomputing min on getMin by scanning: technically O(n), violates the spec.
• Forgetting to push to the min stack on every push: even when the new value is not the minimum, you must push something to keep the two stacks parallel.
• Pushing the wrong value on the min stack when it is empty: must seed with x itself, not zero or negative infinity. Otherwise getMin returns nonsense after the first push.
• Returning a value from a pop: this spec's pop is void (returns null per the I/O format); top is the read.

Where this shows up in the enterprise

• Datadog / New Relic / Honeycomb distributed tracing: per-request running minima over the call stack (latency, allocation, span depth).
• Compiler symbol-table management: scoping where the "minimum scope depth of a free variable" must be queryable.
• Game engines (Unity / Unreal): rendering pipelines maintain stacks of states with cheapest-resource lookup.
• Browser dev tools: call-stack inspectors that report the minimum frame-time within the currently active stack.
• Trading position bookkeeping: stack of open positions with constant-time "lowest cost basis" query for tax-lot accounting (FIFO/LIFO modes).
• Database transaction logs: nested savepoints with quick access to the minimum sequence number in the active set.
• Memory profilers (Valgrind, AddressSanitizer): nested allocation contexts with cheapest-allocation lookup.

The pattern is generalisable: stack plus auxiliary stack of running aggregates. The aggregate can be min, max, sum, gcd, or any associative reducer that supports "undo on pop".

Variants you'll see elsewhere

• max-stack: same with max. Symmetric.
• stack-of-plates / set-of-stacks: design a stack that wraps to a new physical stack when the current one is full.
• monotonic-stack for "next greater" / "next smaller": same idea, applied to indices.
• deque-with-min: same trick on a double-ended queue.
• running-median (data-stream-median): two heaps, same "auxiliary structure" mindset.

How parikshan turns this into a learning loop

The dynamic private tests on parikshan are designed to catch the typical bugs:

• A test where the minimum is popped and the new minimum must be recovered (the single-variable approach fails here).
• A test where push order is strictly decreasing (every push is a new minimum).
• A test where push order is strictly increasing (the minimum never changes; tests that you still push correctly).
• A test where the same value appears multiple times and only one copy is removed at a time (tests that you do not over-eagerly free the min).
• A test with intermixed top and getMin calls (tests that you do not confuse them).

If your first attempt uses a single variable and you fail the first test, the platform's verdict points you at the exact failure. The integrity-scored AI sparring partner is the right place, in practice mode, to ask "why do I need a stack of minimums and not a single variable?" before exam mode. Once you can articulate the answer ("because pop can revert to a prior minimum and a single variable cannot remember it"), the pattern is yours.

In the AI-integrated workspace

An agent writing a "stack with cheap min" abstraction will sometimes produce the single-variable version. Your review:

1. Can the implementation answer getMin correctly after a pop that removed the current minimum? This is the one test that breaks the wrong implementation.
2. Are both stacks growing in lockstep, with the same number of elements at all times?
3. Does pop pop both stacks (a common bug is popping only the main one)?
4. Does the constructor initialise both stacks to empty?

Beyond min-stack itself, the pattern is "auxiliary-structure stack". Engineers who recognise it will use it for any "stack with running X" operation in production. The agent will not invent the pattern; you direct it.

min-stack is the second canonical stack problem in this curriculum after valid-parentheses. Together they cover the two main stack idioms: matching (the parentheses) and auxiliary running state (this one). Master both, and the rest of the cluster is mostly application.