Phase 2 — Standard Coding Interview Patterns

Target level: Medium → Medium-Hard Expected duration: 4 weeks (12-week track) / 4 weeks (6-month track) / 4 weeks (12-month track) Weekly cadence: ~7 patterns introduced per week + 50–80 problems applying them under the framework

Why This Phase Is The Keystone

Phase 0 fixed your execution. Phase 1 fixed your vocabulary. Phase 2 fixes the only thing standing between you and a 95% Medium solve rate: pattern recognition.

Here is the empirical claim, and it is the entire reason this phase exists:

Any unseen LeetCode Medium becomes a 5-minute problem if you immediately recognize the pattern. The recognition takes ~30 seconds. The remaining 4–5 minutes are mechanical: instantiate the template, adapt to the problem’s specifics, write clean code, test.

Candidates who fail Mediums almost never fail because the pattern was hard. They fail because they did not recognize the pattern, so they tried to derive the algorithm from first principles in 25 minutes — a task the original algorithm researcher needed weeks for. Pattern recognition is not memorization; it is the compiled, searchable index of the entire algorithmic literature, indexed by problem-statement signal.

This is the difference between a candidate who looks at “find longest substring with at most K distinct characters” and thinks “sliding window with a frequency map, variable-size, shrink while violation, O(N)” in 20 seconds — and one who thinks “hmm, maybe two pointers? or sort? or…” and starts coding the wrong thing.

The 28 patterns below cover >90% of the problems asked at Big Tech, infrastructure companies, quant firms, and systems-engineering interviews. They are not all the patterns in existence — Phases 3–7 add advanced data structures, hard graphs, DP families, and competitive-programming techniques. But these 28 are the ones that, once internalized, transform Medium-level problems from “puzzles to solve” into “templates to instantiate”.

What You Will Be Able To Do After This Phase

• For any Medium problem, recognize the dominant pattern in <2 minutes of reading the problem statement.
• For each of the 28 patterns, write the canonical template from memory in <5 minutes.
• Distinguish between superficially-similar patterns (e.g., binary search on index vs binary search on answer) by their signal, not their syntax.
• Combine two patterns when one alone is insufficient (e.g., monotonic deque inside a sliding window; trie inside a backtracking DFS).
• Diagnose, when a pattern almost fits but not quite, exactly which generalization is needed (e.g., “this is sliding window but the window is variable and we need the max — we need a monotonic deque, not just a counter”).
• Communicate the pattern out loud at the moment of recognition: “This is X because of signal Y; the template is Z; expected complexity is W; the canonical pitfall is P.”

How To Read This Phase

This README is a reference manual for all 28 patterns, plus a recognition cheat sheet, plus a mastery checklist. Each pattern entry has a fixed structure:

1. Signal recognition — the words/structure in the problem statement that should fire this pattern within 2 minutes of reading
2. Canonical template — pseudocode you should be able to write from memory
3. Complexity — time and space, with the constants that matter
4. Common variants — the family tree (e.g., sliding window has fixed-size, variable-size, count-based variants)
5. Classic problems — 4–8 LeetCode problems where this pattern is the intended solution
6. Common bugs — the specific failure modes seen on this pattern in interviews

Read it linearly the first time. Refer back to specific patterns as you work the labs. After all labs, re-read the cheat-sheet table at the bottom — it should now read as obvious.

A Word On The 28 Patterns As A System

The patterns are not 28 unrelated tricks. They form a small number of meta-strategies:

• Linear scans with state (1, 2, 3, 4, 5, 9, 10, 11) — one pass, maintain a structure
• Reduce-to-sorted (6, 7, 11) — sort first, then exploit order
• Decision-on-monotonic-axis (8) — binary search where the axis is the answer itself
• Local-update primitives on linear/tree/graph topology (12, 13, 14, 15, 16, 17, 18) — propagate information along edges/pointers
• Enumerate with pruning (19) — exhaustive search with backtracking
• Memoize over a state space (20, 21, 22, 23, 24, 25) — cache answers to a DAG of subproblems
• Specialized structures for prefix/order queries (26, 27, 28) — trie, heap, K-way merge

Recognizing the meta-strategy first, then drilling down to the specific pattern, is often faster than trying to match all 28 patterns linearly.

Inline Pattern Reference

1. Two Pointers (opposite ends + same direction)

Signal Recognition (<2 min)

• The input is sorted (or can be sorted cheaply) and the problem asks for a pair/triplet with a property.
• The problem says “in-place” and you are scanning an array.
• The answer is symmetric: it depends on values from both ends shrinking inward.
• “Find pair such that a + b = target” with sorted input.
• “Remove duplicates in place” / “Move zeros”.

Canonical Template (Opposite Ends)

l, r = 0, len(a) - 1
while l < r:
    if condition(a[l], a[r]):
        # record / move both
        l += 1; r -= 1
    elif a[l] + a[r] < target:
        l += 1
    else:
        r -= 1

Canonical Template (Same Direction / Read-Write Pointers)

write = 0
for read in range(len(a)):
    if keep(a[read]):
        a[write] = a[read]
        write += 1
return write  # new length

Complexity

Time O(N) (each pointer moves monotonically — total moves bounded by N). Space O(1).

Common Variants

• Opposite ends: Two Sum on sorted, 3Sum, container with most water, valid palindrome.
• Same direction (slow/fast): remove duplicates, move zeros, partitioning around a pivot.
• Two arrays merge: merge two sorted arrays / lists.
• Cycle detection (Floyd): linked-list two-pointer where fast moves 2× slow.

Classic Problems

• LeetCode 1 — Two Sum (variant: sorted input becomes two pointers)
• LeetCode 15 — 3Sum
• LeetCode 11 — Container With Most Water
• LeetCode 26 — Remove Duplicates from Sorted Array
• LeetCode 75 — Sort Colors (Dutch national flag)
• LeetCode 125 — Valid Palindrome
• LeetCode 167 — Two Sum II Sorted
• LeetCode 283 — Move Zeroes

Common Bugs

• Forgetting to advance both pointers when a match is recorded → infinite loop.
• Off-by-one in while l < r vs l <= r (depends on whether single element is meaningful).
• Skipping duplicates: forgetting the inner while l < r and a[l] == a[l+1]: l += 1 after a recorded match (3Sum).

2. Sliding Window (fixed size + variable size)

Signal Recognition (<2 min)

• “Longest / shortest / count of subarrays / substrings with property X.”
• “Maximum sum of K consecutive elements.”
• “Subarray containing all of …” / “smallest substring that contains all chars of T.”
• The brute force is O(N²) over all subarrays. The property is monotone as the window grows or shrinks.

Canonical Template (Variable Size, Shrink-While-Violation)

l = 0
state = init()
best = 0
for r in range(len(a)):
    state = add(state, a[r])
    while violates(state):
        state = remove(state, a[l])
        l += 1
    best = max(best, r - l + 1)

Canonical Template (Fixed Size K)

state = init()
for i in range(K): state = add(state, a[i])
best = report(state)
for r in range(K, len(a)):
    state = add(state, a[r])
    state = remove(state, a[r - K])
    best = update(best, report(state))

Complexity

Time O(N) — each element enters and leaves the window at most once. Space O(window state size).

Common Variants

• Fixed-size: maximum sum, average, min/max via deque.
• Variable-size with constraint to shrink under: at most K distinct, sum ≤ S, no repeats.
• Variable-size with constraint to grow until satisfied: smallest window containing all of T (then shrink while still satisfying).
• Count of “good” windows = count of “good” right endpoints, often count += r - l + 1 after each step.

Classic Problems

• LeetCode 3 — Longest Substring Without Repeating Characters
• LeetCode 76 — Minimum Window Substring
• LeetCode 209 — Minimum Size Subarray Sum
• LeetCode 340 — Longest Substring with At Most K Distinct Characters
• LeetCode 424 — Longest Repeating Character Replacement
• LeetCode 567 — Permutation in String
• LeetCode 992 — Subarrays with K Different Integers (the “exactly K = atMost(K) − atMost(K-1)” trick)
• LeetCode 1004 — Max Consecutive Ones III

Common Bugs

• Updating the answer inside the shrink loop instead of after — leads to recording invalid windows.
• Forgetting that while (not if) is required when shrinking — a single character can violate by >1.
• Counting “exactly K” as atMost(K) instead of atMost(K) − atMost(K-1).
• For “no repeats”, forgetting that the freq map needs decrement on shrink, not just delete.

3. Prefix Sums (1D + 2D)

Signal Recognition (<2 min)

• “Sum/count over a range [l, r]” with many queries or asked once with N up to 10^5.
• “Subarray with sum equal to K” (prefix sum + hashmap of seen prefix sums).
• “Number of subarrays with sum divisible by K” (prefix sums mod K).
• 2D: “matrix region sum” / “rectangle of ones”.

Canonical Template (1D)

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + a[i]
# range sum a[l..r]:  prefix[r + 1] - prefix[l]

Canonical Template (2D)

P = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(m):
        P[i+1][j+1] = a[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
# region (r1,c1)..(r2,c2):
# P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Complexity

Build O(N) (1D) or O(NM) (2D). Each query O(1). Space O(N) or O(NM).

Common Variants

• Subarray-sum-equals-K with hashmap {prefix_sum: count}.
• XOR prefix for “subarray XOR equals K” — same trick, different operator (any group operator works).
• Mod K prefix for “subarray sum divisible by K” — bucket prefixes by their value mod K.
• Count of negative numbers in a sorted matrix via row prefix.
• 2D rectangle sum, 2D max-sum submatrix.

Classic Problems

• LeetCode 303 — Range Sum Query Immutable
• LeetCode 304 — Range Sum Query 2D Immutable
• LeetCode 560 — Subarray Sum Equals K
• LeetCode 525 — Contiguous Array
• LeetCode 974 — Subarray Sums Divisible by K
• LeetCode 1248 — Count Number of Nice Subarrays
• LeetCode 1314 — Matrix Block Sum

Common Bugs

• Off-by-one: prefix is size N+1, indexed 0..N. Range [l,r] is prefix[r+1] - prefix[l]. Get this wrong once and it’s wrong forever.
• 2D inclusion-exclusion sign flip.
• Initializing the hashmap: {0: 1} is needed for “subarrays starting at index 0” in subarray-sum-equals-K.
• Integer overflow: prefix sums at N=10^5 with values up to 10^9 exceed 32-bit. Use 64-bit.

4. Difference Arrays (range update O(1))

Signal Recognition (<2 min)

• “Apply many range updates (l, r, +v) then query the final array.”
• “How many flights on day X” given (start, end, count) triples.
• “Maximum overlap of intervals.”
• The brute would be O(N · Q); a difference array makes it O(N + Q).

Canonical Template

diff = [0] * (n + 1)
for (l, r, v) in updates:
    diff[l] += v
    diff[r + 1] -= v
a = [0] * n
cur = 0
for i in range(n):
    cur += diff[i]
    a[i] = cur

Complexity

O(N + Q) total. Space O(N).

Common Variants

• Booking-system style: count of overlapping intervals at each point.
• 2D difference (imos method): stamp rectangles, prefix-sum twice.
• Sweep line equivalence: events at l and r+1 are exactly the events of a sweep; difference array is the “discretized sweep”.
• Range add + point query with later updates: Fenwick/BIT becomes more flexible (Phase 3).

Classic Problems

• LeetCode 1109 — Corporate Flight Bookings
• LeetCode 1854 — Maximum Population Year
• LeetCode 2381 — Shifting Letters II
• LeetCode 370 — Range Addition
• LeetCode 731 — My Calendar II
• LeetCode 2536 — Increment Submatrices by One (2D diff)

Common Bugs

• Forgetting the r + 1 cancellation → all suffixes get incremented.
• Using [0] * n instead of [0] * (n + 1) — causes index OOB on diff[r + 1].
• For 2D: forgetting the inclusion-exclusion of all four corners.

5. Hashing Patterns (frequency / complement / grouping)

Signal Recognition (<2 min)

• “Find target - x” for some target → complement in a hashmap.
• “Most/least frequent X” → frequency map, often paired with heap/sort.
• “Group by canonical form” (anagrams, isomorphic strings) → grouping map keyed by canonical form.
• “Has any element appeared twice within K positions?” → sliding window of size K with a hashset.

Canonical Templates

# complement
seen = {}
for i, x in enumerate(a):
    if (target - x) in seen:
        return [seen[target - x], i]
    seen[x] = i

# frequency
from collections import Counter
freq = Counter(a)
top = freq.most_common(K)

# grouping by canonical form
from collections import defaultdict
groups = defaultdict(list)
for s in strs:
    groups[canonical(s)].append(s)

Complexity

O(N) average (hash). Space O(N) worst case. Adversarial inputs may degrade to O(N²) — see Phase 1 §3.

Common Variants

• Two-Sum (complement).
• Group anagrams (grouping by char-count tuple).
• Longest consecutive sequence (set-membership test for x-1 to find sequence starts).
• Subarray sum = K (prefix-sum + complement — see pattern 3).
• Bullet-proof word ladder (wildcards as keys).

Classic Problems

• LeetCode 1 — Two Sum
• LeetCode 49 — Group Anagrams
• LeetCode 128 — Longest Consecutive Sequence
• LeetCode 217 — Contains Duplicate
• LeetCode 219 — Contains Duplicate II
• LeetCode 347 — Top K Frequent Elements
• LeetCode 451 — Sort Characters by Frequency

Common Bugs

• Java int[] as a key — uses object identity, not value equality. (See Phase 1 lab 03.)
• Inserting into seen before the lookup, when the problem needs distinct indices.
• Using ordered map when unordered suffices (e.g., Java TreeMap instead of HashMap) → log-N factor.
• Reusing a mutable buffer as a key — all keys alias to the latest buffer.

6. Sorting + Greedy (sort to enable greedy)

Signal Recognition (<2 min)

• “Maximum number of non-overlapping …” → sort by end, take earliest end.
• “Minimum number of meeting rooms / arrows / platforms” → sort by start; sweep.
• “Schedule jobs to maximize profit / minimize lateness.”
• “Pair items optimally” → sort one or both, pair by index.
• The brute force is “try all pairings” (factorial); sortedness collapses it to linear.

Canonical Template

a.sort(key=lambda x: x[1])  # sort by end
chosen = []
last_end = -inf
for (s, e) in a:
    if s >= last_end:
        chosen.append((s, e))
        last_end = e
return len(chosen)

Complexity

Time O(N log N) for the sort, O(N) for the sweep. Space O(1) beyond sort buffer.

Common Variants

• Activity selection — sort by end, take earliest end.
• Minimum platforms / arrows — sort by start (or by end for arrows).
• Pairing: sort and pair by index (e.g., “minimum pair-sum to fit a target”).
• Two arrays joined — sort both, two-pointer merge.
• Custom comparator — sort by a derived value (profit/time, deadline-then-profit, etc.) requires proving the exchange argument.

Classic Problems

• LeetCode 56 — Merge Intervals
• LeetCode 252 — Meeting Rooms (and 253 — Meeting Rooms II)
• LeetCode 435 — Non-overlapping Intervals
• LeetCode 452 — Minimum Number of Arrows to Burst Balloons
• LeetCode 502 — IPO (sort by capital, pq by profit)
• LeetCode 630 — Course Schedule III
• LeetCode 881 — Boats to Save People

Common Bugs

• Sorting by the wrong key (start vs end). Activity selection by start is wrong.
• Forgetting to prove the exchange argument before committing to greedy. (See Phase 6.)
• For “non-overlap” problems: confusing s >= last_end (touching allowed) vs s > last_end (strict).
• For comparator: subtraction overflow in Java/JS when sorting int differences.

7. Binary Search On Index (sorted array)

Signal Recognition (<2 min)

• The input is sorted (or has a sorted property like a rotated sorted array).
• The task is “find X” / “find first / last X” / “find insertion point”.
• N is large (10^5+), and the brute O(N) is acceptable but O(log N) is wanted (or there are many queries).

Canonical Template (lower_bound)

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # first index with a[i] >= target

Complexity

Time O(log N) per query. Space O(1).

Common Variants

• lower_bound, upper_bound, exact-match.
• Rotated sorted array — pick the half that is sorted, decide which half contains the target.
• Search in 2D matrix — flatten coordinates, binary search the 1D index, or descend from top-right.
• Find peak — local-property binary search (no global sort required).

Classic Problems

• LeetCode 33 — Search in Rotated Sorted Array
• LeetCode 34 — Find First and Last Position
• LeetCode 35 — Search Insert Position
• LeetCode 74 — Search a 2D Matrix
• LeetCode 153 — Find Minimum in Rotated Sorted Array
• LeetCode 162 — Find Peak Element
• LeetCode 240 — Search a 2D Matrix II (descend from top-right; not binary search per se)

Common Bugs

• (lo + hi) // 2 overflow in C++/Java — use lo + (hi - lo) // 2.
• Wrong loop condition (< vs <=) interacting with wrong update (mid vs mid + 1 vs mid - 1) — pick a single canonical form (we use half-open [lo, hi) here) and stick with it.
• Off-by-one when reconstructing the actual index after finding the bound.
• For rotated arrays, forgetting that duplicates break the binary search invariant.

8. Binary Search On Answer (parametric / monotonic predicate)

Signal Recognition (<2 min)

• The problem asks for the minimum X such that property P(X) holds (or maximum X such that ¬P).
• P is monotonic in X (if P(X) holds, P(X+1) also holds — or vice versa).
• Direct construction is hard, but verifying a candidate answer in O(N) or O(N log N) is easy.
• Constraints: answer’s range is enormous (10^9, 10^18), but verification per candidate is cheap.
• Keywords: “smallest capacity / speed / time”, “largest minimum”, “split into K parts minimize max sum”.

Canonical Template

def feasible(x): ...  # returns True if x is a valid answer or larger

lo, hi = LOW, HIGH
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo  # smallest feasible value

Complexity

Time O(log(range) · cost_of_feasible). Space O(1) beyond feasible.

Common Variants

• Min-max / max-min (split array into K parts to minimize the maximum part sum).
• Capacity / rate (capacity to ship within D days; Koko eating bananas).
• Time (earliest day to finish; latest day before failure).
• K-th smallest in matrix / multiplication table (binary search the value, count “≤ value” entries).
• Floating-point binary search — replace lo < hi with hi - lo > eps and pick the right output.

Classic Problems

• LeetCode 410 — Split Array Largest Sum
• LeetCode 875 — Koko Eating Bananas
• LeetCode 1011 — Capacity To Ship Packages Within D Days
• LeetCode 1283 — Find Smallest Divisor Given a Threshold
• LeetCode 1482 — Minimum Number of Days to Make m Bouquets
• LeetCode 668 — Kth Smallest Number in Multiplication Table
• LeetCode 1539 — Kth Missing Positive Number

Common Bugs

• Wrong direction of monotonicity — verify by hand on small cases before committing.
• Wrong search bounds (lo too high → miss the answer; hi too low → infinite loop).
• feasible has a subtle off-by-one — write and test feasible independently before plugging it into the binary search.
• Returning lo - 1 or hi + 1 accidentally — the half-open [lo, hi) template returns lo, period.

9. Monotonic Stack (next-greater / histogram / span)

Signal Recognition (<2 min)

• “Next/previous greater/smaller element” on each index.
• “Largest rectangle in histogram” / “max area of submatrix of 1’s” (uses histogram per row).
• “Daily temperatures” / “stock span” / “trapping rainwater” (an O(N) variant).
• The brute force is “for each i, scan right (or left) until …” — O(N²); the monotonic stack collapses it to O(N).

Canonical Template (Next Greater)

n = len(a)
result = [-1] * n
stack = []  # indices, values strictly decreasing
for i in range(n):
    while stack and a[stack[-1]] < a[i]:
        result[stack.pop()] = a[i]
    stack.append(i)

Complexity

Time O(N) — each index pushed and popped at most once. Space O(N) for the stack.

Common Variants

• Next/previous, greater/smaller (4 combinations) — a sign flip and a comparator change.
• Histogram problems: maintain stack of indices with strictly increasing heights; on pop, the popped index sees the current as its right boundary and the new top as its left.
• Sum of subarray minimums — for each element, count subarrays where it is the min.
• Trapping rainwater — stack of decreasing heights; each pop produces a “trapped” volume.
• Sliding window max — uses a monotonic deque (pattern 10), not stack.

Classic Problems

• LeetCode 84 — Largest Rectangle in Histogram
• LeetCode 85 — Maximal Rectangle (histogram per row)
• LeetCode 42 — Trapping Rain Water (stack variant)
• LeetCode 496 — Next Greater Element I
• LeetCode 503 — Next Greater Element II (circular)
• LeetCode 739 — Daily Temperatures
• LeetCode 901 — Online Stock Span
• LeetCode 907 — Sum of Subarray Minimums

Common Bugs

• Comparator: < vs <= matters when there are duplicates and the problem wants “strictly greater” vs “greater-or-equal”. Pick the variant that gives unique boundary assignment.
• Forgetting to drain the stack at the end (for problems where unprocessed elements have no next-greater).
• Histogram: forgetting the sentinel 0 appended at the end — without it the last bar may not be evaluated.
• Storing values vs indices — almost always store indices, derive values when needed.

10. Monotonic Queue (sliding window max/min in O(N))

Signal Recognition (<2 min)

• “Maximum / minimum of every window of size K” (or variable size) in O(N).
• DP transitions of the form dp[i] = max(dp[j] + ...) for j in some window — the deque maintains the candidate js.
• Constrained Subsequence Sum, Jump Game VI.

Canonical Template (Sliding Window Max)

from collections import deque
dq = deque()  # holds indices, a[dq] strictly decreasing
result = []
for i, x in enumerate(a):
    while dq and a[dq[-1]] <= x:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - K:
        dq.popleft()
    if i >= K - 1:
        result.append(a[dq[0]])

Complexity

Time O(N). Space O(K) for the deque.

Common Variants

• Sliding-window min (flip comparator).
• DP optimization: when dp[i] = f(max{dp[j] : j ∈ window}), the deque maintains the max efficiently.
• Shortest subarray with sum at least K (LC 862) — combine prefix sums with a monotonic deque on prefix-sum values.

Classic Problems

• LeetCode 239 — Sliding Window Maximum
• LeetCode 862 — Shortest Subarray with Sum at Least K
• LeetCode 918 — Maximum Sum Circular Subarray
• LeetCode 1425 — Constrained Subsequence Sum
• LeetCode 1696 — Jump Game VI

Common Bugs

• Storing values, not indices — lose the ability to evict by window position.
• <= vs < for the back-eviction (with duplicates, the wrong choice can leave stale entries that survive past their window).
• Forgetting to evict the front when its index is out of window.
• Reporting before the window is full (i >= K - 1).

11. Intervals (sort by start, merge / sweep)

Signal Recognition (<2 min)

• “Merge overlapping intervals”, “insert interval”, “remove minimum to make non-overlapping”.
• “Meeting rooms” / “minimum platforms” / “maximum concurrent events”.
• “Employee free time” / “interval intersection”.

Canonical Template (Merge)

intervals.sort(key=lambda x: x[0])
merged = []
for s, e in intervals:
    if merged and merged[-1][1] >= s:
        merged[-1][1] = max(merged[-1][1], e)
    else:
        merged.append([s, e])

Canonical Template (Sweep Line)

events = []
for s, e in intervals:
    events.append((s, +1))
    events.append((e, -1))  # or (e + 1, -1) for closed intervals on integers
events.sort()
cur = peak = 0
for _, delta in events:
    cur += delta
    peak = max(peak, cur)

Complexity

Sort O(N log N), sweep O(N). Space O(N) for events.

Common Variants

• Merge (sort by start, fold).
• Sweep (events at endpoints, count concurrent).
• Heap-of-end-times (for “minimum platforms / rooms”).
• Interval trees / balanced BSTs (Phase 3) for online updates.
• Tie-breaking: end events before start events (or vice versa) depending on whether endpoint contact counts as overlap.

Classic Problems

• LeetCode 56 — Merge Intervals
• LeetCode 57 — Insert Interval
• LeetCode 252 — Meeting Rooms
• LeetCode 253 — Meeting Rooms II
• LeetCode 435 — Non-overlapping Intervals
• LeetCode 759 — Employee Free Time
• LeetCode 986 — Interval List Intersections
• LeetCode 1851 — Minimum Interval to Include Each Query

Common Bugs

• Sorting by end when start was needed (or vice versa).
• Tie-breaking events at the same time wrong — touching intervals counted as overlap (or not) depending on the problem.
• Mutating the input list while iterating (Java ConcurrentModificationException).

12. Linked List Manipulation (reverse / detect cycle / merge)

Signal Recognition (<2 min)

• The data structure given is ListNode.
• Tasks: reverse, reverse in groups, detect cycle, find middle, merge sorted, partition, deep copy.
• Often combined with a dummy head for return-pointer simplification.

Canonical Templates

# reverse
prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev, curr = curr, nxt
return prev

# detect cycle (Floyd)
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast: return True
return False

Complexity

All operations O(N) time, O(1) space (recursion variants are O(N) stack).

Common Variants

• Reverse, reverse in K-group, reverse between m..n.
• Floyd’s cycle detection + finding cycle start (mathematical trick: reset slow to head, advance both at speed 1).
• Find middle with slow/fast (handle even/odd length).
• Merge two sorted with dummy.
• Deep copy with random pointer — interleave clones, then split.
• LRU cache (Phase 3) is doubly-linked list + hashmap.

Classic Problems

• LeetCode 21 — Merge Two Sorted Lists
• LeetCode 25 — Reverse Nodes in k-Group
• LeetCode 138 — Copy List with Random Pointer
• LeetCode 141 — Linked List Cycle
• LeetCode 142 — Linked List Cycle II
• LeetCode 206 — Reverse Linked List
• LeetCode 234 — Palindrome Linked List
• LeetCode 876 — Middle of the Linked List

Common Bugs

• Not using a dummy head when the head can change → special-case branches everywhere.
• Reverse: losing the next pointer because of assignment order.
• Cycle detection: incorrect math for finding the cycle start.
• Returning the wrong end (curr is null after the loop; prev is the new head).

13. Tree DFS (preorder / inorder / postorder)

Signal Recognition (<2 min)

• The input is a tree (binary, n-ary, or just a graph that happens to be a tree).
• The answer is computed by combining results from subtrees (postorder) or by augmenting a top-down state (preorder).
• BST in-order traversal yields sorted values.
• “Validate”, “diameter”, “lowest common ancestor”, “serialize / deserialize”, “path sum”.

Canonical Template (Postorder)

def dfs(node):
    if not node: return base
    L = dfs(node.left)
    R = dfs(node.right)
    return combine(node.val, L, R)

Complexity

Time O(N) — each node visited once. Space O(H) recursion (H = height; up to N for skewed trees).

Common Variants

• Inorder for BSTs (yields sorted; use for “kth smallest” / “validate BST”).
• Preorder when state flows top-down (e.g., max value on path).
• Postorder when answer combines subtree results (e.g., diameter, LCA).
• Iterative with explicit stack — required when recursion depth could overflow (N=10^5 in Python ≈ stack limit).
• Morris traversal for O(1) extra space (Phase 3).

Classic Problems

• LeetCode 94 — Binary Tree Inorder Traversal
• LeetCode 98 — Validate Binary Search Tree
• LeetCode 104 — Maximum Depth of Binary Tree
• LeetCode 124 — Binary Tree Maximum Path Sum
• LeetCode 230 — Kth Smallest Element in a BST
• LeetCode 236 — Lowest Common Ancestor of a Binary Tree
• LeetCode 297 — Serialize and Deserialize Binary Tree
• LeetCode 543 — Diameter of Binary Tree

Common Bugs

• “Validate BST” by checking only left.val < node.val < right.val (local check) — must pass (min, max) bounds top-down.
• Confusing “max path through node” with “max path starting at node” — the diameter trick.
• Stack overflow for deep trees in Python (default limit 1000) — sys.setrecursionlimit or go iterative.
• Mutating shared path list without backtracking → wrong “all paths” output.

14. Tree BFS (level order / right side view)

Signal Recognition (<2 min)

• “Level order / level by level / per-depth” output.
• “Right (or left) side view” — last node at each level.
• “Minimum depth” — first leaf encountered in BFS.
• “Connect next pointers per level” (LC 116/117).
• “Vertical / diagonal traversal” — same machinery with different keying.

Canonical Template

from collections import deque
q = deque([root])
levels = []
while q:
    size = len(q)
    cur = []
    for _ in range(size):
        node = q.popleft()
        cur.append(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
    levels.append(cur)

Complexity

Time O(N), space O(W) (W = max width; up to N/2 for balanced).

Common Variants

• Plain level order, with or without per-level grouping.
• Zigzag (alternate appending direction).
• Right-/left-side view (last/first per level).
• Minimum depth (first leaf — cuts BFS short on the goal).
• Bottom-up (collect all levels then reverse).

Classic Problems

• LeetCode 102 — Binary Tree Level Order Traversal
• LeetCode 103 — Binary Tree Zigzag Level Order Traversal
• LeetCode 107 — Binary Tree Level Order Traversal II
• LeetCode 111 — Minimum Depth of Binary Tree
• LeetCode 116 — Populating Next Right Pointers in Each Node
• LeetCode 199 — Binary Tree Right Side View
• LeetCode 314 — Binary Tree Vertical Order Traversal

Common Bugs

• Using list.pop(0) (Python) → O(N²). Use deque.
• Forgetting to capture size = len(q) before the inner loop — q grows during the loop and you’d over-iterate.
• Returning the level structure backwards (or forwards) accidentally.
• Null root not handled.

15. Graph DFS (cycle / connected components / topo via DFS)

Signal Recognition (<2 min)

• The structure is a graph (general, not necessarily tree).
• Tasks: count connected components, detect cycle, topologically order, find bridges/articulation points (Phase 4).
• Recursion is fine (or you simulate it with an explicit stack).

Canonical Template (Connected Components)

visited = [False] * n
def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]: dfs(v)

components = 0
for u in range(n):
    if not visited[u]:
        dfs(u); components += 1

Canonical Template (Cycle Detection in Directed Graph)

WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def has_cycle(u):
    color[u] = GRAY
    for v in adj[u]:
        if color[v] == GRAY: return True
        if color[v] == WHITE and has_cycle(v): return True
    color[u] = BLACK
    return False

Complexity

Time O(V + E). Space O(V) for the recursion + visited arrays.

Common Variants

• Connected components (undirected).
• Strongly connected components (Tarjan / Kosaraju — Phase 4).
• Cycle detection: undirected uses a parent-check; directed uses tri-color (WHITE/GRAY/BLACK).
• Topological sort via DFS — postorder of a DAG, reversed.
• Number of islands / flood fill on grid graphs.

Classic Problems

• LeetCode 200 — Number of Islands
• LeetCode 207 — Course Schedule (cycle detection in directed graph)
• LeetCode 261 — Graph Valid Tree
• LeetCode 323 — Number of Connected Components
• LeetCode 695 — Max Area of Island
• LeetCode 1192 — Critical Connections (Tarjan bridges)

Common Bugs

• Forgetting to mark visited before recursing → infinite recursion.
• For undirected cycle detection, treating “going back to parent” as a cycle.
• Stack overflow for deep recursion in Python on N=10^5 — convert to iterative.
• For grid problems, going out of bounds because the bounds check is after the recursion call.

16. Graph BFS (shortest unweighted / multi-source / 0-1)

Signal Recognition (<2 min)

• Shortest path on an unweighted graph (or weights ∈ {0, 1}).
• “Minimum number of steps / moves / transformations.”
• Multi-source: “shortest distance from any of these sources” (rotting oranges, walls and gates).
• 0-1 BFS: use a deque, push 0-weight to front, 1-weight to back.

Canonical Template

from collections import deque
dist = [-1] * n
q = deque([src]); dist[src] = 0
while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

Complexity

Time O(V + E). Space O(V).

Common Variants

• Standard BFS for unweighted shortest path.
• Multi-source BFS — push all sources with distance 0, then run.
• 0-1 BFS with deque for graphs with weights ∈ {0, 1}.
• Bidirectional BFS for shortest path between fixed source and target — both halves explore O(b^(d/2)) instead of O(b^d).
• Word-ladder pattern — neighbors via wildcard buckets, not adjacency list.

Classic Problems

• LeetCode 127 — Word Ladder
• LeetCode 286 — Walls and Gates (multi-source)
• LeetCode 542 — 01 Matrix (multi-source)
• LeetCode 752 — Open the Lock
• LeetCode 994 — Rotting Oranges (multi-source)
• LeetCode 1162 — As Far from Land as Possible
• LeetCode 2290 — Minimum Obstacle Removal to Reach Corner (0-1 BFS)

Common Bugs

• Marking visited at dequeue time (lets duplicates pile up) instead of at enqueue time.
• Using BFS for weighted graphs (distinct positive weights) — wrong; use Dijkstra (Phase 4).
• Forgetting that “minimum depth of binary tree” is BFS, not DFS — DFS visits all leaves; BFS halts on the first.

17. Topological Sort (Kahn’s / DFS-based)

Signal Recognition (<2 min)

• “Order tasks given dependencies” / “course prerequisites” / “build order” / “alien dictionary”.
• Detecting whether a DAG has a cycle (failure = there’s a cycle).
• DP on DAG (some tasks need a topological order to evaluate).

Canonical Template (Kahn’s BFS)

indeg = [0] * n
for u in range(n):
    for v in adj[u]:
        indeg[v] += 1
q = deque([u for u in range(n) if indeg[u] == 0])
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0: q.append(v)
return order if len(order) == n else []  # else: cycle

Canonical Template (DFS Postorder)

order = []
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(u):
    color[u] = GRAY
    for v in adj[u]:
        if color[v] == GRAY: raise CycleError
        if color[v] == WHITE: dfs(v)
    color[u] = BLACK
    order.append(u)
for u in range(n):
    if color[u] == WHITE: dfs(u)
order.reverse()

Complexity

Time O(V + E). Space O(V + E).

Common Variants

• Kahn’s — gives a valid order; cycle detection by len(order) != n.
• DFS postorder reversed — alternate algorithm; same result.
• Lexicographically smallest topological order — use a min-heap instead of FIFO queue (Kahn’s).
• All possible topological orderings — backtracking over orderings (LC 1632).
• DP on DAG following topological order.

Classic Problems

• LeetCode 207 — Course Schedule
• LeetCode 210 — Course Schedule II
• LeetCode 269 — Alien Dictionary
• LeetCode 310 — Minimum Height Trees (peeling leaves — relative)
• LeetCode 329 — Longest Increasing Path in a Matrix (DP on DAG)
• LeetCode 444 — Sequence Reconstruction
• LeetCode 1136 — Parallel Courses
• LeetCode 2115 — Find All Possible Recipes

Common Bugs

• Building the graph with reversed edges (prerequisites vs unlocks).
• Not detecting cycles (returning a partial order silently).
• For lexicographic smallest, using a regular queue instead of a heap.
• Indegrees off-by-one when the same edge is duplicated in input.

18. Union-Find (connectivity / Kruskal preview)

Signal Recognition (<2 min)

• “Are X and Y connected after these operations?” (online connectivity).
• “Number of connected components” with dynamic union operations (DFS once-and-done is sufficient for static).
• Kruskal’s MST (Phase 4) — sort edges, union components.
• Equation problems (LC 399 — Evaluate Division — weighted union-find).

Canonical Template

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

Complexity

Per operation: amortized O(α(N)) ≈ O(1) with both path compression and union by rank/size. Without rank: O(log N) amortized. Without compression: O(log N) amortized. Naive: O(N) worst case.

Common Variants

• Vanilla connectivity.
• With size — track component sizes for “find largest component”.
• Weighted — each edge has a multiplier (LC 399 — Evaluate Division).
• With rollback (Phase 3) — for offline / divide-and-conquer queries.
• Kruskal MST — sort edges by weight, union the endpoints if they’re in different components.

Classic Problems

• LeetCode 200 — Number of Islands (DSU alternative)
• LeetCode 261 — Graph Valid Tree
• LeetCode 305 — Number of Islands II (online)
• LeetCode 399 — Evaluate Division
• LeetCode 547 — Number of Provinces
• LeetCode 684 — Redundant Connection
• LeetCode 721 — Accounts Merge
• LeetCode 1319 — Number of Operations to Make Network Connected

Common Bugs

• Forgetting path compression — TLE on adversarial chain inputs.
• find recursion that deepens the stack (use iterative or two-pass).
• Updating rank only when unequal — but updating it always makes the rank wrong by +1.
• Comparing parent[x] == x vs find(x) == x — they differ before compression converges.

19. Backtracking (subsets / permutations / combinations / N-queens)

Signal Recognition (<2 min)

• “Find all subsets / permutations / combinations / arrangements satisfying X.”
• “Place K items respecting constraints” (N-queens, Sudoku).
• The brute force is exponential, and you can’t shave it polynomially — but you can prune aggressively.

Canonical Template

def backtrack(state, choices):
    if is_solution(state):
        record(state); return
    for choice in choices:
        if not valid(state, choice): continue
        apply(state, choice)
        backtrack(state, next_choices(choices, choice))
        undo(state, choice)

Complexity

• Subsets: O(N · 2^N).
• Permutations: O(N · N!).
• N-queens: O(N!) worst case, dramatically pruned in practice. Space O(depth) for recursion + O(state size).

Common Variants

• Subsets (include/exclude each element).
• Permutations (choose unused; track used set or swap-in-place).
• Combinations (start index to avoid reordering duplicates).
• Partition into subsets (assign each element to a bucket; prune by sorting + skipping equal-prefix bucket).
• Constraint satisfaction (N-queens, Sudoku) — prune with row/column/box bitmasks.
• String backtracking (palindrome partitioning, restore IP addresses, generate parentheses).

Classic Problems

• LeetCode 17 — Letter Combinations of a Phone Number
• LeetCode 22 — Generate Parentheses
• LeetCode 39 — Combination Sum
• LeetCode 46 — Permutations
• LeetCode 51 — N-Queens
• LeetCode 78 — Subsets
• LeetCode 79 — Word Search
• LeetCode 90 — Subsets II (with duplicates)
• LeetCode 131 — Palindrome Partitioning
• LeetCode 212 — Word Search II (with trie)

Common Bugs

• Forgetting to undo the choice before returning → state corruption.
• Recording state by reference, not by copy → all results alias the final state.
• Duplicate handling: forgetting if i > start and a[i] == a[i-1]: continue (for sorted input with duplicates).
• For grid backtracking, forgetting to mark visited or not unmarking on return.

20. Basic DP (memoization vs tabulation)

Signal Recognition (<2 min)

• “Number of ways to …” / “Min/max … over choices.”
• Recursive structure with overlapping subproblems: the same sub-question is asked multiple times.
• Optimal substructure: the optimal answer combines optimal answers to subproblems.
• The brute is exponential; with memo the state space is polynomial.

Canonical Template (Top-Down Memoization)

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
    if is_base(state): return base_value(state)
    return combine(solve(next_state(state, c)) for c in choices(state))

Canonical Template (Bottom-Up Tabulation)

dp = init_table()
for state in topological_order_of_states():
    dp[state] = combine(dp[prev] for prev in predecessors(state))
return dp[final_state]

Complexity

Time = (# states) × (work per state). Space = (# states), often optimizable to a slice.

Common Variants (covered separately below)

• 1D DP (pattern 21).
• 2D DP (pattern 22).
• Knapsack (pattern 23).
• Subsequence DP (pattern 24).
• String DP (pattern 25).
• Bitmask / interval / digit / probability / tree (Phase 5).

Classic Problems

• LeetCode 70 — Climbing Stairs
• LeetCode 198 — House Robber
• LeetCode 322 — Coin Change
• LeetCode 416 — Partition Equal Subset Sum

Common Bugs

• Wrong state definition — too coarse to reconstruct, too fine to fit in memory.
• Wrong base case (off-by-one in the empty / single-element base).
• Wrong evaluation order in tabulation — predecessors computed after dependents.
• Memo key collisions when two different state tuples accidentally hash equal.

21. 1D DP (climbing stairs / house robber / decode ways)

Signal Recognition (<2 min)

• The state is a single index: “the answer at position i depends on positions ≤ i”.
• Transitions look at the last 1–3 positions.
• The answer is at dp[n] or dp[n-1].

Canonical Template

dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
    dp[i] = combine(dp[i - 1], dp[i - 2], a[i - 1])
return dp[n]

Complexity

Time O(N), space O(N) — usually compressible to O(1).

Common Variants

• Climbing stairs (Fibonacci-shaped).
• House robber / robber II (linear / circular).
• Decode ways (transitions depend on a 2-digit window).
• Maximum subarray (Kadane’s).
• Min cost climbing stairs.

Classic Problems

• LeetCode 53 — Maximum Subarray (Kadane’s)
• LeetCode 70 — Climbing Stairs
• LeetCode 91 — Decode Ways
• LeetCode 121 — Best Time to Buy and Sell Stock
• LeetCode 198 — House Robber
• LeetCode 213 — House Robber II
• LeetCode 264 — Ugly Number II
• LeetCode 746 — Min Cost Climbing Stairs

Common Bugs

• Off-by-one in the dp size (n vs n+1).
• Wrong base for empty input.
• Decode ways: forgetting that 0 is not a valid single-digit decoding.
• Compressing to O(1) but reading dp[i-2] after dp[i-1] is overwritten.

22. 2D DP (grid / unique paths / LCS preview)

Signal Recognition (<2 min)

• The state is a pair (i, j) — typically (row, col) or (index_in_A, index_in_B).
• Transitions look at neighboring cells: dp[i-1][j], dp[i][j-1], dp[i-1][j-1].
• Common shapes: grid path counting/min sum, LCS, edit distance, palindrome substring.

Canonical Template

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], a[i-1], b[j-1])
return dp[n][m]

Complexity

Time O(NM), space O(NM) — often compressible to O(min(N, M)) by keeping two rows.

Common Variants

• Grid DP: unique paths, min path sum, max path sum.
• Two-string DP: LCS, edit distance, regex matching, distinct subsequences (covered in 24/25).
• Matrix DP: maximal square, dungeon game.
• Backwards-traversal (start from (n, m)) when transitions need future state.

Classic Problems

• LeetCode 62 — Unique Paths
• LeetCode 64 — Minimum Path Sum
• LeetCode 72 — Edit Distance
• LeetCode 174 — Dungeon Game
• LeetCode 221 — Maximal Square
• LeetCode 1143 — Longest Common Subsequence

Common Bugs

• Initializing the first row/column wrong (not the additive identity for the operator).
• Allocating [[0] * m] * n in Python — all rows alias the same list (top-3 Python DP bug).
• 1D-compression bug: reading the new value when the old one was needed (or vice versa).
• For grids with obstacles: forgetting the obstacle ⇒ 0-paths-here invariant.

23. Knapsack (0/1 + unbounded)

Signal Recognition (<2 min)

• “Pick a subset of items to maximize value subject to a capacity constraint” (0/1 knapsack — each item once).
• “Pick items with repetition allowed” (unbounded knapsack — coin change min coins, integer break).
• “Number of ways to make sum K from given items” (counting variant).

Canonical Template (0/1 Knapsack — Compressed 1D)

dp = [0] * (W + 1)
for v, w in items:
    for c in range(W, w - 1, -1):  # reverse to avoid re-using item
        dp[c] = max(dp[c], dp[c - w] + v)

Canonical Template (Unbounded Knapsack)

dp = [0] * (W + 1)
for c in range(1, W + 1):  # forward, so each item can be reused
    for v, w in items:
        if c >= w: dp[c] = max(dp[c], dp[c - w] + v)

Complexity

Time O(N · W). Space O(W) (compressed) or O(N · W) (uncompressed).

Common Variants

• 0/1 vs unbounded vs bounded (limited copies of each item).
• Min coins, count-of-ways, can-we-make-this-sum.
• Subset sum (knapsack with value = weight).
• Partition equal subset sum (subset sum to total/2).

Classic Problems

• LeetCode 322 — Coin Change (unbounded, min)
• LeetCode 416 — Partition Equal Subset Sum (0/1, decision)
• LeetCode 474 — Ones and Zeroes (0/1 with two capacities)
• LeetCode 494 — Target Sum (count-of-ways)
• LeetCode 518 — Coin Change II (unbounded, count)
• LeetCode 879 — Profitable Schemes
• LeetCode 1049 — Last Stone Weight II

Common Bugs

• 0/1 with forward inner loop → double-counts items.
• Unbounded with reverse inner loop → behaves like 0/1.
• For “count of ways” with order-insensitive: outer is items, inner is capacity (LC 518). Order-sensitive: opposite (LC 377).
• Forgetting that dp[0] = 1 for count-of-ways, dp[0] = 0 for max-value.

24. Subsequence DP (LIS / LCS / edit distance)

Signal Recognition (<2 min)

• “Longest increasing / common / non-decreasing subsequence.”
• “Edit distance / minimum operations to transform A to B.”
• “Distinct subsequences / supersequences.”
• “Longest palindromic subsequence” (it’s LCS of s and s[::-1]).

Canonical Template (LIS, O(N log N))

import bisect
tails = []
for x in a:
    i = bisect.bisect_left(tails, x)  # bisect_right for non-decreasing
    if i == len(tails): tails.append(x)
    else: tails[i] = x
return len(tails)

Canonical Template (LCS / Edit Distance — 2D DP)

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1   # LCS
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Complexity

LIS: O(N log N) (patience-sort) or O(N²) (DP). LCS / edit distance: O(NM).

Common Variants

• LIS, longest non-decreasing, count of LIS, reconstruction.
• LCS, shortest common supersequence (N + M − LCS).
• Edit distance (Levenshtein), with weighted operations.
• Distinct subsequences (count occurrences of T as subsequence of S).
• Longest palindromic subsequence (= LCS of s and reversed s).

Classic Problems

• LeetCode 72 — Edit Distance
• LeetCode 115 — Distinct Subsequences
• LeetCode 300 — Longest Increasing Subsequence
• LeetCode 354 — Russian Doll Envelopes (LIS in 2D)
• LeetCode 516 — Longest Palindromic Subsequence
• LeetCode 583 — Delete Operation for Two Strings
• LeetCode 673 — Number of LIS
• LeetCode 1143 — Longest Common Subsequence

Common Bugs

• LIS with bisect_left vs bisect_right controls strict vs non-strict — pick the wrong one and ties are mishandled.
• Edit distance: forgetting that the base row/col is 0..n (i deletions / insertions to reach empty).
• Reconstruction: walking the dp table backward, easy to off-by-one.

25. String DP (palindrome / partitioning)

Signal Recognition (<2 min)

• “Longest palindromic substring / subsequence.”
• “Minimum cuts to partition into palindromes.”
• “Word break / segment string into dictionary words.”
• “Regex / wildcard matching.”

Canonical Template (Palindrome Substring DP)

n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n): dp[i][i] = True
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
            dp[i][j] = True

Complexity

Most string-DP problems: O(N²) time, O(N²) space (often compressible to O(N)). Manacher (Phase 3) gives O(N) for longest-palindrome.

Common Variants

• Longest palindromic substring (DP, expand-around-center, or Manacher).
• Longest palindromic subsequence (LCS-based).
• Minimum cuts (palindrome partitioning II).
• Word break (boolean DP) and word break II (recover all decompositions).
• Regex / wildcard matching (?, *, .).

Classic Problems

• LeetCode 5 — Longest Palindromic Substring
• LeetCode 10 — Regular Expression Matching
• LeetCode 44 — Wildcard Matching
• LeetCode 132 — Palindrome Partitioning II
• LeetCode 139 — Word Break
• LeetCode 140 — Word Break II
• LeetCode 516 — Longest Palindromic Subsequence
• LeetCode 647 — Palindromic Substrings

Common Bugs

• Iteration order: filling dp[i][j] requires dp[i+1][j-1] already filled — iterate by length, not by i then j.
• Word break: building all decompositions naively is O(2^N) — memoize, but be aware total output can still be exponential.
• Wildcard * matching empty vs many — both transitions needed.
• Off-by-one when j = i + length - 1.

26. Trie (prefix queries / autocomplete preview)

Signal Recognition (<2 min)

• “Many strings, prefix queries” — does any word start with X? Count words starting with X?
• Autocomplete / spell check.
• Word search II (LC 212) — combine trie with backtracking on a grid.
• Maximum XOR pair (LC 421) — bit-level trie.
• Replace words / dictionary lookup.

Canonical Template

class TrieNode:
    __slots__ = ('children', 'end')
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self): self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.end = True
    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end
    def starts_with(self, prefix):
        return self._walk(prefix) is not None
    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children: return None
            node = node.children[c]
        return node

Complexity

Insert / search / prefix: O(L) per operation. Space O(N · L) worst case (no shared prefixes).

Common Variants

• Character trie (by char).
• Bit trie (by bit) — for XOR / Hamming-distance problems.
• Compressed (radix) trie — Phase 3.
• Trie + DFS for “all words on a board” (LC 212) — early-prune by failing nodes.
• Suffix trie / suffix automaton — Phase 3 / Phase 12.

Classic Problems

• LeetCode 208 — Implement Trie (Prefix Tree)
• LeetCode 211 — Design Add and Search Words Data Structure
• LeetCode 212 — Word Search II
• LeetCode 336 — Palindrome Pairs
• LeetCode 421 — Maximum XOR of Two Numbers in an Array (bit trie)
• LeetCode 648 — Replace Words
• LeetCode 677 — Map Sum Pairs
• LeetCode 1268 — Search Suggestions System

Common Bugs

• Forgetting the end flag (or whatever marks a complete word) — search("app") returns true when only "apple" was inserted.
• Using a 26-element array vs a hashmap — array is faster but only for fixed alphabets.
• Iterating node.children mistakenly using insertion order assumptions.
• For LC 212, not pruning nodes after they’ve been used (still works correctly but wastes time).

27. Heap Top-K (k-largest / k-frequent / k-closest)

Signal Recognition (<2 min)

• “Find the K largest / smallest / most frequent / closest.”
• Online/streaming K-th element.
• Median maintenance (two heaps).
• “Merge K sorted streams” (pattern 28 — see below).

Canonical Template (Top-K with Min-Heap of Size K)

import heapq
heap = []
for x in stream:
    if len(heap) < K:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)
return heap  # K largest, unsorted

Complexity

Time O(N log K). Space O(K). Compare to full sort O(N log N) — beats it when K << N.

Common Variants

• Top K largest / smallest.
• Top K frequent — bucket sort gives O(N) when frequencies fit (LC 347).
• K closest points to origin — heap of K by distance.
• Median from data stream — two heaps (max-heap of low half, min-heap of high half).
• K-th smallest in matrix / K-th smallest in BST — heap or controlled traversal.

Classic Problems

• LeetCode 215 — Kth Largest Element in an Array
• LeetCode 295 — Find Median from Data Stream
• LeetCode 347 — Top K Frequent Elements
• LeetCode 451 — Sort Characters by Frequency
• LeetCode 692 — Top K Frequent Words
• LeetCode 703 — Kth Largest Element in a Stream
• LeetCode 973 — K Closest Points to Origin
• LeetCode 1046 — Last Stone Weight

Common Bugs

• Using a max-heap for top-K-largest — wrong; use a min-heap of size K (we evict the smallest).
• Java PriorityQueue is min-heap by default; use Comparator.reverseOrder() for max.
• Python heapq is min-heap only; negate values for max-heap.
• For “top K frequent words” with tie-breaking (alphabetical) — comparator gets tricky in Java/Python.

28. K-Way Merge (merge K lists / smallest range covering K lists)

Signal Recognition (<2 min)

• K sorted lists/streams; merge them into one sorted output.
• “Find the smallest range that contains at least one element from each of K lists.”
• “Find the K-th smallest in K sorted lists / matrix.”
• External-merge / external-sort flavor.

Canonical Template (Merge K Sorted Lists)

import heapq
heap = []
for i, lst in enumerate(lists):
    if lst: heapq.heappush(heap, (lst[0].val, i, lst[0]))
dummy = ListNode(0); tail = dummy
while heap:
    val, i, node = heapq.heappop(heap)
    tail.next = node; tail = tail.next
    if node.next:
        heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next

Complexity

Time O(N log K) where N is the total number of elements. Space O(K) for the heap.

Common Variants

• Merge K sorted lists / arrays / streams.
• Smallest range covering at least one from each list — heap holds one element per list, track current max; pop the min and advance the popped list.
• K-th smallest in sorted matrix — heap of (value, row, col); pop, push next-in-row (or use binary search on answer instead).
• Find smallest pair sums (LC 373) — heap from two sorted lists.
• Skyline problem (LC 218) — sweep over events with a heap of active heights.

Classic Problems

• LeetCode 23 — Merge K Sorted Lists
• LeetCode 218 — The Skyline Problem
• LeetCode 264 — Ugly Number II
• LeetCode 313 — Super Ugly Number
• LeetCode 373 — Find K Pairs with Smallest Sums
• LeetCode 378 — Kth Smallest Element in a Sorted Matrix
• LeetCode 632 — Smallest Range Covering Elements from K Lists
• LeetCode 1675 — Minimize Deviation in Array

Common Bugs

• Heap items must include a tiebreaker — comparing ListNode directly raises TypeError in Python.
• Forgetting to push the next element in the same list after popping.
• For “smallest range”: confusing max so far (cheap to maintain) with re-scanning the heap (O(K)).
• Off-by-one when one list is exhausted before others.

Pattern Recognition Cheat Sheet (Signal → Pattern)

This is the table you should be able to traverse, top-to-bottom, in <60 seconds for any new Medium.

When two patterns plausibly fit, try both signals on a small example. Often one fits cleanly and the other forces awkward special cases.

Mastery Checklist For This Phase

You are ready to leave Phase 2 when, for every one of the 28 patterns:

• You can recognize the signal in <2 minutes on a fresh Medium.
• You can write the canonical template from memory in <5 minutes, without lookup.
• You can articulate the time/space complexity precisely, including amortized vs worst case.
• You can name 4+ classic LeetCode problems where this pattern is the intended solution.
• You can list at least 2 common bugs that the pattern is famous for.
• You have solved at least 5 problems applying this pattern, with at least 2 reviewed via REVIEW_TEMPLATE.md.

And, more generally:

• You can produce the cheat-sheet table above from scratch (or close to it) on a whiteboard.
• You can name, given a signal, the most likely pattern plus the second-most-likely (because tricky problems disguise themselves).
• You can combine two patterns when one alone is insufficient (e.g., monotonic deque inside sliding window for LC 862; trie inside backtracking for LC 212).
• You have run mock interviews on Mediums and your time-to-recognize is reliably under 2 minutes.

Required Problem Volume

The patterns are not learned from this README. They are learned from solving lots of problems per pattern and reviewing each via REVIEW_TEMPLATE.md, then revisiting via SPACED_REPETITION.md.

Recommended minimums for Phase 2 completion (per pattern):

• 5–8 Medium problems that explicitly use the pattern as their intended solution.
• 2 mock-interview Mediums where the pattern is not hinted (you must recognize it).
• 1 problem at the boundary where two patterns plausibly apply — pick one, justify, solve.

Total over the phase: ~150–200 Mediums. This is the cost. The benefit is that, after Phase 2, almost every Medium becomes a 5-minute problem.

Exit Criteria

You may move to Phase 3 — Advanced Data Structures when:

1. You score ≥ 75% on a 10-problem random-Medium mock (35 min each, no hints, no lookup), with the pattern recognition and template write-up completed in the first 5 minutes of each problem.
2. You can pass the READINESS_CHECKLIST.md entries for “pattern recognition” without lookup.
3. You have completed all 9 labs in labs/ with the format-required deliverables.
4. You have at least 40 problems in your spaced-repetition queue from this phase, with first reviews passed.

If your unaided solve rate on random Mediums is below 75%, do not advance. Spend another 1–2 weeks at this level, focusing on the patterns where you missed. The patterns calcify here. Calcify wrong patterns and Phase 3+ becomes a fight against your own intuition.

How This Phase Connects To The Rest

• Phase 0 / Phase 1 are prerequisites. You cannot recognize patterns if you cannot read the problem and you do not know the data structures.
• Phase 3 (Advanced DS) generalizes patterns 9, 10, 18, 26, 27, 28 with segment trees, BITs, balanced BSTs, suffix arrays.
• Phase 4 (Graphs) generalizes patterns 15, 16, 17, 18 with Dijkstra, Bellman-Ford, SCC, max flow.
• Phase 5 (DP) generalizes patterns 20–25 with bitmask, interval, tree, digit, probability DP.
• Phase 6 (Greedy) formalizes the proof techniques behind pattern 6 (sort + greedy).
• Phase 9 (Language/Runtime) drills the language-specific footguns called out in each pattern’s “Common Bugs”.

You will return to this README dozens of times over the rest of the curriculum — each return faster than the last, until eventually the patterns are no longer something you look up but something you simply see.