DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Min Stack

mediumStack and queue Must-do

Problem statement

Build a stack class, MinStack, that supports the usual operations plus one extra:

  • push(val) puts val on top.
  • pop() removes the top value.
  • top() returns the top value without removing it.
  • getMin() returns the smallest value currently anywhere in the stack.

Every one of these should run in constant time. You can assume pop, top and getMin are only called when the stack is not empty.

Examples

Example 1

Input: push(4), push(7), push(2), getMin(), pop(), top(), getMin()

Output: getMin() -> 2, top() -> 7, getMin() -> 4

Explanation: After popping 2, the stack holds 4 and 7, so the smallest is 4 again.

Example 2

Input: push(5), push(5), push(9), pop(), pop(), getMin(), top()

Output: getMin() -> 5, top() -> 5

Explanation: Popping one copy of 5 must not lose the minimum, because another 5 is still there.

Hints

Approach

The trick is that a stack only changes at the top, so the minimum "below" any entry never changes while that entry exists. Save it with the entry.

  1. Each entry is a pair: the value, and the smallest value at or below it.
  2. On push(val), the new pair's minimum is min(val, minimum of the current top), or just val if the stack is empty.
  3. pop removes the top pair. The pair underneath already carries the correct older minimum, so there is nothing to recompute.
  4. top reads the value from the top pair, getMin reads its minimum.

A common variation keeps a second stack that only receives values less than or equal to the current minimum. It saves memory when the minimum rarely changes, but the pair version is simpler to get right.

ComplexityTime O(1) for every operationSpace O(n)
Python
class MinStack:
def __init__(self):
self.items = [] # each entry: (value, smallest value at or below this entry)
def push(self, val: int) -> None:
current_min = min(val, self.items[-1][1]) if self.items else val
self.items.append((val, current_min))
def pop(self) -> None:
self.items.pop()
def top(self) -> int:
return self.items[-1][0]
def getMin(self) -> int:
return self.items[-1][1]

Follow-up questions

  • Support getMax() as well, in constant time.
  • Build a queue that reports its minimum in constant time (hint: two min-stacks).

Frequently asked questions

Duplicates. If the minimum 5 is pushed twice but only recorded once, popping the first 5 removes it from the minimum stack while another 5 is still in the main stack. Recording equal values keeps the counts matched.

Yes, by storing the difference between each value and the current minimum instead of the value itself, and decoding on pop. It works, but it is harder to read and can overflow in fixed-width integers, so mention it rather than lead with it.

It tests whether you can trade a little memory for constant-time reads, which is the same reasoning behind keeping a running minimum or maximum for a metric instead of rescanning a buffer on every dashboard refresh.