Design a Min Stack

Difficulty: Medium · Pattern: Design · Concept: General Coding (DSA) — Core Patterns to Drill

Design problems ask you to build a small data structure that supports a specific set of operations, each under a specific time-complexity constraint — the constraint is the actual problem, not the individual operations in isolation.

Here: a stack that supports the usual push/pop/top, plus get_min() — return the current minimum element — and every operation must run in $O(1)$ . The obvious approach (scan the whole stack for the minimum on every get_min() call) is $O(n)$ and fails that constraint; the trick is maintaining the running minimum incrementally as things are pushed and popped, not recomputing it.

Your task: implement a MinStack class with push(val), pop() (returns the popped value), top() (returns the top value without removing it), and get_min() (returns the current minimum) — each $O(1)$ .

Implement it yourself

assert ms.push(5) is None
assert ms.get_min() == 5
assert ms.push(3) is None
assert ms.get_min() == 3
assert ms.push(7) is None
assert ms.get_min() == 3
assert ms.pop() == 7
assert ms.get_min() == 3
assert ms.pop() == 3
assert ms.get_min() == 5
assert ms.top() == 5

Next: Design an LRU Cache (a harder Design problem), or continue to Merge K Sorted Lists