DSA sheet · Stack · Stack-based design pattern

Min Stack

Build a stack that can also tell you its smallest item in O(1), at any moment, even after pops. Push, pop and top are easy; getMin in constant time is the whole problem. The teacher solves it twice: first with a second "min stack" (2n space), then with a clever encode/decode trick that keeps only one stack and one variable (n space). At the end she shows that Max Stack is the same idea with the comparisons flipped. She calls this problem very interesting because of the space optimisation.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (operation-sequence table) → ⑨ complexity & remember

• Part 0 · Stacks and design-problem costs from scratch
• Part A · Two stacks: stack + min stack (O(2n) space)
• Part B · One stack + one variable: encode the previous minimum (O(n) space)
• Part C · Max Stack: the same trick, flipped
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates: you add and remove only at the top. Last in, first out (LIFO). Operations: push(x) puts x on top, pop() removes the top, top() (peek) reads the top without removing it.

st = []
st.append(5)      # push 5   -> [5]
st.append(8)      # push 8   -> [5, 8]   (right end = top)
st[-1]            # peek     -> 8
st.pop()          # pop      -> 8, st = [5]
if st:            # ALWAYS check "not empty" before pop() or [-1]
    print(st[-1])

We draw stacks left = bottom, right = top, like the list.

A stack never forgets what was below

This is the property that makes Min Stack possible. When you push x, everything already inside stays there, untouched, until x is popped. So "the smallest item from the bottom up to x" stays the same for as long as x is in the stack. We can work it out once at push time and keep it next to x.

Design problems: what does the cost of an operation mean?

In design problems we price each method separately. Worst-case O(1) means every single call is fast. Amortised O(1) means some calls can be slow but the average over a long run is constant (like the queue made of two stacks, Problem 18). In this problem the teacher reaches true worst-case O(1) for every method, which is even stronger than amortised.

Why it matters, counted: with 10⁵ items in the stack and 10⁵ getMin calls, scanning the stack each time costs up to 10⁵ × 10⁵ = 10¹⁰ steps (too slow; about 10⁸ is the limit). Reading a stored answer costs 10⁵ steps in total.

Part A · Two stacks: stack + min stack

LeetCode 155

1The question in simple words

Design MinStack with:

• push(val): put val on top.
• pop(): remove the top item.
• top(): return the top item.
• getMin(): return the smallest item currently in the stack.

Each must run in O(1) time. pop, top and getMin are always called on a non-empty stack.

The teacher's example: push 5, push 8, getMin → 5, push 4, getMin → 4, pop, getMin → 5, push 9, getMin → 5.

2What the constraints tell us

• Up to about 10⁵ operations (the teacher's number; LeetCode says 3 × 10⁴) → a scan for every getMin could be 10¹⁰ steps. We really need O(1).
• Values go up to about 2³¹ (the edge of a 32-bit int), and can be negative. The teacher warns: if we ever add or multiply such values, in Java/C++ we must switch to long. This matters a lot in Part B. In Python integers never overflow, so we're safe, but we'll still test with huge and negative values.

3Intuition: store "the minimum so far" next to every item

Without the O(1) rule, getMin would be a simple loop over the stack. With it, we must keep track of the minimum at every step instead of searching for it later.

Keep a second stack, the min stack, that grows and shrinks together with the main stack. On each push, the min stack gets the smallest value among everything pushed so far that is still inside. Then getMin is just the top of the min stack.

The teacher also mentions you could keep the pair (value, min so far) in one stack. That's the same thing, still 2n space.

4Building the logic from the example

push 5

Main stack [5]. The min stack is empty, so this is the first item: the minimum is 5 itself. Min stack [5].

push 8

Main [5, 8]. What's the minimum of 5 and 8? Compare the new value with the top of the min stack: min(8, 5) = 5. Min stack [5, 5].

getMin → 5

Just read the top of the min stack. We don't pop anything.

push 4 → min(4, 5) = 4

Main [5, 8, 4], min [5, 5, 4]. getMin → 4.

pop → pop BOTH stacks

Main [5, 8]. If we left the min stack alone, its top would still be 4, and getMin would answer 4, a number that isn't even in the stack anymore. So every pop must remove from both stacks. Min [5, 5] → getMin 5 ✓ (correct: 5 and 8 are left).

push 9 → min(9, 5) = 5

5 was pushed first and is still the smallest. However many bigger items come later, getMin keeps saying 5 until 5 itself is popped.

5Approach steps

1. push(x): push x on the main stack. If the min stack is empty, push x on it; else push min(x, minStack top).
2. pop(): pop from both stacks (only if non-empty).
3. top(): top of the main stack.
4. getMin(): top of the min stack.

6Code (Python)

class MinStack:
    def __init__(self):
        self.st = []        # the real values
        self.mn = []        # mn[i] = smallest of st[0..i]

    def push(self, val):
        self.st.append(val)
        if not self.mn:                         # first item
            self.mn.append(val)
        else:
            self.mn.append(min(val, self.mn[-1]))

    def pop(self):
        if self.st:                             # both stacks always have the same size
            self.st.pop()
            self.mn.pop()

    def top(self):
        return self.st[-1] if self.st else -1

    def getMin(self):
        return self.mn[-1] if self.mn else -1

The teacher returns −1 from top/getMin when the stack is empty, as a safety net. LeetCode never calls them on an empty stack.

7Code line by line

8Dry run: operation-sequence table

Each row of mn is the answer to getMin when the stack has exactly that many items.

9Complexity & remember

• Time: O(1) for every method, worst case.
• Space: O(2n): n for the values and n for the minimums. Still O(n) in big-O, but the teacher asks: can we drop the second n?

Part B · One stack + one variable: encode the previous minimum

1The question again, with the new goal

Same four methods, all O(1), but now use only one stack of n values plus a few variables: O(n) space instead of O(2n).

2What the constraints tell us now

• We'll store a computed value 2·x − min. With x and min near ±2³¹, this can be about ±2³², which overflows a 32-bit int. That's why the teacher stores long in Java. Python ints are unbounded, so no change is needed in our code.
• Up to 10⁵ operations: we can't keep a separate variable for every old minimum, because that's just the min stack again.

3Intuition: why one variable fails, and how to hide the old minimum inside the stack

First try: keep one variable mini. push 5 → mini 5. push 8 → still 5. push 4 → mini 4. getMin → 4 ✓. Now pop 4. The minimum should go back to 5, but the variable only remembers 4, and 5 is gone. One variable can't remember the previous minimum. Two, three variables? There can be 10⁵ changes, so no.

The teacher notices when the old minimum gets lost: only at a push that makes a new minimum (like 4). Pushing 8 or 9 doesn't change the minimum, so popping them later doesn't need any fixing.

So the idea: at the moment a new minimum arrives, don't store it as it is. Store a special "encoded" number that both (a) marks this spot as "the minimum changed here" and (b) hides the previous minimum inside it. When we later pop that spot, we notice the mark and decode the old minimum back.

4Building the encode/decode rule step by step

Step 1: find a mark we can recognise

Look at every normal (not encoded) value in the stack: each one is ≥ the current minimum (5 ≥ 5, 8 ≥ 5). That's always true, since the minimum is the smallest of them. So if we ever see a stack value that is less than the current minimum, it can't be a normal value. That breaks the rule on purpose and works as our mark.

Step 2: derive a formula that is smaller than the new minimum

A new minimum x arrives, with the previous minimum prev. We know x < prev, so

x − prev < 0 → add x to both sides → 2x − prev < x

So store e = 2x − prev. After the push, the minimum becomes x, and e < x = mini. The mark works ✓. Example: prev = 5, x = 4 → e = 2·4 − 5 = 3, and 3 < 4 ✓. (Any number below 4 would mark the spot; this formula also hides 5 inside.)

Step 3: decode when popping

We pop e = 3 and see 3 < mini (4). From e = 2x − prev and x = mini, solve for prev:

prev = 2·mini − e = 2·4 − 3 = 5 ✓

So pop sets mini = 2·mini − top, bringing back the old minimum.

5Approach steps

1. push(x): if the stack is empty → push x, mini = x. Else if x < mini → push 2x − mini, then mini = x. Else → push x.
2. pop(): take the top. If top < mini → it was encoded → mini = 2·mini − top.
3. top(): if top < mini → return mini, else return top.
4. getMin(): return mini.

6Code (Python)

class MinStack:
    def __init__(self):
        self.st = []
        self.mini = None

    def push(self, val):
        if not self.st:                          # first item
            self.st.append(val)
            self.mini = val
        elif val < self.mini:                   # new minimum: hide the old one
            self.st.append(2 * val - self.mini)  # encoded, always < val
            self.mini = val
        else:
            self.st.append(val)                  # minimum unchanged

    def pop(self):
        if not self.st:
            return
        top = self.st.pop()
        if top < self.mini:                     # encoded spot: minimum changed here
            self.mini = 2 * self.mini - top      # decode the previous minimum

    def top(self):
        if not self.st:
            return -1
        top = self.st[-1]
        return self.mini if top < self.mini else top

    def getMin(self):
        return self.mini if self.st else -1

7Code line by line

8Dry run: operation-sequence table

The teacher's sequence first, then two more new minimums in a row to see that the chain of old minimums decodes back correctly. Bold = encoded value.

Each encoded value holds the minimum from just before it: 0 hides 2, −1 hides 5. Popping peels them off in order.

9Complexity & remember

• Time: O(1) for every method, the same as Part A.
• Space: O(n), one stack plus one variable, instead of 2n. That's the only gain.

The teacher's honest advice: encode/decode tricks are rare in DSA, and it's normal not to invent this on your first try. But after seeing it once, you should be able to reproduce it, including why the formula is 2x − prev.

Part C · Max Stack: the same trick, flipped

The sheet's next item is a stack with getMax() instead of getMin(). The teacher says everything is the same and asks you to try it on your own first. (Note: LeetCode 716 "Max Stack" also has a popMax method, which needs a different design. Here we mean the simple version: push, pop, top, getMax.)

1What changes

• Two-stack version: the second stack stores max(x, top) instead of min.
• O(n) version: the mark flips. Normal values are all ≤ maxi, so an encoded value must be greater than maxi. When a new maximum x > prev arrives: x − prev > 0 → 2x − prev > x. Store 2x − prev. On pop, if top > maxi → maxi = 2·maxi − top.

2Code (Python)

class MaxStackTwo:
    def __init__(self):
        self.st, self.mx = [], []

    def push(self, val):
        self.st.append(val)
        self.mx.append(val if not self.mx else max(val, self.mx[-1]))

    def pop(self):
        if self.st:
            self.st.pop()
            self.mx.pop()

    def top(self):
        return self.st[-1] if self.st else -1

    def getMax(self):
        return self.mx[-1] if self.mx else -1

class MaxStack:
    def __init__(self):
        self.st = []
        self.maxi = None

    def push(self, val):
        if not self.st:
            self.st.append(val)
            self.maxi = val
        elif val > self.maxi:                   # new maximum
            self.st.append(2 * val - self.maxi)  # encoded, always > val
            self.maxi = val
        else:
            self.st.append(val)

    def pop(self):
        if not self.st:
            return
        top = self.st.pop()
        if top > self.maxi:                     # encoded spot
            self.maxi = 2 * self.maxi - top

    def top(self):
        if not self.st:
            return -1
        top = self.st[-1]
        return self.maxi if top > self.maxi else top

    def getMax(self):
        return self.maxi if self.st else -1

3Dry run

4Complexity & remember

O(1) per method; O(2n) or O(n) space, exactly as for Min Stack.

Part D · Revision page

s = MinStack()
s.push(5); s.push(8)
print(s.getMin())   # 5
s.push(4)
print(s.getMin())   # 4
print(s.top())      # 4
s.pop()
print(s.getMin())   # 5
s.push(9)
print(s.top(), s.getMin())   # 9 5
s.push(-2**31); print(s.getMin())   # -2147483648

Based on this video: Min Stack