LeetCode 155: Min Stack

Problem Restatement

We need to design a stack that supports normal stack operations and also returns the minimum element currently inside the stack.

The class must support these methods:

Each operation must run in O(1) time. LeetCode states that pop, top, and getMin will only be called on non-empty stacks, and at most 3 * 10^4 calls will be made.

Input and Output

Example class shape:

class MinStack:

    def __init__(self):
        ...

    def push(self, val: int) -> None:
        ...

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

    def top(self) -> int:
        ...

    def getMin(self) -> int:
        ...

Examples

Use this operation sequence:

minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin()
minStack.pop()
minStack.top()
minStack.getMin()

After pushing -2, 0, and -3, the stack is:

[-2, 0, -3]

The minimum is:

-3

After pop(), the stack becomes:

[-2, 0]

The top is:

0

The minimum is now:

-2

First Thought: Normal Stack Plus Scan

A normal stack can support push, pop, and top in O(1) time.

For getMin(), the simplest idea is to scan the whole stack.

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def getMin(self) -> int:
        return min(self.stack)

This is correct, but getMin() takes O(n) time.

The problem requires constant time for every operation, so scanning is too slow.

Key Insight

When we push a value, we can also remember the minimum value at that exact stack depth.

For example, after these pushes:

push(-2)
push(0)
push(-3)

The normal stack is:

[-2, 0, -3]

The current minimum after each push is:

[-2, -2, -3]

So we maintain two stacks:

The top of min_stack always gives the current minimum.

That makes getMin() an O(1) operation.

Algorithm

Initialize two empty lists:

self.stack = []
self.min_stack = []

For push(val):

1. Push val onto stack.
2. Compute the new minimum.
3. Push that minimum onto min_stack.

If min_stack is empty, the new minimum is val.

Otherwise, the new minimum is:

min(val, self.min_stack[-1])

For pop():

1. Pop from stack.
2. Pop from min_stack.

The two stacks must stay the same length.

For top():

return self.stack[-1]

For getMin():

return self.min_stack[-1]

Walkthrough

Start with empty stacks:

Notice that min_stack changes in sync with stack.

When the top value is removed, the saved minimum for that old stack depth is also removed.

Correctness

The invariant is:

After every operation, min_stack[i] stores the minimum value among stack[0] through stack[i].

When we push a new value val, the minimum at the new top can only be either:

1. The new value val
2. The previous minimum, stored at min_stack[-1]

So pushing min(val, self.min_stack[-1]) preserves the invariant.

When we pop, both stacks remove their top values. The stack returns to the previous depth, and min_stack[-1] again stores the minimum for that previous depth.

Because the invariant is always true, getMin() can return min_stack[-1], which is exactly the minimum value in the current stack.

top() returns stack[-1], which is the most recently pushed value that has not been popped.

Therefore, every method returns the correct result.

Complexity

Let n be the number of elements currently in the stack.

Implementation

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        if self.min_stack:
            current_min = min(val, self.min_stack[-1])
        else:
            current_min = val

        self.min_stack.append(current_min)

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

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

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

Code Explanation

The constructor creates two stacks:

self.stack = []
self.min_stack = []

The main stack stores real values.

The second stack stores the running minimum at every depth.

When pushing a value:

self.stack.append(val)

we first add it to the normal stack.

Then we compute the minimum after this push:

if self.min_stack:
    current_min = min(val, self.min_stack[-1])
else:
    current_min = val

If there was already a minimum, compare it with the new value.

If the stack was empty, the new value itself is the minimum.

Then store that minimum:

self.min_stack.append(current_min)

When popping:

self.stack.pop()
self.min_stack.pop()

we remove from both stacks so their depths remain aligned.

The top value is:

return self.stack[-1]

The current minimum is:

return self.min_stack[-1]

Testing

def run_tests():
    s = MinStack()

    s.push(-2)
    s.push(0)
    s.push(-3)
    assert s.getMin() == -3

    s.pop()
    assert s.top() == 0
    assert s.getMin() == -2

    s.push(-5)
    assert s.getMin() == -5

    s.pop()
    assert s.getMin() == -2

    s.pop()
    assert s.top() == -2
    assert s.getMin() == -2

    print("all tests passed")

run_tests()