DSA Min Stack

The problem

A stack is a last-in, first-out store. The last value pushed is the first value popped. Reading the top value removes nothing.

This problem is a design problem. The task is to build a stack type, named MinStack. It supports the usual stack operations and one extra query.

The four operations are push, pop, top, and getMin. The getMin query reports the smallest value currently in the stack. Every operation, the query included, must run in O(1) time.

That last rule is the whole difficulty. A normal stack reads its top in O(1). Its minimum can hide anywhere in the stack, and finding it must also cost one step.

script = [
    ("push -2", "min: -2"),
    ("push 0", "min: -2"),
    ("push -3", "min: -3"),
    ("pop", "returns -3, min: -2"),
    ("top", "0"),
    ("getMin", "-2"),
]
for step, expected in script:
    print(step, "->", expected)

Read the pop row closely. Popping removes -3, the current minimum. The minimum then falls back to -2, the smallest value that remains.

No operation may rescan the stack to produce those answers. The fallback minimum must already be stored somewhere when the pop happens.

Intuition

The first idea answers getMin by scanning. Keep the values in a plain list. On each query, walk the list and track the smallest value seen.

items = []
for value in [-2, 0, -3]:
    items.append(value)
smallest = items[0]
for value in items[1:]:
    if value < smallest:
        smallest = value
print("items:", items)
print("min by scanning:", smallest)

The scan is always right. It is also slow in exactly the place the spec forbids. A stack of a million values pays a million steps for one query.

The deeper problem is repetition. Nothing changes between two queries without a push or a pop. The scan recomputes an answer it could have kept.

Brute force

The brute force is a stack whose getMin scans. Push, pop, and top touch only the end of the list. They already run in O(1).

Only the query breaks the spec. Its cost grows with the number of stored values. The class below counts the comparisons so the bill is visible.

class NaiveMinStack:
    def __init__(self):
        self.items = []
        self.comparisons = 0

    def push(self, value):
        self.items.append(value)

    def pop(self):
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        smallest = self.items[0]
        for value in self.items[1:]:
            self.comparisons += 1
            if value < smallest:
                smallest = value
        return smallest

stack = NaiveMinStack()
stack.push(-2)
print("push -2, min:", stack.get_min())
stack.push(0)
print("push 0, min:", stack.get_min())
stack.push(-3)
print("push -3, min:", stack.get_min())
print("pop:", stack.pop(), "min:", stack.get_min())
print("top:", stack.top())
print("getMin:", stack.get_min())
print("comparisons spent on queries:", stack.comparisons)

Every expected value from the scripted case appears. The design still fails its spec. Five queries spent five comparisons on a stack of at most three items, and the count grows with the stack.

The fix must move the work. The minimum has to be maintained during push and pop. The query then becomes a read, not a search.

The optimal solution: a second stack of minima

Keep a second stack whose top is always the minimum of the items at that level, so every operation stays a single end-of-list step. That one sentence is the whole design.

The second stack is called mins. A running minimum is the smallest value from the bottom of the stack up to one position. Each push appends one running minimum beside the new item.

The stored minimum is the smaller of two values. It is the new value, or the previous running minimum, whichever is smaller. A larger new value therefore stores the old minimum again.

class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []

    def push(self, value):
        self.items.append(value)
        if self.mins:
            self.mins.append(min(value, self.mins[-1]))
        else:
            self.mins.append(value)

    def pop(self):
        self.mins.pop()
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        return self.mins[-1]


stack = MinStack()
stack.push(-2)
print("push -2, min:", stack.get_min())
stack.push(0)
print("push 0, min:", stack.get_min())
stack.push(-3)
print("push -3, min:", stack.get_min())
print("pop:", stack.pop(), "min:", stack.get_min())
print("top:", stack.top())
print("getMin:", stack.get_min())

The full scripted case passes. The pop restores -2 as the minimum without any search. The old running minimum was still stored one level down.

Both stacks always hold the same number of entries. That equal height is the invariant of the design. Every push adds one entry to each stack, and every pop removes one from each.

Walkthrough

Watch both stacks through four pushes and three pops. The values are 5, 3, 7, and 3. The printout shows both stacks after each step.

class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []

    def push(self, value):
        self.items.append(value)
        if self.mins:
            self.mins.append(min(value, self.mins[-1]))
        else:
            self.mins.append(value)

    def pop(self):
        self.mins.pop()
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        return self.mins[-1]


stack = MinStack()
for value in (5, 3, 7, 3):
    stack.push(value)
    print("push", value, "-> items", stack.items, "mins", stack.mins, "min", stack.get_min())
for _ in range(3):
    print("pop ->", stack.pop(), "| items", stack.items, "mins", stack.mins, "min now", stack.get_min())

The push of 7 stores 3 again in mins. The 7 is not the minimum, but its level still needs a mins entry. That repeated 3 is what keeps the two stacks the same height.

The first two pops leave the minimum at 3. A stored 3 remains each time. The third pop removes the last item holding 3, and the minimum returns to 5 from the stored entries alone.

Complexity

The time cost of every operation is O(1). Push, pop, top, and getMin each touch only the top entry of a list.

The space cost is O(n) for n stored values. The mins stack holds one extra entry per item, which is the price of the one-step minimum.

class NaiveMinStack:
    def __init__(self):
        self.items = []

    def push(self, value):
        self.items.append(value)

    def get_min_counted(self):
        comparisons = 0
        smallest = self.items[0]
        for value in self.items[1:]:
            comparisons += 1
            if value < smallest:
                smallest = value
        return smallest, comparisons

for size in [10, 20, 40]:
    stack = NaiveMinStack()
    for value in range(size, 0, -1):
        stack.push(value)
    smallest, comparisons = stack.get_min_counted()
    print("items:", size, "scan comparisons:", comparisons, "two-stack query reads: 1")

The scan comparisons grow in a straight line with the stack. Doubling the items roughly doubles them, from 9 to 19 to 39. The two-stack query reads one top entry at every size.

Counts make the spec concrete. O(1) here means the read count never moves as the stack grows. The scan count visibly moves.

Edge cases and pitfalls

Duplicate minima are the sharpest case. Two items can both hold the minimum value. Popping one of them must leave the minimum unchanged.

The repeated-entry rule is what saves that case. Each copy of the minimum stored its own mins entry. One pop removes one entry, and the other copy still reports the same minimum.

class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []

    def push(self, value):
        self.items.append(value)
        if self.mins:
            self.mins.append(min(value, self.mins[-1]))
        else:
            self.mins.append(value)

    def pop(self):
        self.mins.pop()
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        return self.mins[-1]


stack = MinStack()
stack.push(2)
stack.push(2)
print("two equal pushes, min:", stack.get_min())
print("pop:", stack.pop(), "min after pop:", stack.get_min())
print("top:", stack.top())

other = MinStack()
other.push(5)
print("single item, top:", other.top(), "min:", other.get_min())
other.push(9)
print("larger push, min:", other.get_min())
other.pop()
other.push(3)
print("new minimum pushed, min:", other.get_min())
other.pop()
print("minimum popped, min restored:", other.get_min())

Pushing only new minima is the classic pitfall. It keeps mins shorter than items. A pop then removes a minimum entry that belongs to a deeper item, and later queries read the wrong level.

Calling getMin on an empty stack has no answer. The spec's scripts only query a non-empty stack. Code that cannot promise that must check the height first and report the empty case itself.