A stack that also reports its minimum

Stacks and queues Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

stack: list[tuple[int, int]] = []
for v in [5, 3, 7, 2]:
    low = min(v, stack[-1][1]) if stack else v
    stack.append((v, low))
stack.pop()
print(stack[-1], stack[-1][1])

Options(7, 3) 3(7, 2) 2(2, 2) 2

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A (7, 3) 3

Right: after popping 2, the top pair remembers the minimum 3.

Each pair records the minimum at the time it was pushed, so popping restores the earlier minimum for free.

Why not the others?

B (7, 2) 2. The pair for 7 was pushed before 2 existed, so its minimum is 3.
C (2, 2) 2. The pop removed the pair for 2.

30-second answer

Store pairs on the stack: the value and the smallest value at or below it. Pushing computes the new minimum from the pair underneath; popping removes the pair, which restores the previous minimum automatically. Every operation is O(1) time; space is O(n).

Practise saying it · 45 s. No recording, just a timer

Explain the stack with O(1) minimum.

Say your answer out loud, then check which of these points you covered:

Store (value, min so far)
Pop restores the old min
All operations O(1)

Deep dive

A second stack holding only new minimums saves space when values rarely decrease.

Storing the minimum with each item is the simplest way to make pops correct.

The same idea gives a stack that reports its maximum, or both.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def run_min_stack(ops: list[str]) -> list[int]:
    stack: list[tuple[int, int]] = []  # (value, smallest so far)
    out = []
    for op in ops:
        if op.startswith("push "):
            v = int(op[5:])
            stack.append((v, min(v, stack[-1][1]) if stack else v))
        elif op == "pop":
            stack.pop()
        elif op == "top":
            out.append(stack[-1][0])
        else:  # "min"
            out.append(stack[-1][1])
    return out

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun runMinStack(ops: List<String>): List<Int> {
    val stack = ArrayDeque<Pair<Int, Int>>()
    val out = mutableListOf<Int>()
    for (op in ops) {
        when {
            op.startsWith("push ") -> {
                val v = op.substring(5).toInt()
                val low = if (stack.isEmpty()) v
                    else minOf(v, stack.last().second)
                stack.addLast(v to low)
            }
            op == "pop" -> stack.removeLast()
            op == "top" -> out.add(stack.last().first)
            else -> out.add(stack.last().second)
        }
    }
    return out
}

Common mistakes

Keeping one 'current minimum' variable, which is wrong after the minimum is popped.
Scanning the stack for the minimum, which is O(n).

Senior take & follow-ups

Point out why a single minimum variable fails after a pop. It is the trap the question sets.

Follow-up questions

Think of your answer first, then open the hint.

Can you do it with O(1) extra space?
Show hint
Store encoded differences from the current minimum; it is tricky and overflow-prone in fixed-width languages.
How would you build a queue with O(1) minimum?
Show hint
Two min-stacks, or a monotonic deque.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.