Stack Implementations

What is this?

A plain stack answers one question: what is on top? These problems ask it to answer a second question at the same speed — what is the minimum, what is the maximum, what happens if I add 5 to the bottom k elements — without ever scanning.

The unifying answer is that a stack is a sequence of snapshots. When you push, you can record what the answer was at that moment, and popping automatically restores the previous truth. You are not maintaining a value; you are storing history alongside the data.

💡 Fun fact: Max Stack is where a stack stops being sufficient. popMax has to remove an element that may sit anywhere in the middle, and a stack has no way to reach inside itself. The clean solution is a doubly linked list plus a sorted map from value to the nodes holding it — the same structure an LRU cache uses, for the same reason: you need O(1) removal from the middle and an ordering. Recognising when a problem has outgrown the structure it is named after is the real lesson.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: attach to each element whatever the answer was when it was pushed, or defer work until a pop forces you to do it. Both turn an O(n) query into O(1) by refusing to recompute what a snapshot already knows.

1. Answer-at-push-time

To make getMin() O(1), store pairs:

def push(self, x):
    current_min = x if not self.stack else min(x, self.stack[-1][1])
    self.stack.append((x, current_min))

def get_min(self):
    return self.stack[-1][1]        # the minimum of everything at or below the top

Each entry carries the minimum of the stack as it stood when that entry arrived. Popping discards that snapshot and re-exposes the previous one — which is still correct, because it was correct then and nothing below it has changed.

The "extra space" variant asks for the same behaviour with only O(1) additional memory, using the trick of pushing an encoded value when the minimum changes: store 2*x - min and update min to x, so the old minimum can be recovered on pop as 2*min - stored. It is clever, it overflows if you are careless, and the honest interview answer is to present the pair version first and offer this as the follow-up.

2. Lazy bulk updates

Design a Stack With Increment Operation asks you to add val to the bottom k elements. Doing it eagerly is O(k) per call. Instead keep a parallel inc array and record the increment only at index k-1 — the boundary. On pop, apply the pending increment to the returned value and push it down to the element below:

increment(k, val)   →   inc[k-1] += val

pop()               →   result = stack[top] + inc[top]
                        inc[top-1] += inc[top]     # cascade the debt downward
                        inc[top] = 0

Every element eventually receives every increment that applied to it, but only when it is actually needed. This is the same amortisation idea behind lazy propagation in segment trees.

3. A 30-second worked example (min stack)

push 5   stack = [(5,5)]                getMin → 5
push 3   stack = [(5,5), (3,3)]         getMin → 3
push 7   stack = [(5,5), (3,3), (7,3)]  getMin → 3   ← 7 carries the min it found
pop      stack = [(5,5), (3,3)]         getMin → 3
pop      stack = [(5,5)]                getMin → 5   ← restored for free

Nothing was recomputed. The 5 never had to be re-examined, because its snapshot had said "the minimum here is 5" since the moment it was pushed.

4. Where you'll actually meet this

• Undo systems. Each undo frame stores the state it superseded — exactly the snapshot idea.
• Database and editor transactions. Nested savepoints restore the prior state on rollback because each level recorded it on entry.
• Lazy propagation in trees. Segment trees defer range updates identically: record at the boundary, push down when a query forces it.
• Streaming statistics. Rolling min/max over a bounded history with O(1) queries, used in monitoring and trading systems.
• LRU and LFU caches. The doubly-linked-list-plus-map structure that Max Stack needs is the same one every cache eviction policy is built on.

5. Problems in this chapter

▶ Min Stack (with O(1) extra space)

Support push, pop, top and getMin, all O(1). Present the paired-snapshot version, then the encoded-value trick that removes the auxiliary storage.
Pattern: answer-at-push-time. Target: O(1) per operation.

▶ Design a Stack With Increment Operation

A capacity-bounded stack with a bulk increment on the bottom k elements. Record the increment at the boundary; cascade it downward on pop.
Pattern: lazy propagation. Target: O(1) per operation.

▶ Max Stack

Like Min Stack, but popMax must remove the maximum from wherever it sits. The point at which a plain stack stops being enough.
Pattern: doubly linked list + sorted map (or two heaps with lazy deletion). Target: O(log n) for popMax, O(1) for the rest.

6. Common pitfalls 🚫

• One shared minimum variable. A single min field is wrong the moment the minimum is popped — the snapshot must live per element.
• Recomputing min on pop. That is O(n) and defeats the exercise.
• Overflow in the encoded-value trick. 2*x - min can exceed the integer range; mention it, and use a wider type where the language requires one.
• Applying the increment to all k elements eagerly. Correct but O(k); the whole point is the boundary record.
• Forgetting to cascade on pop. If the pending increment is not pushed down, every element below silently loses it.
• Reaching for a second stack in Max Stack. It handles getMax but not popMax, since the maximum may be buried — this is the trap the problem is built around.
• Ignoring ties in Max Stack. With duplicate maxima, popMax must remove the top-most occurrence, which is why the value-to-nodes map stores a list.

7. Key takeaways

1. Store the answer as it was at push time. Popping then restores the previous answer for free.
2. A stack is a sequence of snapshots, and that reframing solves the whole min/max family.
3. Defer bulk work to the boundary and cascade it on pop — lazy propagation, in miniature.
4. Know when the structure has been outgrown. Removal from the middle needs a linked list and a map, not a stack.
5. Offer the simple version first. The paired-snapshot stack is correct and clear; the O(1)-space encoding is a follow-up, not an opener.
6. Why interviewers like it: these are design questions disguised as data-structure questions. The signal is whether you pick an invariant that makes every operation cheap, rather than patching each operation separately.

Order: Max Stack → Min Stack with Extra Space → Design a Stack With Increment Operation.