Skip to content
GKgkml.dev
← Problem set
#155MediumStack & monotonic stack

Min Stack

The tell: Stack operations plus getMin, all required to be O(1).

How you get there

  1. 1The minimum cannot be recomputed on demand without an O(n) scan.
  2. 2Push the running minimum alongside each value, so every level knows its own minimum.
  3. 3Popping discards that level's minimum automatically.

Solution

Python
class MinStack:
    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []   # (value, min at this depth)

    def push(self, val: int) -> None:
        current_min = val if not self._stack else min(val, self._stack[-1][1])
        self._stack.append((val, current_min))

    def pop(self) -> None:
        self._stack.pop()

    def top(self) -> int:
        return self._stack[-1][0]

    def getMin(self) -> int:
        return self._stack[-1][1]
Time
O(1) per operation
Space
O(n)

What goes wrong

Keeping a single min variable breaks on pop, because the previous minimum is unrecoverable.

Test yourself on DSANext: Daily Temperatures →