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, all without 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.
popMaxhas 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 list-plus-map shape an LRU cache uses: you need to unlink a node from the middle in O(1) and find the largest value quickly. 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.
Core 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.
A common follow-up asks for the same behaviour with only O(1) additional memory. The trick is to push an encoded value when a push sets a new minimum: store 2*x - min and update min to x, so the old minimum is recovered on pop as 2*min - stored. It is clever, and in Java or C++ it overflows 32-bit ints unless you use long. My answer in an interview is to present the parallel-stack version first and offer this second.
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:
Every element eventually receives every increment that applied to it, but only when it is actually popped. Each operation is strictly O(1), not just amortized, because a pop does a constant amount of work. Segment trees use the same lazy idea for range updates.
3. A 30-second worked example (min stack)
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 can store the state it superseded, which is the snapshot idea.
- Backtracking search. A running aggregate on the current path has to roll back exactly when you pop, so you store it per level.
- Lazy propagation in trees. Segment trees defer range updates in a similar way: record at the boundary, push down when a query forces it.
- LRU caches. A doubly linked list plus a map is the shape Max Stack needs, and the one an LRU cache uses.
5. Problems in this chapter
Max Stack
Like Min Stack, but popMax must remove the top-most maximum from wherever it sits. The point at which a plain stack stops being enough. The lesson covers a two-stack baseline, a heap with lazy deletion, and the linked list plus sorted map.
Pattern: lazy deletion with ids, or doubly linked list + sorted map. Target: top in O(1), the other operations O(log n).
Min Stack with Extra Space
Support push, pop, top and getMin, all O(1). Start with the parallel minimum stack (O(n) extra space), then the compact variant that needs <=, then the encoded-value trick that uses O(1) extra space.
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; pass it down on pop.
Pattern: lazy propagation. Target: strict O(1) per operation.
6. Common pitfalls
- One shared minimum variable. A single
minfield is wrong the moment the minimum is popped, so the snapshot must live per element. - Recomputing
minon pop. That is O(n) and defeats the exercise. - Overflow in the encoded-value trick.
2*x - mincan reach about -3 * 2^31 with 32-bit inputs; use a 64-bit type in Java or C++. - Applying the increment to all
kelements eagerly. Correct but O(k); the whole point is the boundary record. - Forgetting to pass the increment down 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
peekMaxbut notpopMaxefficiently, since the maximum may be buried. This is the trap the problem is built around. - Ignoring ties in Max Stack. With duplicate maxima,
popMaxmust remove the top-most occurrence, which is why the value-to-nodes map stores a list of nodes, newest last.
7. Key takeaways
- Store the answer as it was at push time. Popping then restores the previous answer for free.
- A stack is a sequence of snapshots, and that reframing solves the whole min/max family.
- Defer bulk work to the boundary and pass it down on pop: lazy propagation in miniature.
- Know when the structure has been outgrown. Removal from the middle needs a linked list and a map, not a stack.
- Offer the simple version first. The parallel-stack version is correct and clear; the O(1)-space encoding is a follow-up, not an opener.
- 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, then Min Stack with Extra Space, then Design a Stack With Increment Operation.
Max Stack
Core idea: This is where a stack stops being enough:
popMaxmust remove an element from the middle, which a stack cannot reach. Use a doubly linked list plus a map from value to the nodes holding it, and on ties remove the top-most occurrence.
Problem, rephrased
A triage console stacks incoming escalations the way an engineer works them: newest on top, so the freshest context is handled first, but a lead may also yank the highest-severity escalation out of the pile, wherever it sits. You're given the severities as integers x, pushed one at a time.
Implement the MaxStack class:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson