Week 4: Stacks

Pattern family: Stacks · Time budget: 12 hours · Prerequisites: Weeks 1 through 3 done, with list, dict, and enumerate fresh. · Cold-revisit obligation: Group Anagrams, Trapping Rain Water.

Overview

A stack is the simplest data structure in the course, and that simplicity is the point: push to the top, pop from the top, last in is first out. In Python you do not import anything; a plain list is a stack, with append to push and pop to take the top back off. The skill this week is not the structure, it is the reflex of noticing when a problem is secretly a stack problem.

Two cues cover most of it. The first is anything about matching pairs or nesting: brackets, tags, function calls, undo histories. The most recently opened thing must be the first one closed, which is exactly last in, first out. The second cue is harder and worth more: the answer for one element depends on a later element you have not reached yet, “the next thing bigger than me,” “how many days until it gets warmer.” There you keep a stack of the elements still waiting for their answer, and you resolve them in a batch the moment the answer arrives. When that stack stays sorted as you go, it has a name, the monotonic stack, and it is the single most reused idea this week.

flowchart TD
    Q["Read the problem"] --> A{"Is the most recent thing<br/>the first one I must resolve?<br/>(matching pairs, nesting, undo)"}
    A -->|yes| H["Plain stack: push as you go,<br/>pop to match. O(n) time, O(n) space."]
    A -->|no| B{"Does each element's answer<br/>depend on a later element?<br/>('next greater', 'days until')"}
    B -->|yes| M["Monotonic stack: hold the<br/>elements still waiting; pop and<br/>resolve when the answer arrives."]
    B -->|no| C["Probably a different pattern.<br/>Keep reading the cues."]

Notice: the decision happens before you code, and the second branch is the valuable one. Most people see the bracket-matching stack; far fewer reach for the monotonic stack on “next greater” problems. Naming the pattern out loud (principle 1) is what makes the second branch fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the Week 0 refresher tools that this week leans on hardest.

Which two list methods turn a plain Python list into a stack, and what is the time cost of each?
Why is a.pop(0) the wrong way to take an item off a stack, and what does it cost compared to a.pop()?
What does enumerate(a) give you on each iteration, and why would you want the index, not just the value, when you build a stack?

Check your recall

1. `a.append(x)` pushes `x` onto the top, and `a.pop()` removes and returns the top item. Both are amortized O(1), because they act at the end of the list where no shifting is needed. A `list` is the stack; there is nothing to import. 2. `a.pop(0)` removes from the *front* of the list, which forces every remaining element to shift left by one, so it is O(n) per call. A stack only ever touches the top, so you always use `a.pop()` (no argument), which is O(1). Reaching for `pop(0)` is usually a sign you wanted a `deque`, not a stack. 3. `enumerate(a)` yields `(index, value)` pairs as you loop. On the "next greater" family you push the *index* rather than the value, because the answer you want is usually a distance or a position (how many steps until a larger value), and you can always read the value back with `a[index]`. Storing the index keeps both the position and the value available.

Learning objectives

By the end of this week you can:

Recognize the two stack cues (matching pairs or nesting, and “the answer depends on a later element”) and reach for a stack without being told.
Distinguish a plain stack from a monotonic stack, and state out loud whether a given monotonic stack is increasing or decreasing and why.
Decide whether to push values or indices onto the stack, and justify the choice from what the answer needs to report.
Construct a monotonic-stack solution that resolves each element exactly once, and explain why that makes the whole pass O(n) despite the inner loop.
Apply the sentinel-value trick to flush a stack cleanly at the end of a pass instead of writing a second clean-up loop.
Analyze the time and space complexity of your solution and name what dominates at scale.
Defend every line of each solution you commit, from memory, with no AI open.

Recognition cue

Anything LIFO (last in, first out) is a stack: matching pairs, nesting, undo, “the most recent one first.” The higher-value cue is when the answer for an element depends on a future element you have not processed yet, any “next greater,” “next smaller,” “how far until something larger” phrasing. That is the monotonic-stack signal: keep a stack of the elements still waiting for their answer, and the moment a new element resolves some of them, pop and record. If you catch yourself wanting a second loop that scans forward from each position to find “the next one that is bigger,” stop, that forward scan is what a monotonic stack collapses into a single pass.

Core concepts to internalize this week

A list is your stack. append pushes, pop() (no argument) takes the top. Both amortized O(1). You never need a separate stack type in Python, and you never use pop(0) on a stack.
Plain stack vs monotonic stack. A plain stack just remembers things in LIFO order (the bracket matcher). A monotonic stack additionally maintains an order invariant: every time you push, you first pop everything that violates it. “Increasing or decreasing?” is the question you must answer out loud, and it is decided by what you are searching for: a stack kept increasing finds next-smaller relationships, a stack kept decreasing finds next-greater ones.
Storing indices vs values. Push the value when the value is all you need (matching brackets). Push the index when the answer is a distance or position, or when you still need to read the value later (Daily Temperatures wants i - j, a gap between indices, so the index goes on the stack and you read the temperature back with temperatures[j]).
The “resolve on pop” move. In the monotonic family, you do the real work when you pop, not when you push. The element being popped is the one whose answer just became known; the element that triggered the pop is its answer. Internalize that the popped element, not the trigger, is the one you finalize.
The sentinel trick. After the main loop a monotonic stack can still hold unresolved elements. Rather than a separate clean-up loop, append a sentinel value to the input that is guaranteed to pop everything (a 0 for the histogram, since no bar is shorter than zero; a value larger than any temperature to flush Daily Temperatures). The sentinel forces the final flush in the same loop.
Why one inner while is still O(n). A monotonic-stack loop has a for over n elements with a while-pop inside, which looks like O(n^2). It is not: each element is pushed exactly once and popped at most once across the entire run, so the total pop work is O(n). Amortized analysis (count pushes and pops over the whole pass, not per step) is the lesson, and interviewers ask for exactly this argument.

Common misconception. “A stack is a special container I have to build or import in Python.” Reality. A list already is a stack: append to push, pop() to pop the top, both amortized O(1). There is no Stack class to reach for. The only trap is using pop(0) (front removal, O(n)) when you meant pop() (top removal, O(1)); if you find yourself popping the front, you wanted a deque, which is a queue, not this week’s pattern.

Common misconception. “Whenever I keep a stack of numbers, that is a monotonic stack.” Reality. A plain stack (the bracket matcher) keeps things in arrival order and never enforces a relationship between neighbors. A monotonic stack adds one rule: before each push, pop everything that breaks the increasing-or-decreasing invariant. That popping is where the work happens and where “next greater / next smaller” answers fall out. If your stack never pops based on a comparison between the incoming element and the top, it is a plain stack, and calling it monotonic will confuse you about why the algorithm is correct.

Common misconception. “The element that causes a pop is the one I compute the answer for.” Reality. It is the other way round. When the incoming element triggers a pop, the popped element is the one whose answer just arrived; the incoming element (and often the new stack top beneath it) are its boundaries. In Daily Temperatures the popped day is the one that finally gets a warmer day; in the histogram the popped bar is the rectangle’s height. Getting “who am I finalizing right now” backwards is the most common monotonic-stack bug.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday (the list-as-stack note is in section 3).

list as a stack: stack.append(x) to push, stack.pop() to pop the top, both amortized O(1). Never pop(0) on a stack.
stack[-1] to peek at the top without removing it, and if not stack: to test for empty.
enumerate(a) to walk values with their indices, so you can push indices and still read values.
Storing tuples on the stack, for example (value, count) or (index, height), when one number per slot is not enough.
The sentinel-value trick: append a guard value to the input so the final flush happens inside the main loop.
A dict of closing-to-opening bracket pairs ({')': '(', ']': '[', '}': '{'}) to make the matcher a table lookup instead of a chain of ifs.

These are tools you are allowed to know cold in an interview. The pattern (which problems are stack problems, and increasing vs decreasing) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/stacks.md. It must contain:

The recognition cue, in your own words (cover both the matching-pairs cue and the “answer depends on a later element” cue).
The algorithmic skeleton in pseudocode (a plain-stack matcher, and the monotonic-stack loop with its “resolve on pop” step).
Time and space complexity, general form, with the one-sentence amortized argument for why the monotonic loop is O(n) and not O(n^2).
Three edge cases (empty input, a single element, and an already-sorted input that never triggers a pop are good starts).
One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram/)

Largest Rectangle in Histogram is this course’s home for the monotonic stack and the sentinel-flush trick. It is the hardest stack problem you will see, and the one that proves you understand “resolve on pop”: when a bar shorter than the stack top arrives, the popped bar becomes a rectangle’s height and the width spans from just past the new stack top to the current index. The full guided walk-through, with the invariant, the width formula (and its off-by-one), the sentinel, and the exact complexity, is in canonical/largest-rectangle-in-histogram.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

Valid Parentheses (practice/valid-parentheses/). The plain-stack matcher: push openers, pop and check on every closer. This is the cleanest example of LIFO matching.
Min Stack (practice/min-stack/). A design problem: build a stack that also returns its current minimum in O(1). The lesson is augmenting a stack with extra bookkeeping that pushes and pops in lockstep.
Daily Temperatures (practice/daily-temperatures/). The monotonic stack on its home turf: “how many days until a warmer one,” answered by holding the days still waiting and resolving them on pop.
Generate Parentheses (practice/generate-parentheses/). A different flavor: generate all valid combinations. The implicit stack here is the recursion’s call stack, and the validity rule (never more closes than opens) is what prunes the search.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (you did this Monday).
Name the pattern aloud and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided.
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: describe the monotonic stack to a peer who has only done arrays and hashing, in three sentences. What goes on the stack, when do you pop, and what do you compute on the pop?
Connect: Daily Temperatures and Largest Rectangle in Histogram are the same pattern. What is “the element waiting for its answer” in each, and what event resolves it?
Monitor: is “increasing or decreasing” still something you have to derive each time, or can you now state it from the question being asked? Write the one sentence that would make it reflexive.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

What two cues in a problem statement should make you reach for a stack, and which one is the higher-value, more-often-missed cue?
In a monotonic stack, when the incoming element triggers a pop, which element do you compute the answer for, the one being popped or the one that triggered the pop?
A monotonic-stack loop is a for over n elements with a while-pop inside. Why is it O(n) and not O(n^2)?
⟲ From Week 0: why is a.pop() the right way to take the top off a stack while a.pop(0) is the wrong tool, and what is the cost of each?
⟲ From Week 1: Valid Parentheses uses a dict mapping closing brackets to opening brackets. Why is a dict lookup the right structure here, and what is its average cost?

Answer key

1. First cue: matching pairs or nesting (brackets, tags, undo), which is LIFO. Second, higher-value cue: the answer for an element depends on a later element ("next greater," "next smaller," "how far until larger"), which is the monotonic stack. The second is the one most people miss; they see the bracket stack but write a forward-scanning nested loop for "next greater." 2. The element being **popped**. Its answer just became known, and the incoming element (with the new stack top beneath it as the other boundary) supplies that answer. Computing the answer for the trigger instead is the classic bug. 3. Each element is pushed exactly once and popped at most once over the whole run, so the total number of pops across all iterations of the inner `while` is at most n. The work is amortized: you count pushes and pops over the entire pass, not per outer step, giving O(n) total. 4. `a.pop()` removes from the top (the end of the list) in amortized O(1) with no shifting; `a.pop(0)` removes from the front, shifting every remaining element left, which is O(n). A stack only touches the top, so always `pop()`; if you need front removal you wanted a `deque`. 5. The matcher repeatedly asks "what opener does this closer correspond to," which is a direct key-to-value lookup; a `dict` answers it in average O(1) and keeps the code a table lookup instead of a chain of `if`/`elif`. The cost is one average-O(1) read per character.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full instructions are in revisit.md.

Group Anagrams (Week 1, Arrays and Hashing). A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
Trapping Rain Water (Week 2, Two Pointers). A blind re-solve, same rules.

Neither is a stack problem, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. (Trapping Rain Water can be solved with a stack, which makes it a useful nudge, but its cleanest solution is the two-pointer one from Week 2; solve it however you recognize it.) Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Pattern Card complete at .tutor/pattern-cards/stacks.md, including the war-story field.
Canonical deep-dive done: Largest Rectangle in Histogram implemented yourself, with your short debrief (in your work repo).
Four practice problems solved, each with a five-question debrief in its commit message.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
.tutor/progress.md updated to “Week 4 complete; ready for Week 5.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 5 until all five are present.

Resources

Free, no account required:

[Article] Stack (abstract data type), the idea: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
[Article] Amortized analysis (why the monotonic loop is O(n)): https://en.wikipedia.org/wiki/Amortized_analysis
[Docs] Python list as a stack (append, pop): https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks