155. Min Stack

Reformulated question¶

Design a stack with these operations in \(O(1)\) time:

push(x)
pop()
top()
getMin() returns the smallest value currently in the stack

Example:

ops:    push(2), push(1), push(3), getMin(), pop(), getMin(), top()
stack:  [2] -> [2,1] -> [2,1,3] -> min=1 -> [2,1] -> min=1 -> top=1
out:    -, -, -, 1, -, 1, 1

Key trick¶

Keep the current minimum alongside each pushed value.

Store (value, min_so_far) for every stack entry
Then:
push computes the new min from the previous one
pop removes both value and its min
top and getMin read the last tuple

Trap¶

Tracking only one global minimum.
It breaks when the minimum is popped.
Forgetting duplicate minimums.
If stack is [2, 1, 1], popping one 1 should still leave min as 1.
Using an \(O(n)\) scan for getMin().
This violates the requirement.

Why this question is interesting¶

It tests whether you can augment a basic data structure to preserve extra information in constant time.

Simple API
Easy to code
Reveals whether you think about invariants instead of recomputing

Solve the problem with idiomatic python¶

class MinStack:
    def __init__(self):
        # Each item is (value, min_so_far_at_this_point).
        self.stack = []

    def push(self, val: int) -> None:
        curr_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, curr_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]

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("ops", "args", "expected"),
    [
        (
            ["push", "push", "push", "getMin", "pop", "top", "getMin"],
            [[-2], [0], [-3], [], [], [], []],
            [None, None, None, -3, None, 0, -2],
        ),
        (
            ["push", "getMin", "top"],
            [[5], [], []],
            [None, 5, 5],
        ),
        (
            ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"],
            [[2], [1], [1], [], [], [], [], []],
            [None, None, None, 1, None, 1, None, 2],
        ),
        (
            ["push", "push", "push", "pop", "top", "getMin"],
            [[3], [4], [2], [], [], []],
            [None, None, None, None, 4, 3],
        ),
    ],
)
def test_min_stack(ops, args, expected):
    s = MinStack()
    out = []

    for op, arg in zip(ops, args):
        if op == "push":
            out.append(s.push(*arg))
        elif op == "pop":
            out.append(s.pop())
        elif op == "top":
            out.append(s.top())
        elif op == "getMin":
            out.append(s.getMin())

    assert out == expected

Comment my solution¶

Your solution is correct and keeps all operations in \(O(1)\).

Good:

minimums[i] matches the min after the first i + 1 pushes
pop() updates both structures consistently
Duplicate minimums are handled correctly

Could be simpler:

Use one list of tuples instead of:
a linked-list-like dict stack
a separate minimums list
In push, prefer self.minimums.append(val) over self.minimums = [val]
same result, more consistent
A dict-based linked list is unusual in Python here and adds noise

class MinStack:

    def __init__(self):
        self.stack = None
        self.minimums = []

    def push(self, val: int) -> None:
        if self.minimums:
            last_min = self.minimums[-1]
            self.minimums.append(min(val, last_min))
        else:
            self.minimums = [val]
        head = {"val": val, "next": self.stack}
        self.stack = head

    def pop(self) -> None:
        self.minimums.pop()
        self.stack = self.stack["next"]

    def top(self) -> int:
        return self.stack["val"]

    def getMin(self) -> int:
        return self.minimums[-1]

## Test

import pytest

def test_MinStack():

    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)
    minStack.push(-3)

    assert minStack.getMin() == -3

    minStack.pop()

    assert minStack.top() == 0
    assert minStack.getMin() == -2

A cleaner version of your idea:

class MinStack:
    def __init__(self):
        self.stack = []
        self.minimums = []

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

    def pop(self) -> None:
        self.stack.pop()
        self.minimums.pop()

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

    def getMin(self) -> int:
        return self.minimums[-1]

Code¶

import pytest


class MinStack:
    def __init__(self):
        # Each item is (value, min_so_far_at_this_point).
        self.stack = []

    def push(self, val: int) -> None:
        curr_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, curr_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]


@pytest.mark.parametrize(
    ("ops", "args", "expected"),
    [
        (
            ["push", "push", "push", "getMin", "pop", "top", "getMin"],
            [[-2], [0], [-3], [], [], [], []],
            [None, None, None, -3, None, 0, -2],
        ),
        (
            ["push", "getMin", "top"],
            [[5], [], []],
            [None, 5, 5],
        ),
        (
            ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"],
            [[2], [1], [1], [], [], [], [], []],
            [None, None, None, 1, None, 1, None, 2],
        ),
        (
            ["push", "push", "push", "pop", "top", "getMin"],
            [[3], [4], [2], [], [], []],
            [None, None, None, None, 4, 3],
        ),
    ],
)
def test_min_stack(ops, args, expected):
    s = MinStack()
    out = []

    for op, arg in zip(ops, args):
        if op == "push":
            out.append(s.push(*arg))
        elif op == "pop":
            out.append(s.pop())
        elif op == "top":
            out.append(s.top())
        elif op == "getMin":
            out.append(s.getMin())

    assert out == expected


s = MinStack()
s.push(-2)
s.push(0)
s.push(-3)
example_min_1 = s.getMin()   # -3
s.pop()
example_top = s.top()        # 0
example_min_2 = s.getMin()   # -2