LeetCode 155 · Stack

Min Stack, explained with a picture

Plates with a sticky note for the lightest.

MediumStack
▶ Watch it step by step

The problem

Design a stack that supports push, pop, top, and getMin (the smallest value currently in the stack), all in constant time.

Input:  push 5, push 3, push 7, min, pop, push 2, min, pop, pop, min
Output: min → 3, pop → 7, min → 2, pop → 2, pop → 3, min → 5

Picture it

Picture a stack of plates where each plate carries a sticky note saying “the lightest plate in the pile when I was added”. To answer “what’s the lightest?” you just read the note on the top plate. When you take the top plate off, the plate underneath still has the correct note for the smaller pile.

How to recognise it

  • You are asked to design a class, and every operation must be O(1), including a query (the minimum) that a plain stack cannot answer quickly.
  • Items only come and go at one end, so the set of items below any position never changes while that position is in the stack.
  • That means a summary of "everything at or below here" (the minimum, maximum or sum) can be computed once on push and stored, and it stays correct until that item is popped.
  • Up to 3 × 10^4 calls, so a scan of the whole stack on every get_min is too slow to rely on.

Start with brute force

Use a normal list for the stack and compute the minimum on demand with min.

class MinStackBrute:
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
    def pop(self):
        self.stack.pop()
    def top(self):
        return self.stack[-1]
    def get_min(self):
        return min(self.stack)

Push, pop and top are O(1), but get_min is O(n) because it scans the whole stack. With 1.5 × 10^4 pushes followed by 1.5 × 10^4 get_min calls, that is about 2.25 × 10^8 comparisons, and the task explicitly asks for constant time.

From brute force to the idea

  1. Find the waste. Every get_min rescans items that have not changed since the last call. The items below the top only change when they are popped themselves.
  2. Ask what the minimum depends on. The minimum of the whole stack is the minimum of the items from the bottom up to the top. When a new item lands on top, the new minimum is min(x, old minimum).
  3. Store it with the item. The shown code pushes a pair (value, min so far). The low it stores is x for the first item, and otherwise the smaller of x and the stored minimum of the item below.
  4. Popping needs no repair. Removing the top pair exposes the pair below it, whose stored minimum was correct for exactly the items that remain.
  5. Answer from the top. top reads self.stack[-1][0] and get_min reads self.stack[-1][1], both O(1).

This is the key idea: each entry remembers the minimum of itself and everything beneath it, so popping automatically restores the old minimum.

The key idea

Store (value, minimum so far) with every entry. The top entry always knows the current minimum: every operation is O(1).

Python solution

class MinStack:
    def __init__(self):
        self.stack = []                # (value, min so far)
    def push(self, x):
        low = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, low))
    def pop(self):
        self.stack.pop()
    def top(self):
        return self.stack[-1][0]
    def get_min(self):
        return self.stack[-1][1]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forcepush, pop, top O(1); get_min O(n): scans every itemO(n): the items
Pairs (shown code)O(1) for every operation: one append, pop or indexO(n): one extra number per item, about twice the brute force

Edge cases

  • The example sequence (push 5, 3, 7, then min, pop, push 2, min, pop, pop, min): gives 3, then 2, then 5, matching the expected output.
  • Duplicate minimums (push 2, push 2, pop): the remaining pair still stores 2, so get_min is 2. Each copy has its own stored minimum.
  • Extreme values (−2^31 and 2^31 − 1): returns −2147483648; Python integers have no overflow.
  • Calls on an empty stack: pop, top and get_min all raise IndexError. LeetCode promises these are only called when the stack is non-empty, so the shown code does not check.
  • Pop does not return a value in the shown code. Read top() first if you need the value.

Common mistakes

  • Keeping a single self.min variable. After the minimum is popped there is no way to know the next smallest without a scan.
  • Comparing the new value with the top's value instead of the top's stored minimum: after pushing 1, 5, 3 it reports 3 instead of 1.
  • In the two-stack version (below), pushing onto the min stack only when x < mins[-1]. Duplicates of the minimum are then lost after one pop.
Your turn: store fewer minimums

The shown code stores a minimum for every item, even when it repeats. Change the design to use a separate stack of minimums that only grows when the minimum changes or repeats. All operations must stay O(1). Describe your approach, then write it if you like.

Compare with our answer

Keep two lists. stack holds every value; mins holds a value only when it is less than or equal to the current minimum. On pop, if the removed value equals the top of mins, pop that too.

class MinStack2:
    def __init__(self):
        self.stack = []
        self.mins = []
    def push(self, x):
        self.stack.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)
    def pop(self):
        if self.stack.pop() == self.mins[-1]:
            self.mins.pop()
    def top(self):
        return self.stack[-1]
    def get_min(self):
        return self.mins[-1]

Pushing 5, 6, 7, 8 stores only one minimum. The worst case (decreasing values) is still O(n) extra space, but typical inputs use less.

A strong answer mentions: why <= is needed (push 2, push 2, pop must still have a 2 in mins), that every operation remains O(1), and that the worst-case space is unchanged.

Check what stuck

1. A text editor needs undo (remove the latest edit) and must show, in O(1), the largest file size reached by the edits still applied. Which design fits best?

2. After pop(), why does the shown code not need to recompute the minimum?

3. A learner writes low = min(x, self.stack[-1][0]). After which pushes does get_min() return a wrong value?

Score 60% or more and the lesson is marked complete.