155. Min Stack

Problem¶

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 is it 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

Python solution¶

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

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

Comment on 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]

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]