The Five Signals: How to Spot a Stack Problem

First, the One Idea a Stack Is Built Around

Before we can recognise when to use a stack, we must be crystal clear on what a stack actually gives us. Forget the code for a moment. A stack is just a pile — like a pile of plates. You can only do two things: put a plate on top (push), or take the top plate off (pop). You cannot pull a plate from the middle. The last plate you put on is the first one you take off.

That property has a name: LIFO — Last In, First Out. And that single property is the entire reason stacks exist. So the real question we are learning to answer is not "should I use a stack?" but something more precise:

Does my problem care about the most recent unfinished thing?

Almost every stack problem, underneath its story, is really asking: "of everything I have seen so far and not yet dealt with, what was the most recent one?" If a problem keeps needing the latest unresolved item, a stack is almost certainly your tool — because a stack hands you exactly that, instantly, for free.

Hold that sentence in your mind. Everything below is just different disguises of it.

Let Us Make That Concrete (From Everyday Life to Real Problems)

That sentence — "the most recent unfinished thing" — sounds abstract. So before any code, let us watch it come alive in four examples, starting from something you already do every day and climbing up to a real interview problem. In each one, keep your eye on the pile of "started but not yet finished" items, and notice that the thing we act on is always the newest one on top.

Example A — Interruptions at work (pure everyday life)

You are writing an email (call it task A). Mid-sentence, your manager phones you (task B). While on the call, a calendar reminder pops up and needs a click (task C). Which do you finish first? You click the popup (C), then return to the call (B), then finally back to the email (A). Watch the pile of unfinished tasks:

start email      → unfinished: [A]           top = A
manager calls    → unfinished: [A, B]        top = B
popup appears    → unfinished: [A, B, C]     top = C
handle popup     → unfinished: [A, B]        top = B ← back to recent
finish the call  → unfinished: [A]           top = A
finish the email → unfinished: []            all done

You always work on the top — the most recent unresolved thing. You did not plan this; it is just how interruptions naturally nest. This is exactly how your computer runs functions (the "call stack"): the function called most recently is the one that must finish and return first.

Example B — Matching brackets (the simplest algorithm version)

Now the same idea in code form. Read ( [ { } ] ) from left to right. Every opening bracket is "seen but not yet dealt with" until its partner arrives:

read (  → waiting: [ (      ]   top = (
read [  → waiting: [ ( [    ]   top = [
read {  → waiting: [ ( [ {  ]   top = {

read }  → a closer! the most recent unmatched opener is { → it matches, pop it
          waiting: [ ( [    ]   top = [
          
read ]  → most recent is [ → matches, pop
          waiting: [ (      ]   top = (
read )  → most recent is ( → matches, pop
          waiting: []  →  balanced ✓

Every closing bracket only ever checks the top — the most recent unmatched opener. We never dig into the middle. That is the whole reason a stack fits like a glove here.

Example C — The browser back button (real-world software)

You visit Home, then Blog, then Article. Each page is "somewhere I can still return to" — unfinished business. Pressing back always returns you to the most recently visited page:

visit Home     → history: [Home]
visit Blog     → history: [Home, Blog]
visit Article  → history: [Home, Blog, Article]   top = Article
press back     → leave Article, land on Blog       ← most recent first
press back     → land on Home

Undo in your text editor, the "back" gesture on your phone, retracing your steps out of a maze — all the same shape. The most recent action is the first one you reverse.

Example D — Stock span (a real interview problem)

Finally, let us climb to a genuine problem — the one from our stock span post. We walk through daily prices, and each day is "unresolved" until a higher price comes along and ends its span. Prices [100, 80, 60, 70]:

day 0 (100) →                         unresolved: [100]            top = 100

day 1 (80)  → 80 < 100, 80 waits too  unresolved: [100, 80]     top = 80

day 2 (60)  → 60 < 80, waits          unresolved: [100, 80, 60] top = 60

day 3 (70)  → 70 is bigger than the top (60)! that day is now resolved → pop it.

              70 < 80, so we stop. unresolved: [100, 80, 70]

Look at day 3: it settles the waiting days starting from the most recent one (60) and stops the moment it meets a bigger price. Same instinct as brackets, same instinct as your interrupted email — deal with the most recent unresolved thing first.

See the ladder we just climbed? Interrupted tasks → brackets → back button → stock span. Wildly different stories, one identical shape. That shape is the stack, and learning to see it underneath the story is the entire skill.

The Benefit: Why Not Just Use an Array and Loop?

A fair beginner question: "I can already add and remove from the end of an array. Why give it a fancy name?" Two reasons, and they are the whole payoff:

1. Instant access to the most recent item. Peeking or removing the top is O(1) — one step, no searching. If instead you had to scan backwards through your data every time to find "the most recent thing that matters," you would pay O(n) each time, and your whole algorithm balloons to O(n²).
2. The history cleans up after itself. This is the subtle, beautiful part. When you pop an item, the item underneath is now on top — and in a huge class of problems, that underneath item is exactly the next thing you need, with no recomputation. The stack remembers your unfinished business in perfect order and reveals it back to you one layer at a time as you finish each piece.

So the benefit is almost always the same headline: a stack turns an O(n²) "look backwards and search" solution into an O(n) "each item is handled once" solution. When you can say that sentence about a problem, you have found your answer.

The Five Signals: How to Spot a Stack Problem

Here are the five recurring shapes. In an interview, you are pattern-matching against these. I will give each one a trigger, the intuition, and the problems from our world that fit it.

Signal 1 — "Matching pairs" or "nested structure"

Trigger words: balanced, valid, matching, opening/closing, nested, well-formed.

If a problem involves things that open and must later close in the reverse order they opened — brackets, tags, parentheses in a formula — that is a stack, guaranteed. Why? Because the rule "the thing that opened most recently must close first" is literally the LIFO property spoken out loud.

Think of nesting like Russian dolls: to close the outer doll you must first close the inner one you opened last. When you see an opener, you push it ("I am now waiting for this to close"); when you see a closer, you check the top ("does it match the most recent opener?").

Why a stack, concretely. Imagine validating HTML tags: <div> <p> </p> </div>. Read them left to right and keep a pile of "tags I have opened but not yet closed":

<div>  → push div     open: [div]
<p>    → push p        open: [div, p]     ← p is the most recent unclosed tag
</p>   → closes p? top is p → yes, pop     open: [div]
</div> → closes div? top is div → yes, pop open: []   valid ✓

Now ask: why does a stack fit so perfectly here? Because a closing tag can only ever validly close the most recently opened tag. If the input were <div> <p> </div> </p>, then when </div> arrives the top is p, not div — mismatch, invalid! The stack catches it instantly, because the only tag a closer is allowed to match is the one sitting on top. That is the "most recent unresolved thing" idea in its purest form: an opener is unresolved until its closer arrives, and closers always resolve the newest opener first — which is precisely LIFO.

Our problems: Valid Parentheses. And later, this same instinct powers Basic Calculator and Decode String, where ( and [ open a sub-problem that must be finished before the outer one continues.

Signal 2 — "Next / previous greater or smaller" (the monotonic stack)

Trigger words: next greater, next smaller, nearest larger, how many days until, how far until, span, first element that is bigger.

If a problem asks you, for every element, to find the nearest element in some direction that is bigger or smaller — that is the monotonic stack, the most valuable pattern of them all. The intuition (which we built in the daily-temperatures post) is to flip the question: instead of each element searching forward for its answer, you let each new element look backward and resolve all the waiting elements it "beats." The stack holds the elements still waiting for their answer, and it naturally stays sorted (monotonic) because a bigger arrival evicts all the smaller waiters.

Why a stack, concretely. Take "next greater element" on [2, 1, 5]. Each number is unresolved until a bigger number appears to its right:

2 → nobody bigger yet, it waits    waiting: [2]
1 → 1 < 2, so 1 waits too          waiting: [2, 1]   ← 1 is the most recent waiter
5 → 5 > top(1)? yes → 1's answer is 5, pop it
    5 > top(2)? yes → 2's answer is 5, pop it
    waiting: [5]

Here is the key question: why must this be a stack and not, say, a queue? Look at the moment 5 arrives. The waiting numbers are 2 then 1, and 5 must resolve them from the most recent backwards — it checks 1 first (the newest waiter, on top), then 2. Why that order? Because 1 is closer to 5, so if 5 is big enough to be 1's answer, great — but we must check the nearest waiter first. And crucially, the waiters are always in decreasing order (2, 1), so the moment 5 meets a waiter it is not bigger than, it can stop — everyone below is even larger. Only a stack gives you that "newest waiter first, and they are conveniently sorted" behaviour for free. It is the same "resolve the most recent unresolved item" rule as brackets — the twist is that here "resolve" means "you are the next greater element" instead of "you are the matching closer."

Our problems: Next Greater Element, Daily Temperatures, Stock Span — and the heavyweights Largest Rectangle in a Histogram, Trapping Rain Water, Remove K Digits, and Sum of Subarray Minimums all live here. This one bucket is worth more than all the others combined.

Signal 3 — "Reverse, undo, or backtrack"

Trigger words: reverse, undo, redo, go back, most recent, backtrack, retrace.

Anything that needs to be undone in the reverse order it was done wants a stack. The browser back button, undo in an editor, retracing your steps out of a maze — the last action you took is the first one you reverse. This is LIFO in its most literal, everyday form.

Why a stack, concretely. Think about typing with backspaces, as in "backspace string compare." The string "ab#c" means: type a, type b, press backspace (#), type c. A backspace must delete the character typed most recently — not some random one. Watch:

a  → type a       result: [a]
b  → type b       result: [a, b]    ← b is the most recent character
#  → backspace → delete the top (b)  result: [a]
c  → type c       result: [a, c]  →  final string "ac"

Why is a stack the right tool and not, say, tracking a count? Because backspaces can chain — "abc###" deletes c, then b, then a, each time removing whatever is now most recent. After popping c, the character b becomes the new top and is the next thing a backspace removes. The stack automatically exposes the correct "most recent" character after every deletion, with zero bookkeeping. Undo is nothing but "pop the most recent unresolved action," which is the same core idea yet again — only now "resolve" means "erase."

Our problems: Reverse a Stack. And Backspace String Compare is a lovely disguised version — a backspace "undoes" the most recent typed character, which is exactly a pop.

Signal 4 — "Collapse or cancel adjacent items"

Trigger words: remove adjacent duplicates, cancel out, collide, simplify, reduce, eliminate neighbours.

If elements can interact with their immediate neighbour and cancel or combine — and after they cancel, the new neighbours might interact too — a stack is perfect. You push items one by one; each new item checks the top; if they cancel, you pop and the item beneath is now exposed to interact next. The stack automatically handles the "chain reaction" of cancellations.

Why a stack, concretely. Take "simplify path" on the Unix path /a/b/../c. Reading the folders left to right, a normal folder means "go in," and .. means "go back up one level" — which cancels the folder you entered most recently:

a  → enter a       path: [a]
b  → enter b       path: [a, b]      ← b is the folder we most recently entered
.. → go up → cancel the most recent folder (b), pop it   path: [a]
c  → enter c       path: [a, c]  →  simplified path "/a/c"

Why must this be a stack? Because .. does not cancel any folder — it cancels the deepest, most recently entered one, and after that cancellation the folder beneath becomes the new "current" one that the next .. would remove. That is a chain reaction (/a/b/c/../.. pops c, then b), and only a stack keeps the "most recent folder" correctly on top after every pop. Notice the beautiful bonus: when you finish, the stack is the answer — its contents, bottom to top, spell out the simplified path. Cancelling neighbours is once more the "deal with the most recent unresolved item" rule, where "resolve" means "annihilate."

Our problems (coming up): Asteroid Collision (asteroids moving toward each other destroy one another), Remove Duplicate Letters, and Simplify Path (a .. cancels the most recent folder — pop it off).

Signal 5 — "Process something naturally recursive, without recursion"

Trigger words: evaluate an expression, depth, tree traversal without recursion, deeply nested.

Recursion secretly uses a stack — the "call stack." So any problem that is naturally recursive or deeply nested can be rewritten with an explicit stack that you control. Parsing an arithmetic expression, walking a nested structure, evaluating postfix notation — all of these are "manage the layers of nesting yourself with a stack."

Why a stack, concretely. Take "evaluate Reverse Polish Notation" (postfix), where operators come after their numbers. Evaluate ["3", "4", "+", "5", "*"], meaning (3 + 4) * 5. Push numbers; when you hit an operator, it consumes the two most recent numbers:

3 → push        numbers: [3]
4 → push        numbers: [3, 4]   ← 3 and 4 are the two most recent operands
+ → pop 4, pop 3 → 3 + 4 = 7, push 7   numbers: [7]
5 → push        numbers: [7, 5]
* → pop 5, pop 7 → 7 * 5 = 35, push 35 numbers: [35]  →  answer 35

Why a stack? Because an operator always applies to the numbers computed most recently — the results waiting right on top. And notice the elegance: when + produces 7, that 7 goes back on the stack and instantly becomes one of the "most recent" operands for the next operator. The stack lets a partial result become the input to the next step automatically — which is exactly what the recursion call stack does when an inner computation returns a value to the expression that called it. Evaluating nested expressions is, once again, "finish the most recent unresolved piece first," where "resolve" means "compute and hand the result back up."

Our problems: Evaluate Reverse Polish Notation, Basic Calculator, Decode String.

A Quick Recognition Table

Keep this in your back pocket. When you read a problem, scan for these:

Let Us Practise Recognition (Without Solving)

The skill is spotting, so let us do three quick reads. I will not solve them — just show the bell ringing.

"Given a string of brackets, decide if it is valid." → The words "brackets" and "valid" light up Signal 1. Openers must close in reverse order. Stack. Benefit: check validity in one O(n) pass instead of repeatedly rescanning.

"For each day, how many days until a warmer temperature?" → "how many days until … warmer" is Signal 2 in plain clothes — it is a next greater question asking for a distance. Monotonic stack. Benefit: O(n) instead of O(n²) forward scanning.

"Simplify a Unix path like /a/./b/../c." → The .. means "go up one level," i.e. cancel the most recent folder. That is Signal 4. Stack. Benefit: each folder is pushed and popped once; the final stack is the simplified path.

Do you feel it? You did not need the algorithm. You matched the shape of the problem to a signal, and the tool announced itself.

When a Stack Is NOT the Answer (Just as Important)

A sharp engineer also knows the limits. A stack is the wrong instinct when:

• You need the oldest unfinished item, not the newest. That is First-In-First-Out — a queue, not a stack. (Think: processing tasks in arrival order, breadth-first search.)
• You need to search, sort, or access the middle. A stack only exposes the top. If you need "the 3rd element" or "is X anywhere in here," a stack fights you — use an array, hash set, or heap.
• You need the largest/smallest overall repeatedly, in changing data. That is a heap (priority queue), not a stack.

Knowing these boundaries is what stops you from forcing a stack onto a problem that quietly wanted something else — a mistake that reads very clearly to an interviewer.