π± Correct, quadratic, failed
"Next greater element for every item." Candidate A: "monotonic decreasing stack of indices β each index is pushed once and popped at most once, so O(n) amortized," then finishes with edge cases to spare. Candidate B writes the nested loop scanning rightward for every element: correct, untested at scale, O(nΒ²). At senior level, "correct but quadratic when a named linear pattern exists" is a no-hire on coding. The stack wasn't the hard part; recognizing that "next greater to the right" has a shape was.
π§° What you'll learn
- Stacks for nested structure β brackets, decoding, saved parse state
- Monotonic stacks β next greater/smaller, spans, histograms, in O(n)
- Fast & slow pointers β middle, cycle detection, gap-of-n
- In-place reversal β the three-pointer rotation, without losing the tail
- Dummy nodes β making the head a non-case
Pattern 1 β Stack: nested sequences and monotonic boundaries
Two distinct uses. Nesting: the most recently opened thing must close first β LIFO is the problem's own rule, so push opens, match closes, and a non-empty stack at the end means unclosed business. Monotonic: keep a stack of "elements still waiting for their answer," sorted; when a new element answers the top's question, pop and record. Each element enters and leaves the stack once β that's the amortized O(n) argument, and it's the sentence drill leaders want to hear.
| You see⦠| Think⦠|
|---|---|
| Matching pairs, "well-formed", nested brackets | Stack: push opens, validate closes |
| "Next greater/smaller element to the right" | Monotonic stack of indices |
| "Largest rectangle / span bounded by shorter bars" | Monotonic stack: pop when the boundary appears |
Parsing with nested contexts (decode k[...], undo) |
Stack of saved states β bookmark and restore |
| Per-element contribution (subarray minimums) | Monotonic stack gives left/right boundaries |
Template β monotonic stack (next greater):
def next_greater(nums):
res = [-1] * len(nums)
stack = [] # indices; their values decrease
for i, x in enumerate(nums):
while stack and x > nums[stack[-1]]:
j = stack.pop() # x answers the question for nums[j]
res[j] = i - j # or res[j] = x β whatever is asked
stack.append(i)
return res
Complexity: O(n) amortized time β n pushes, at most n pops β and O(n) space. Flip the comparison for next-smaller; scan right-to-left for previous-greater; store indices, not values, whenever the answer involves distances or spans.
Drills (easy β hard): Valid Parentheses β Daily Temperatures (next warmer day, in days) β Decode String (stack of saved strings + counts) β Largest Rectangle in Histogram (monotonic increasing stack).
Pattern 2 β Linked list: three moves cover everything
Almost every linked-list question is a composition of three moves: fast & slow pointers (middle, cycles, gap-of-n), in-place reversal (the prev/curr/next rotation), and a dummy node (give every node β even the head β a predecessor; build output lists with zero special cases). Reorder List = middle + reverse second half + interleave. Palindrome = the same, plus a value comparison. Recognize the composition, then assemble.
| You see⦠| Think⦠|
|---|---|
| "Detect a cycle" / "find the middle" | Fast & slow pointers |
| "Remove the nth node from the end" | Two pointers with an n-gap, plus a dummy |
| "Reverse all or part of the list, in place" | prev/curr/next rotation; save next before overwriting |
| "Merge / build a new list from pieces" | Dummy head + tail pointer, append by rewiring |
| Palindrome or reorder | middle + reverse second half + compare/interleave |
Template β the two building blocks:
def middle(head): # second middle when length is even
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow
def reverse(head): # in place; save next first
prev, curr = None, head
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prev
Complexity: every composition is O(n) time, O(1) space β that's the
point of pointer surgery. Two cautions to volunteer: the reversal's
assignment order matters (read curr.next before rewiring it), and the
O(1)-space palindrome mutates the input β you'd re-reverse to restore it
in production code. Flagging that trade-off unprompted is a senior signal.
Drills (easy β hard): Linked List Cycle β Remove Nth Node From End of List β Reorder List (all three moves at once) β Reverse Nodes in k-Group.
π€ Coding drill: run it
You are a staff engineer running a timed coding drill at a top tech company. Run one drill
drill with me on STACKS (including monotonic stacks) and LINKED LISTS.
1. Pick ONE problem that maps to these patterns at senior difficulty.
State it concisely: setup, input, output, one worked example, one
constraint worth noticing. Do not name the pattern it uses.
2. Enforce a 30-minute timer. Warn me at 5 minutes left; stop me at zero.
3. Ask which language I'm using and hold me to it.
4. Hints only when I explicitly ask, one rung at a time, never code:
(a) nudge β restate the constraint or point at a suspicious example;
(b) direction β name the family of approach, not the algorithm;
(c) structure β outline the algorithm's steps in words.
5. Drill like a senior loop: make me restate the problem, state my
complexity unprompted, and trace one example before I call it done.
6. When time is up or I say done, grade 1-5 each: correctness, complexity
analysis, communication, edge cases β one line of evidence per score,
then the single highest-leverage improvement.
Start with the problem statement. No preamble.
β You own it when
- You can deliver the push-once-pop-once amortized O(n) argument
- Next-greater vs next-smaller vs previous-greater is one comparison flip each
- The reversal loop works first try, including single-node lists
- You reach for a dummy node before writing any
if headspecial case - Reorder List assembles middle + reverse + interleave without notes
- You flag that O(1)-space list tricks mutate the input
π Jargon
| Term | What it means |
|---|---|
| LIFO | Last in, first out β the stack contract |
| Monotonic stack | A stack kept sorted (values rising or falling) so each pop answers a pending question |
| Amortized O(n) | Total work bounded by n even though single steps vary β the push/pop accounting |
| Fast & slow pointers | Two cursors at 1x and 2x; meet inside a cycle, land on the middle |
| Dummy (sentinel) node | A throwaway node before the head so every real node has a predecessor |
| In-place | Rewiring with O(1) extra memory |
| Pointer surgery | Reassigning next references to restructure the list without copying |
π When it goes wrong
- Blanking. Sort the problem by shape: does something nest (stack), reverse order (stack), or involve relinking (the three list moves)? Naming the shape out loud restarts the clock.
- Wrong pattern. Counting brackets instead of stacking them passes
interleavings like
( [ ) ]that are invalid. Counts can't see order. - Off-by-one on the head. Deleting the head breaks code with no predecessor. That is the dummy node's entire job β use it from the start.
- Lost tail on reversal. Overwriting
curr.nextbefore reading it orphans the rest of the list. If your loop runs once and stops, that's it. - Monotonic stack feels like magic. Trace a 6-element array by hand once β push, pop, record. The invariant ("waiting elements, kept sorted") is only believable after one trace.
- Silence during rewiring. Say which pointer you're reassigning and why. Linked lists are graded on narration as much as correctness.