Skip to content

Min Stack

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Approach

Store (value, current_min) tuples on the stack. Each entry records the minimum at the time it was pushed, so getMin is always O(1) by reading the top tuple's min field.

When to Use

Augmented data structure for O(1) aggregate queries — "get min/max while supporting push/pop". Pattern: store auxiliary data alongside each element. Useful for real-time monitoring dashboards.

Complexity
Time O(1) for all operations
Space O(n) -- one tuple per element

Implementation

min_stack

Min stack.

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Approach

Store (value, current_min) tuples on the stack. Each entry records the minimum at the time it was pushed, so getMin is always O(1) by reading the top tuple's min field.

When to use

Augmented data structure for O(1) aggregate queries — "get min/max while supporting push/pop". Pattern: store auxiliary data alongside each element. Useful for real-time monitoring dashboards.

Complexity

Time: O(1) for all operations Space: O(n) -- one tuple per element

MinStack

Stack supporting O(1) push, pop, top, and get_min.

ms = MinStack() ms.push(-2) ... ms.push(0) ... ms.push(-3) ms.get_min() -3 ms.pop() ms.get_min() -2

Source code in src/algo/stacks_queues/min_stack.py 
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class MinStack:
    """Stack supporting O(1) push, pop, top, and get_min.

    >>> ms = MinStack()
    >>> ms.push(-2)
    ... ms.push(0)
    ... ms.push(-3)
    >>> ms.get_min()
    -3
    >>> ms.pop()
    >>> ms.get_min()
    -2
    """

    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []

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

    def pop(self) -> None:
        if not self._stack:
            msg = "pop from empty stack"
            raise IndexError(msg)
        self._stack.pop()

    def top(self) -> int:
        if not self._stack:
            msg = "top from empty stack"
            raise IndexError(msg)
        return self._stack[-1][0]

    def get_min(self) -> int:
        if not self._stack:
            msg = "get_min from empty stack"
            raise IndexError(msg)
        return self._stack[-1][1]
tests/stacks_queues/test_min_stack.py
"""Tests for min stack."""

import pytest
from hypothesis import given
from hypothesis import strategies as st

from algo.stacks_queues.min_stack import MinStack


class TestMinStack:
    def test_basic_operations(self) -> None:
        ms = MinStack()
        ms.push(-2)
        ms.push(0)
        ms.push(-3)
        assert ms.get_min() == -3
        ms.pop()
        assert ms.top() == 0
        assert ms.get_min() == -2

    def test_single_element(self) -> None:
        ms = MinStack()
        ms.push(42)
        assert ms.top() == 42
        assert ms.get_min() == 42

    def test_ascending_pushes(self) -> None:
        ms = MinStack()
        ms.push(1)
        ms.push(2)
        ms.push(3)
        assert ms.get_min() == 1

    def test_descending_pushes(self) -> None:
        ms = MinStack()
        ms.push(3)
        ms.push(2)
        ms.push(1)
        assert ms.get_min() == 1
        ms.pop()
        assert ms.get_min() == 2

    def test_pop_empty_raises(self) -> None:
        ms = MinStack()
        with pytest.raises(IndexError):
            ms.pop()

    def test_top_empty_raises(self) -> None:
        ms = MinStack()
        with pytest.raises(IndexError):
            ms.top()

    def test_get_min_empty_raises(self) -> None:
        ms = MinStack()
        with pytest.raises(IndexError):
            ms.get_min()

    @given(
        values=st.lists(
            st.integers(min_value=-1000, max_value=1000),
            min_size=1,
            max_size=50,
        ),
    )
    def test_min_matches_builtin(self, values: list[int]) -> None:
        """get_min always agrees with min() of pushed values."""
        ms = MinStack()
        for v in values:
            ms.push(v)
        assert ms.get_min() == min(values)

Implement it yourself

Run: just challenge stacks_queues min_stack

Then implement the functions to make all tests pass. Use just study stacks_queues for watch mode.

Reveal Solution

min_stack

Min stack.

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Approach

Store (value, current_min) tuples on the stack. Each entry records the minimum at the time it was pushed, so getMin is always O(1) by reading the top tuple's min field.

When to use

Augmented data structure for O(1) aggregate queries — "get min/max while supporting push/pop". Pattern: store auxiliary data alongside each element. Useful for real-time monitoring dashboards.

Complexity

Time: O(1) for all operations Space: O(n) -- one tuple per element

MinStack

Stack supporting O(1) push, pop, top, and get_min.

ms = MinStack() ms.push(-2) ... ms.push(0) ... ms.push(-3) ms.get_min() -3 ms.pop() ms.get_min() -2

Source code in src/algo/stacks_queues/min_stack.py 
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class MinStack:
    """Stack supporting O(1) push, pop, top, and get_min.

    >>> ms = MinStack()
    >>> ms.push(-2)
    ... ms.push(0)
    ... ms.push(-3)
    >>> ms.get_min()
    -3
    >>> ms.pop()
    >>> ms.get_min()
    -2
    """

    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []

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

    def pop(self) -> None:
        if not self._stack:
            msg = "pop from empty stack"
            raise IndexError(msg)
        self._stack.pop()

    def top(self) -> int:
        if not self._stack:
            msg = "top from empty stack"
            raise IndexError(msg)
        return self._stack[-1][0]

    def get_min(self) -> int:
        if not self._stack:
            msg = "get_min from empty stack"
            raise IndexError(msg)
        return self._stack[-1][1]