Min Stack (LeetCode 155)

The problem

Design a stack class with four operations, each in O(1) time:

• push(x) puts x on top.
• pop() removes the top element.
• top() returns the top element.
• getMin() returns the smallest element currently in the stack.

pop, top and getMin are only called on a non-empty stack.

Operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output:                                    -3             0      -2

After pushing -2, 0, -3 the minimum is -3. Popping removes -3, so the top is 0 and the minimum goes back to -2.

How to think about it

Start with brute force. Use a normal list and have getMin scan it: min(self.st). Push, pop and top are O(1), but getMin is O(n), which breaks the requirement.

Why one min variable fails. You could track a single current_min and update it on every push. That works until you pop the minimum. Now you need the previous minimum, and you threw it away. Recomputing it is O(n) again.

The key insight: the minimum depends only on what is below. When a value sits at some depth in a stack, everything under it is fixed until it is popped. So the minimum “as of this element” never changes while the element is there. Store that minimum alongside the value: push the pair (x, min(x, min_of_previous_top)). Popping simply removes the pair and the previous minimum is right there in the new top.

Which pattern is this? Augmented stack: the stack carries a running aggregate. The tell is “support some query in O(1) on a structure that only changes at one end”. The same trick gives a running max, or a queue with min built from two such stacks.

Approach

1. Keep one list st of (value, min_so_far) pairs.
2. push(x): the new minimum is x if the stack is empty, else min(x, st[-1][1]). Append (x, m).
3. pop(): remove the last pair.
4. top(): return st[-1][0].
5. getMin(): return st[-1][1].

Solution

class MinStack:
    def __init__(self):
        self.st = []                               # pairs of (value, min at this depth)
    def push(self, x):
        m = x if not self.st else min(x, self.st[-1][1])
        self.st.append((x, m))
    def pop(self):
        self.st.pop()                              # the min below is already stored
    def top(self):
        return self.st[-1][0]
    def getMin(self):
        return self.st[-1][1]
# ms=MinStack(); ms.push(-2); ms.push(0); ms.push(-3)
# ms.getMin() -> -3 ; ms.pop(); ms.top() -> 0 ; ms.getMin() -> -2

The same idea appears in the design-a-data-structure lesson written as one-liners (self.st.append((x, min(x, self.st[-1][1] if self.st else x)))). It is the same algorithm, so pick whichever reads better to you.

Dry run

After the pop, the pair (0, -2) already remembers that the minimum below it is -2, so no scan is needed.

Complexity

• Time: O(1) per operation. Every method does a constant amount of work on the end of a list.
• Space: O(n). Each element stores one extra number, its running minimum.

Edge cases and pitfalls

• Duplicate minimums such as push(1), push(1), pop() work automatically because every pair stores its own minimum. The two-stack variant (a separate min stack that only pushes on new minimums) must push on <=, not <, or popping a duplicate breaks it.
• First push has nothing below, so the minimum is x itself; guard the self.st[-1] lookup.
• Negative numbers and very large values are fine in Python. In languages with fixed-width integers, the “store x - min difference” space trick can overflow, so prefer pairs.
• Calling top or getMin on an empty stack would raise. The problem promises it won’t happen, but say so in an interview.

Related problems

• LRU Cache (LeetCode 146): another “design a structure with O(1) operations” problem.
• Online Stock Span (LeetCode 901): a stack of pairs where the second field also carries accumulated information.
• Design Circular Queue (LeetCode 622): designing a fixed-size queue with O(1) operations.