Vibe Engines Learn
CODING CHALLENGE · N°30

Min Stack

Easy StackData StructuresDesign

A stack that also returns its minimum in O(1) — no scanning. The trick is to carry the running minimum alongside each element. Replay a sequence of push/pop/top/getMin operations and return the outputs. Solve it in Python or TypeScript, with hidden tests.

The problem

Design a stack that supports push(x), pop(), top(), and getMin() — each in O(1) time. You are given a list of ops such as ["push",5], ["pop"], ["top"], ["getMin"]. Apply them in order and return the list of values produced by the read operations (top and getMin), in order.

EXAMPLE 1
Input ops = [["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]]
Output [3, 5, 5]
min is 3, then after pop the min is 5 and top is 5
EXAMPLE 2
Input ops = [["push",2],["push",2],["getMin"],["pop"],["getMin"]]
Output [2, 2]
duplicate mins must be tracked correctly
CONSTRAINTS
  • Every pop/top/getMin is called on a non-empty stack.
  • All four operations must be O(1) — do not scan the stack to find the minimum.
  • Duplicate minimum values must survive a single pop (the min only rises once all copies are gone).
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement min_stack_ops(ops): maintain a stack plus a parallel "min so far" stack. On push, record min(x, current_min); on pop, drop both. Collect the outputs of every top and getMin.

HINTS — 4 IDEAS
  1. The naive getMin scans the stack — O(n). To get O(1), store the minimum as of each push next to the value.
  2. Keep a second stack mins: when you push x, push min(x, mins[-1]) (or just x if empty).
  3. On pop, pop both stacks together so mins[-1] always reflects the current stack.
  4. This is why duplicates matter: pushing the min twice puts it on mins twice, so one pop does not lose it.
CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Algorithms & DSA