DSA Pattern Lab▍

§◇ · YOUR DESK

Today

Due for re-solve

jump to the practice ladder → · drill the flashcards →

§00 · THE FULL MAP — FAANG COVERAGE

Pattern atlas — every pattern, one table

~20 patterns cover 85–90% of what Meta, Google, Amazon and Apple actually ask, and the marginal return curve is brutal: the first 15 are worth more than the next 30. This table is the whole territory — each pattern named by the redundancy it kills, with the Set of this lab that will cover it. Learn top to bottom.

S = daily bread, learn first  ·  A = separates offers from rejections  ·  B = strong-hire / senior depth (Google-weighted)

§★ · A FRESH PROBLEM WALKS IN

The decision tree — route first, then verify

The atlas lists the patterns; this routes you to one. Ask these questions in this order — the first hit wins, and more-specific beats more-general. After routing, verify the chosen set's hidden requirement (every theory section names one) before writing a line.

§★ · THE OTHER HALF OF THE INTERVIEW

Speaking the solution

Interviewers grade the narration as much as the code. This is the script the whole lab has been feeding in fragments, consolidated. Practice it out loud on every ladder problem.

1. Restate + clarify — repeat the problem in one sentence, then ask the questions that change the design: duplicates allowed? negatives? sorted? may I mutate the input? ties — how broken? what's returned for empty input?
2. Read the constraints out loud — "n up to 10⁵, so I need O(n log n) or better" (§F.5). The setter is telling you the intended pattern.
3. Brute force first, in words — state it, state its complexity, and name the redundant work it repeats. This is the master framework (§0) performed live; it is also what earns you partial credit if time runs out.
4. Route to a pattern — say the signal that triggered it ("count subarrays with exact sum — that's prefix + hashmap") and check the hidden requirement out loud.
5. State the invariant before coding — one sentence ("after the while-loop, [left..right] is the largest valid window ending at right"). Then every line you write has a justification.
6. Narrate decisions, not syntax — say "check before insert so an element can't pair with itself", not "now I write a for loop".
7. Test like a ritual — trace the smallest non-trivial input by hand, then the edges: empty, single element, all-duplicates, negatives, the exact boundary (k = 0, capacity 1). Then run the relevant set's trap checklist.
8. Close with complexity, precisely — the adjectives are the senior signal: average for hash ops, amortized for stacks/queues/resizes, expected for quickselect, pseudo-polynomial for value-bounded DP, output-sensitive when the answer itself is big.

§F.1 · SET 00 — FOUNDATIONS · READ THIS SET FIRST

Big-O from zero

Before any pattern in this lab makes sense, you need one skill: looking at code and predicting how much slower it gets as the input grows. That is the whole of Big-O. It is not advanced math — it is counting, plus one honest observation about growth.

Start with a picture you already know. Two ways to find a name in a phone book: flip page by page, or open the middle and throw away the wrong half each time. For a 20-page book, both feel instant. For a million pages, page-by-page takes days and halving takes about 20 flips. Same task, wildly different growth — and Big-O is just the label we put on each behaviour: page-by-page grows like n (we write O(n)); halving grows like log n (we write O(log n)).

What we actually do: pick the operation the code repeats (a comparison, an addition, a visit) and count how many times it runs as a formula in n, the input size. We deliberately ignore two things: how fast the computer is, and small constant factors — because neither changes the shape of the growth, and the shape is what decides whether your solution survives a big input.

One anchor number makes all of this concrete: a computer runs very roughly 100 million to 1 billion simple steps per second. So a step-count converts straight into seconds:

The four counting rules. Every complexity claim in this lab is built from just these:

1. Steps in sequence add. Two separate loops over n = 2n steps. We still call it O(n), because 2n and n have the same shape — doubling a computer’s speed also halves the constant, and neither rescues a bad shape. That is why dropping constants is honest, not sloppy.
2. A loop inside a loop multiplies. For each of n items, scan all n items → n × n = n². This is where most accidental slowness comes from.
3. Halving means log. If each step cuts the remaining problem in half, 1,000,000 shrinks to 1 in about 20 steps. Whenever you spot halving, say “log”. (Set 04 is built entirely on this rule.)
4. “Amortized” means: average it over the whole run. Sometimes one step is expensive but the total across all steps is provably small — so the average per step is small. The tell that this is happening: something that only ever moves in one direction. It sounds abstract now; §2.2 makes it concrete, and you will then meet the same argument seven more times.

Space is counted the same way — but for memory, and only the extra memory beyond the input itself: two index variables = O(1); a copy of the array = O(n); a recursion n levels deep = O(n) of hidden stack memory (next section shows why).

§F.2 · SET 00 — FOUNDATIONS

Recursion — what the computer actually does

A recursive function is simply a function that calls itself. The definition is never the hard part. The hard part is that beginners try to hold every in-flight call in their head at once — and that feels like vertigo. The fix is to see the simple machinery underneath, then learn the professional trick for never needing to trace it at all.

The machinery: a pile of sticky notes. Every function call gets its own sticky note (the technical name is a stack frame) holding its own copies of the parameters and local variables. Calling a function puts a new note on top of the pile. Returning throws the top note away, and the note underneath resumes exactly where it paused. That’s all recursion is: the same rule, applied to a function calling itself.

def fact(n):
    if n == 0:          # base case — the floor that stops the descent
        return 1
    return n * fact(n - 1)

the same picture as text:
  fact(3) waits for fact(2)·        stack: [fact(3)]
    fact(2) waits for fact(1)·      stack: [fact(3), fact(2)]
      fact(1) waits for fact(0)·    stack: [fact(3), fact(2), fact(1)]
        fact(0) returns 1           — the stack now unwinds —
      fact(1) resumes: 1·1 = 1
    fact(2) resumes: 2·1 = 2
  fact(3) resumes: 3·2 = 6

The professional trick: never trace big inputs. Instead, do three small checks:

1. Write one sentence saying what the function promises: “fact(n) returns n!”.
2. Check the smallest case keeps the promise: fact(0) = 1 ✓.
3. Check the general step keeps the promise assuming the smaller call already does: if fact(n−1) really is (n−1)!, then n · fact(n−1) = n! ✓.

That assumption in step 3 feels like cheating; it isn’t — it is mathematical induction, and it is exactly how the pros stay calm. Set 06 will name this habit “trust the recursion”, and interviewers actively watch for it: tracing into a recursive call signals doubt; stating the promise and checking the step signals command.

§F.3 · SET 00 — FOUNDATIONS

Hash tables — the library-shelf trick

Half the lab says “use a hashmap, O(1) average”. Here is what those words actually mean, because you will be asked.

The problem it solves: finding one book in an unsorted pile means checking every book — O(n) per search. A library fixes this without sorting anything: it computes each book’s shelf from its title. To find a book you redo that small computation and walk straight to the right shelf. No scanning.

A hash table is exactly that library. The hash function turns your key into a shelf number; the shelf is called a bucket. Two keys can land on the same shelf — a collision — and that is fine: the shelf just holds a short list you check quickly. When shelves get crowded, the table quietly rebuilds itself bigger (a resize) — occasionally expensive, cheap on average, which is rule 4 of §F.1 (amortized) making its first real appearance.

Why every bound says “average”: a truly unlucky (or malicious) set of keys could all land on one shelf — then that shelf IS the unsorted pile again, and lookups degrade to O(n). Real inputs almost never do this, but the precise claim — the one to say in interviews — is “O(1) average, O(n) worst case”.

Why keys must be immutable: the shelf was chosen from the key’s value at insert time. If you could change the key afterwards, the book would be filed under a shelf its new title no longer points to — lost forever. That is why Python accepts strings, numbers and tuples as keys, and refuses lists (you will hit this personally in §B.3).

That first row is the most common beginner performance bug in existence: if x in my_list inside a loop is a hidden n×n (rule 2 of §F.1) — the code is correct, passes small tests, and times out at scale. Building a set first fixes it with one line.

§F.4 · SET 00 — FOUNDATIONS

The Python this lab is written in

The lab’s code uses a handful of Python moves that read like magic until someone slows them down. Here they are, slowed down.

1. Tuple assignment — the move the linked-list set lives on. The rule is simple: Python finishes reading the ENTIRE right-hand side before it changes anything on the left. So this famous one-liner:

cur.next, prev, cur = prev, cur, cur.next
# is exactly this, with the temp written out:
old_next = cur.next     # the right side was captured FIRST
cur.next = prev
prev = cur
cur = old_next

Nothing is lost, because everything on the right was safely read before anything on the left changed. In Java or JavaScript you must write that temp yourself — and writing the three statements in the wrong order there is the classic lost-list bug (§L.2 shows the wreckage).

2. Two names, one list — the aliasing trap. Assignment in Python copies the arrow, never the object. b = a gives you two names for one list; change it through either name and both “see” the change, because there is only one list to see. A real copy needs a[:].

3. The rest of the vocabulary — skim now, return whenever a code block uses one:

§F.5 · SET 00 — FOUNDATIONS

Reading constraints — the setter is talking to you

Every problem statement ends with limits like “n ≤ 100,000”. Beginners skim past them. Don’t — the limits quietly tell you which solution the author expects, and reading them takes ten seconds.

The arithmetic behind it, once: your time budget is roughly 10⁸ steps (§F.1’s anchor number). An O(n²) idea at n = 100,000 costs 10¹⁰ steps — about 100 seconds — automatic rejection. So the largest allowed n filters the curves of §F.1’s chart down to the ones that fit the budget, and the biggest surviving shape is almost always the intended one:

Two more messages hiding in constraints:

• A tiny n combined with “return ALL…” means the answer itself is huge (2ⁿ subsets, n! orderings) — no algorithm can beat the size of its own output, so exponential is not a failure there, it’s the job (§K.1).
• A guarantee like “timestamps are strictly increasing” is a gift: it is sortedness you didn’t have to pay for, and the intended solution exploits it (§V.4 is built on exactly this).

Habit to build from day one: read the constraints before thinking about approaches, and say the budget out loud — “n is 10⁵, so I need O(n log n) or better.” It steers you toward the right pattern and it is, verbatim, step 2 of the interview script (§guide-talk).

§0 · READ THIS FIRST

The master framework

Every optimization pattern exists to kill a specific redundancy in the brute force. The workflow for any problem:

1. Write the brute force (in comments, not code)
2. State its complexity
3. Name the redundant work it repeats
4. Pick the tool that eliminates exactly that redundancy

For this pair of patterns:

§B.1 · BASELINE — ARRAYS & HASHING

Theory

Redundancy it kills: answering "have I seen X?" by re-scanning costs O(n) per question. Ask it n times — once per element — and you have the O(n²) hiding inside most brute forces in this family. A hash table answers the same question in O(1) average, buying speed with O(n) space.

Mechanics you must be able to say out loud: a hash function maps each key to a bucket; resizing keeps the load factor bounded, so inserts are amortized O(1); collisions are why every bound says average — adversarial keys degrade a bucket to O(n). Same honest footnote as LC 560's map in §1.4 — in interviews, "O(1) average" is precision, not hedging.

The three payloads. Everything in this set is one data structure with three choices of value:

• set → pure existence ("seen it?")
• dict value = count → frequency
• dict value = index / list → location or grouping

The question that picks the payload is the same one that picked the map value in prefix-sum Types C/D/E: "what do I need to know about earlier elements?" That answer is your value type.

§B.2 · TYPE A

Complement lookup

Easy-tier, included on purpose: it is the archetype — reportedly the most-asked interview question in existence — and its one-pass shape is the seed of half this set.

Brute force: every pair → O(n²).

Redundancy: for a fixed x, the inner loop re-scans for target − x among elements the outer loop already walked past.

Insight: walk once, storing value → index. Before inserting x, ask whether its complement is already in the map. Check before insert — the same ordering discipline as LC 560 — or target = 2x lets an element pair with itself.

def twoSum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:         # check FIRST — self-pair guard
            return [seen[target - x], i]
        seen[x] = i

§B.3 · TYPE B

Canonical-key grouping

Brute force: pairwise anagram checks → O(n²·k) for n words of length k.

Redundancy: group membership is a property of each string alone; comparing pairs recomputes that property endlessly.

Insight: map every item to a canonical form — chosen so that equal canonical form ⟺ same group — and bucket by it. Two candidate keys here: the sorted string (O(k log k) per word) or a 26-slot count tuple (O(k) per word).

def groupAnagrams(strs):
    groups = {}
    for s in strs:
        key = [0] * 26                     # canonical form: char counts
        for ch in s:
            key[ord(ch) - 97] += 1
        groups.setdefault(tuple(key), []).append(s)
    return list(groups.values())

§B.4 · TYPE C

Frequency + buckets

Brute force: count, then sort pairs by count → O(n log n).

Redundancy: a full ordering when only the top k matters.

The escalation ladder (know all three rungs): sort O(n log n) → size-k heap O(n log k) → buckets O(n). The bucket insight: a frequency is an integer in [1..n] — a bounded integer domain is bucket sort's invitation. Index an array by the frequency itself.

def topKFrequent(nums, k):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for x, c in freq.items():
        buckets[c].append(x)
    res = []
    for c in range(len(nums), 0, -1):              # harvest high to low
        for x in buckets[c]:
            res.append(x)
            if len(res) == k:
                return res

§B.5 · TYPE D

Sequence starts from a set

Brute force: for each x, scan the array for x+1, then x+2, … → O(n²) and worse. Sorting gives O(n log n) — correct, but the problem dares you to beat it.

Insight: pour everything into a set, then only begin counting from sequence starts — elements x where x − 1 is absent. Every walk then covers its sequence exactly once.

def longestConsecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:            # only sequence STARTS start a walk
            streak = 1
            while x + streak in s:
                streak += 1
            best = max(best, streak)
    return best

§B.6 · TYPE E

Running products

Brute force: per-index product of the others → O(n²).

Redundancy: neighboring answers share almost all their factors — overlapping products, the multiplicative sibling of Set 01's overlapping range sums.

Insight: answer[i] = (product left of i) × (product right of i). One prefix sweep, one suffix sweep, both accumulated into the output array → O(1) extra space.

Why division is banned: one zero makes total ÷ nums[i] meaningless everywhere except at the zero; two zeros zero out everything. The sweeps handle both cases with no case analysis at all.

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):                 # res[i] = product of nums[0..i-1]
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):     # fold in product of nums[i+1..]
        res[i] *= suffix
        suffix *= nums[i]
    return res

§B.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Inserted before checking → Two Sum returns the same index twice when target = 2·nums[i]
• Canonical key built from a list → unhashable; tuples/strings only
• Cited O(n) while calling most_common() or sorting inside the loop
• Missing start-check in LC 128 → correct answers, quiet O(n²)
• Division shortcut in LC 238 → one-zero and two-zero inputs break it differently
• Asked a hashmap a range/nearest/≤ question — it only answers exact equality
• Claimed O(1) worst-case for hash ops — it's average; say so

Signals → pattern (added to the drill deck in §3.2)

"have I seen X / does my complement exist"  → hashset or map, check BEFORE insert
"group items by a shared property"          → canonical key → map of lists
"top k frequent"                            → counts + buckets (freq ≤ n) or size-k heap
"longest run of consecutive VALUES"         → set + expand only from starts
"product/sum of everything except me"       → prefix sweep × suffix sweep

Interrogation — answer in your journal

§1.1 · PART 1 — PREFIX SUM

Theory

Definition: prefix[i] = sum of the first i elements, with prefix[0] = 0 (the "empty prefix").

nums   =      [3,  1,  4,  2,  5,  1]
prefix = [0,  3,  4,  8,  10, 15, 16]

Build: prefix[i+1] = prefix[i] + nums[i] — one pass.

The core identity (this is the entire pattern):

sum(l..r) = prefix[r+1] − prefix[l]

Why it works: prefix[r+1] contains everything up to r; prefix[l] contains exactly the unwanted part before l. Subtracting cancels the unwanted part. A range question becomes a difference of two point values. Every prefix-sum problem is this reframing wearing a costume.

§1.2 · TYPE A

Range queries on an immutable array

Brute force: loop l..r per query → O(n) per query, O(n·q) total for q queries.

Redundancy: queries (2,4) and (2,5) share almost all their additions.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sumRange(self, l, r):
        return self.prefix[r + 1] - self.prefix[l]

§1.3 · TYPE B

Left part vs right part (pivot)

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, x in enumerate(nums):
        if left_sum == total - left_sum - x:
            return i
        left_sum += x
    return -1

§1.4 · TYPE C · THE WORKHORSE

Count subarrays with sum exactly k (prefix + hashmap)

This is the workhorse of prefix-sum mediums. Understand it deeply.

Derivation — never memorize this, re-derive it

Subarray (i..j) has sum k
⟺ prefix[j+1] − prefix[i] = k
⟺ prefix[i] = prefix[j+1] − k

So walk left to right and ask at every position: "how many EARLIER prefixes equal my current prefix minus k?" A hashmap {prefix value → times seen} answers in O(1). No window, no grow/shrink decision — just pair counting.

def subarraySum(nums, k):
    count, prefix = 0, 0
    seen = {0: 1}                              # the empty prefix
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)       # check FIRST
        seen[prefix] = seen.get(prefix, 0) + 1 # THEN insert
    return count

Worked trace — step through it

nums = [3, 4, −7, 1, 3], k = 4. Prefixes: 0, 3, 7, 0, 1, 4. Predict each step before advancing.

Answer: 3 → subarrays [4], [1,3], and the whole array.

Three load-bearing details

1. Why {0: 1}? It's the prefix before any element. Without it, no subarray starting at index 0 can ever pair up. In the trace, dropping it changes the answer from 3 to 2 (the whole-array match vanishes).
2. Why counts, not booleans/indices? Negatives make the prefix dip back to values it already visited (the −7 drags it back to 0). Step 5 finds prefix 0 twice — both matches are real subarrays. A boolean would lose one.
3. Why check BEFORE inserting? Swap the lines and run with k = 0: every position finds itself and counts a zero-length subarray. The ordering enforces "strictly earlier prefixes only" (the i < j+1 in the math). Note this bug only appears for one specific k — a passing test case would have fooled you.

§1.5 · TYPE D

Sum divisible by k (store remainders)

Derivation: sum(i..j) divisible by k ⟺ prefix[j+1] % k == prefix[i] % k (equal remainders subtract to a multiple of k). So store remainder counts instead of prefix counts; every pair of equal remainders is one valid subarray.

def subarraysDivByK(nums, k):
    count, prefix = 0, 0
    seen = {0: 1}
    for x in nums:
        prefix += x
        r = prefix % k          # Python: always non-negative
        count += seen.get(r, 0)
        seen[r] = seen.get(r, 0) + 1
    return count

const r = ((prefix % k) + k) % k;

§1.6 · TYPE E

LONGEST subarray with sum k (store earliest index)

What changes vs 560: the question changed from count to longest, so what you store changes from counts to the earliest index of each prefix value — and you never overwrite it (an earlier index always gives a longer subarray).

def maxSubArrayLen(nums, k):
    first = {0: -1}      # prefix 0 occurs "before index 0"
    prefix, best = 0, 0
    for i, x in enumerate(nums):
        prefix += x
        if prefix - k in first:
            best = max(best, i - first[prefix - k])
        if prefix not in first:      # keep only the EARLIEST
            first[prefix] = i
    return best

§1.7 · TYPE F

Transform then prefix (disguised problems)

§2.1 · PART 2 — SLIDING WINDOW

Theory

Redundancy it kills: consecutive subarrays share almost all elements; brute force re-evaluates each from scratch (O(n²) or O(n³)).

The fix: maintain ONE window [left..right] with running state (a sum, a frequency map, a distinct-count). Extend right by adding one element's contribution; shrink left by removing one element's contribution. Never recompute.

The variable-window skeleton (memorize the shape, derive the rest):

left = 0
for right in range(n):
    # 1. add nums[right] into window state
    while window_is_invalid():
        # 2. remove nums[left] from state
        left += 1
    # 3. window [left..right] is now the largest valid window
    #    ending at right → record answer here

§2.2 · THE AMORTIZED ARGUMENT

Why sliding window is O(n)

This looks like a nested loop, so why isn't it O(n²)?

Wrong way to analyze: "outer loop n times × inner loop up to n times = O(n²)." This overcounts because the inner loop's work is shared across iterations, not repeated per iteration.

Right way — count total pointer movements across the ENTIRE run:

• right only moves forward: exactly n steps total.
• left only moves forward and never passes right: at most n steps total summed over all iterations of the while-loop combined.
• Total work ≤ 2n pointer movements, each with O(1) state updates → O(n).

Equivalent framing (charging argument): every element enters the window exactly once and leaves at most once. Charge each element 2 units of work. n elements × 2 = O(n).

§2.3 · TYPE A

Fixed-size window

Brute force: sum every length-k window from scratch → O(n·k).

Redundancy: window starting at i+1 shares k−1 elements with window at i.

Fix: add the entering element, subtract the leaving one — O(1) per slide.

def findMaxAverage(nums, k):
    window = sum(nums[:k])          # first window: k additions
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # enter right, leave left
        best = max(best, window)
    return best / k

§2.4 · TYPE B

Variable window, LONGEST valid

Brute force: check every substring for duplicates → O(n³) (n² substrings × n scan). Even with a set per start index: O(n²).

Redundancy: on finding a duplicate, brute force restarts; the window instead slides past the earlier occurrence and keeps everything else.

def lengthOfLongestSubstring(s):
    freq = {}
    left = best = 0
    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        while freq[ch] > 1:              # invalid: a duplicate exists
            freq[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

§2.5 · TYPE C

Variable window, SHORTEST valid

What flips vs Type B: for "longest", you shrink while INVALID and record after. For "shortest", you shrink while VALID (trying to make it smaller) and record inside the shrink loop:

def minSubArrayLen(target, nums):
    left, window = 0, 0
    best = float('inf')
    for right, x in enumerate(nums):
        window += x
        while window >= target:                 # valid → try to shrink
            best = min(best, right - left + 1)  # record INSIDE
            window -= nums[left]
            left += 1
    return best if best != float('inf') else 0

§2.6 · TYPE D

Window with a budget

def longestOnes(nums, k):
    left = zeros = best = 0
    for right, x in enumerate(nums):
        zeros += (x == 0)
        while zeros > k:                # over budget → shrink
            zeros -= (nums[left] == 0)
            left += 1
        best = max(best, right - left + 1)
    return best

Same family (do after): LC 424 (state = window length − count of most frequent char), LC 904 (at most 2 distinct), LC 76 (must contain all chars of t — the hard one; state = how many required chars are satisfied).

§3.1 · PART 3 — DECISION GUIDE

Window vs prefix — the decision test

§3.2 · SIGNAL → PATTERN

Signal drill — flashcards

These lines seed your cheat sheet. Drill them: read the signal, say the pattern out loud, then flip. Missed cards come back at the end of the pass.

§3.3 · GENERAL METHOD

How to calculate complexity

1. Count the dominant operation as a function of n — loop iterations × work per iteration. Nested independent loops multiply (n × n = n²).
2. BUT check for shared/amortized work first: if an inner loop's variable only moves in one direction across the whole run (sliding window's left, a stack that pops each element once), sum its TOTAL work over all iterations instead of multiplying. That's how a "nested" loop can be O(n).
3. Hashmap get/set = O(1) average. Say "average" — it's the precise claim.
4. Drop constants and lower-order terms: 2n → O(n); n + k → O(n + k) unless one dominates; k + (n−k) → O(n).
5. Space = extra memory beyond the input: prefix array O(n); a window's char-frequency map O(min(n, charset)); two pointers O(1).
6. Sanity-check against constraints: n ≤ 10⁵ → you need O(n) or O(n log n); an O(n²) idea (10¹⁰ ops) will TLE. Reading constraints FIRST often tells you which pattern is expected — that's a legitimate recognition signal, use it.

§3.4 · BEFORE YOU SUBMIT

Common bugs checklist

Run through this before every submit. Ticks are per-visit, on purpose — they reset on reload.

• Forgot {0: 1} seed → subarrays starting at index 0 uncounted
• Inserted into map before checking → self-match bug when k = 0
• Stored boolean/last-index instead of count/earliest-index for the variant at hand
• Negative % in JS/Java → normalize ((x % k) + k) % k
• Used sum-based sliding window with negatives present → wrong answers, not errors
• "Longest": recorded inside shrink loop (should be after). "Shortest": recorded after (should be inside)
• Off-by-one: window length is right − left + 1, range sum is prefix[r+1] − prefix[l]
• Moved left by fixed +1 when a jump was available/required (LC 3 optimized variant)

§T.1 · SET 02 — TWO POINTERS

Theory

Redundancy it kills: examining all O(n²) pairs when structure — sortedness, geometry, an exchange argument — lets you prove that whole blocks of pairs cannot contain the answer. Each pointer move permanently discards candidates. The loop is trivial; the discard proof is the pattern.

Three archetypes:

• Converging — both ends move inward: pair search, partitioning, geometric arguments (this set).
• Reader / writer — same direction, in-place compaction and partitioning (Type D).
• Fast / slow — cycle detection and middles; arrives with linked lists in Set 05.

Complexity: each pointer moves in one direction only, ≤ 2n total moves with O(1) work each → O(n) after any sort. The same one-direction tell from §2.2 — third time it has appeared.

§T.2 · TYPE A

Converging pair search

Brute force: O(n²) pairs. A hashmap gives O(n) time but O(n) space and ignores the gift of sortedness — the follow-up demands O(1) space.

The discard proof, spelled out: if nums[l] + nums[r] < target, then nums[l] paired with any r′ < r is smaller still — r was already nums[l]'s largest available partner. Every remaining pair involving l is dead; l += 1 discards them all at once. Mirror argument when the sum is too big.

def twoSumSorted(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]      # this problem is 1-indexed
        if s < target:
            l += 1                     # l's largest partner failed: l is done
        else:
            r -= 1                     # r's smallest partner failed: r is done

§T.3 · TYPE B

Fix one, converge the rest

Brute force: O(n³) triples.

Insight: sort, fix nums[i], and the rest is exactly Type A with target −nums[i]. n fixings × O(n) converge = O(n²); the O(n log n) sort is free relative to that.

Dedup at every level — and it's the sort that makes dedup possible, because equal values become adjacent: skip a repeated i; after each hit, skip repeated l values and repeated r values.

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break                      # smallest remaining is positive: done
        if i > 0 and nums[i] == nums[i - 1]:
            continue                   # dedup the fixed element
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1             # dedup the left element
                r -= 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1             # dedup the right element
    return res

§T.4 · TYPE C

The exchange argument

Brute force: O(n²) pairs. Area of a pair: (r − l) × min(h[l], h[r]).

The discard proof: always move the shorter wall. Keeping the shorter wall (say h[l] ≤ h[r]) while bringing the other end inward can never win: the width strictly shrinks and the height stays capped at h[l]. Every pair keeping l is therefore ≤ the area just measured — the entire row of candidates dies, l += 1.

def maxArea(height):
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        best = max(best, (r - l) * min(height[l], height[r]))
        if height[l] < height[r]:
            l += 1                     # shorter wall is the limit — move it
        else:
            r -= 1
    return best

§T.5 · TYPE D

Three-way partition (Dutch national flag)

Two-pass counting sort is fine engineering — the one-pass invariant dance is what's being interviewed.

Write the invariant as a comment before any code — every branch is then forced:

[0 .. low−1]   all 0s
[low .. mid−1] all 1s
[mid .. high]  unknown — mid scans this
(high .. end]  all 2s

• see 0 → swap(low, mid), advance both — the swapped-in value came from the 1s zone, already examined
• see 1 → mid++
• see 2 → swap(mid, high), high−− and do not advance mid — the swapped-in value is unexamined

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    # [0..low-1]=0s [low..mid-1]=1s [mid..high]=unknown (high..]=2s
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1                   # incoming value was an examined 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                  # do NOT advance mid — new value unexamined

§T.6 · TYPE E · THE BOSS

Two ends with carried state

The physics first: water above bar i = min(maxLeft(i), maxRight(i)) − h[i], floored at 0. Every solution is a strategy for knowing those two maxes.

The solution ladder (walk it in this order):

1. Brute: scan left and right per bar → O(n²).
2. DP: precompute maxLeft[] and maxRight[] arrays → O(n) time, O(n) space.
3. Two pointers: O(n) time, O(1) space — carry the maxes.

The information-sufficiency proof: in the h[l] < h[r] branch, l only ever advanced past walls that some then-current right wall exceeded — so the right side always still holds a wall ≥ every left wall seen. Hence min(maxLeft, maxRight) = left_max at l: the water there is decided by information we already have, and can be settled final. Symmetric for the other branch.

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]   # bounded by left_max — final
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

§T.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Moved a pointer without a discard proof — silently wrong answers, not errors
• Sorted when the answer needs original indices (Two Sum I) — that's the hashmap's job; sort only when answers are values (3Sum)
• 3Sum dedup only at i — l/r duplicates leak ([−2, 0, 0, 2, 2])
• Dutch flag: advanced mid after the high swap ([1, 2, 0] breaks)
• Wrong loop bound: pairs exclude l == r (strict <); partitions include it (mid ≤ high)
• Decision needed info about elements BETWEEN the pointers — that's a sliding window, switch tools

Signals → pattern (added to the drill deck in §3.2)

"pair/triple in a SORTED array hitting a target" → converge from both ends + discard proof
"k-sum, answers are values not indices"          → sort, fix the outers, converge
"max area/score between two ends"                → converge — move the limiting side
"partition / compact in place"                   → reader-writer; three groups → Dutch flag
"water/area bounded by the tallest so far"       → two ends + carried maxes
"unsorted input + need INDICES back"             → hashmap, not sort+pointers

Interrogation — answer in your journal

§S.1 · SET 03 — STACK & MONOTONIC STACK

Theory

Redundancy it kills — two flavors, one structure:

• Plain stack: re-scanning for "the most recent unresolved thing" (the innermost open bracket, the pending operator). LIFO is that question answered in O(1).
• Monotonic stack: for each element, scanning backward/forward for the nearest element that beats it — O(n) per element, O(n²) total. The stack kills it by discarding permanently: once a greater element stands in front of you, nothing behind it can ever be someone's "nearest greater" again.

The core template (next-greater form — memorize the shape, derive the rest):

stack = []                        # indices; values non-increasing
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:
        j = stack.pop()           # x is j's NEXT GREATER
        # resolve j here, using i and j
    stack.append(i)
# whatever remains never met a greater element

The discard proof (why popping is permanent): when x pops j, two things are settled at once. (1) j's answer is x — x is the first thing to beat it. (2) No future element can ever need j: any later element looking backward sees x standing in front of j, and x ≥ anything j could have offered. j is shadowed forever. This is the same "the discarded region cannot contain the answer" sentence from Set 02 — the stack is a discard structure.

Complexity tell: every element is pushed exactly once and popped at most once → total stack operations ≤ 2n → O(n) amortized, however long any single while-loop runs. This is the argument §2.2 promised you'd reuse — fourth appearance now (window's left pointer, LC 128's walks, converging pointers, stack pops). One direction, bounded total: same tell every time.

§S.2 · TYPE A

LIFO matching

Easy-tier, included because it IS the archetype: "most recent unresolved thing resolves first" in its purest form.

Brute force: repeatedly delete adjacent matched pairs until stuck — up to n/2 sweeps of O(n) → O(n²).

Redundancy: every sweep re-finds the innermost pair from scratch. The innermost open bracket is by definition the most recently seen one — a stack hands it over in O(1).

def isValid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False           # unmatched or mismatched closer
        else:
            stack.append(ch)
    return not stack                   # leftovers = unclosed opens

§S.3 · TYPE B · THE WORKHORSE

Next greater element

Brute force: forward scan per day → O(n²).

Redundancy: day i's scan re-walks days that day i−1's scan already crossed. On a falling run of temperatures, every day re-scans the same cold stretch.

Insight: keep a waiting room of unresolved days (indices). A new temperature resolves — pops — every waiting day cooler than it, and the answers are written at the pop: the popped day's next-warmer is exactly today. Equal temperatures stay waiting (the problem says strictly warmer), so the stack is non-increasing.

def dailyTemperatures(T):
    res = [0] * len(T)
    stack = []                        # indices; temps non-increasing
    for i, t in enumerate(T):
        while stack and T[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j            # first strictly warmer day
        stack.append(i)
    return res                        # never-resolved days keep 0

§S.4 · TYPE C

Previous greater with an aggregated payload

Brute force: walk backward per query → O(n) per call, O(n²) total.

Redundancy: whenever prices rise, today's backward walk re-traverses everything yesterday's walk covered.

Insight: span(today) = 1 + the spans of every popped day. A day popped (price ≤ today's) is shadowed permanently — any future backward walk hits today first, and today's price is ≥ theirs — so its span can be absorbed into today's and the day itself discarded. Store (price, span) pairs: the payload rides the stack.

class StockSpanner:
    def __init__(self):
        self.stack = []               # (price, span); prices strictly decreasing
    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

§S.5 · TYPE D

Greedy build with a budget

Brute force: choose which n−k digits survive → C(n, k) subsequences, exponential.

Insight: most-significant positions dominate, so spend deletions there first. Build the answer on a stack; while budget remains and the top digit is larger than the incoming one, pop it. Exchange argument (Set 02, Type C — same proof style): any solution that keeps a larger digit in front of a smaller one can be improved by deleting that larger digit instead — swapping the choice never hurts, so the greedy pop is never suboptimal.

def removeKdigits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    if k:
        stack = stack[:-k]            # non-decreasing leftovers: worst digits at the tail
    return ''.join(stack).lstrip('0') or '0'

Same family (do after): LC 316 Remove Duplicate Letters (budget = "must still be able to supply each letter"), LC 321 Create Maximum Number.

§S.6 · TYPE E

Contribution counting

Brute force: n² subarrays × O(n) min → O(n³); running min while extending → O(n²).

The reframe (this is the skill): don't ask "what is each subarray's min" — ask "for how many subarrays is arr[j] THE min?" Flip the sum from subarrays to elements: each element contributes arr[j] × (number of subarrays it dominates).

Derivation of the count: arr[j] is the min of exactly the subarrays that start after its previous-smaller element and end before its next-smaller element. left = j − prevSmaller(j) start choices, right = nextSmaller(j) − j end choices; the choices are independent → left × right subarrays.

The tie-break: with duplicates, "smaller" must be strict on one side and non-strict on the other (here: previous strictly smaller, next smaller-or-equal) so each equal-min subarray is assigned to exactly one owner. Both strict → subarrays with tied mins counted zero times; both non-strict → counted twice.

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    total = 0
    stack = []                        # indices; values strictly increasing
    for i in range(len(arr) + 1):
        cur = 0 if i == len(arr) else arr[i]   # sentinel flushes everything
        while stack and arr[stack[-1]] >= cur:
            j = stack.pop()
            left = j - (stack[-1] if stack else -1)   # prev STRICTLY smaller
            right = i - j                             # next smaller OR EQUAL
            total = (total + arr[j] * left * right) % MOD
        stack.append(i)
    return total

§S.7 · TYPE F · THE BOSS

Largest rectangle in a histogram

Brute force: for each bar, expand left and right while bars stay ≥ it → O(n²).

Redundancy: neighboring bars re-scan the same stretches to find their limits — and "limit" means exactly nearest smaller on each side: the Type E skeleton, aimed at a max instead of a sum.

Insight: keep an increasing stack of indices. When the incoming bar is lower than the top, the top bar's rectangle is settled: its right wall is here (i), its left wall is just past the new stack top, so width = i − stack[-1] − 1 (or i if the stack empties — nothing to its left was shorter). A sentinel height 0 at the end flushes every bar without a second loop.

def largestRectangleArea(heights):
    stack = []                        # indices; heights increasing
    best = 0
    for i in range(len(heights) + 1):
        cur = 0 if i == len(heights) else heights[i]
        while stack and heights[stack[-1]] > cur:
            j = stack.pop()
            width = i - (stack[-1] + 1 if stack else 0)
            best = max(best, heights[j] * width)
        stack.append(i)
    return best

When this feels derivable — not memorized — the set is yours. LC 85 Maximal Rectangle is this per matrix row.

§S.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Popped an empty stack on an unmatched closer (")" as first char) — guard not stack
• Forgot the final not stack in LC 20 — "((" passes wrongly
• Strict/non-strict pop chosen carelessly: max problems forgive it (LC 84), counting problems don't (LC 907 on [2, 2] double-counts or zero-counts)
• No sentinel flush — bars still waiting on the stack at the end never got resolved
• Wrote answers at the wrong moment: NEXT-greater resolves at POP, PREVIOUS-greater reads the top at PUSH
• Quiet quadratic: list.pop(0) / insert(0, x) as "stack" ops — O(n) each; use append/pop at the END
• Circular array (LC 503) without the 2n sweep + modulo
• Needed COUNTS of greater elements or range sums — popping destroys that info; that's Fenwick / merge-sort territory, not a stack

Signals → pattern (added to the drill deck in §3.2)

"next / previous greater or smaller element"     → monotonic stack — resolve at pop / peek at push
"how many days/steps until a bigger X"           → next-greater on indices; answer = distance at pop
"span / consecutive run ending here"             → previous-greater + (value, span) payload
"remove k to make smallest/largest sequence"     → greedy stack + budget, exchange argument
"sum/count of min/max over ALL subarrays"        → contribution: strict prev × non-strict next
"largest rectangle / max area under a skyline"   → increasing stack, width at pop, sentinel
"valid nesting / matched pairs / undo"           → plain LIFO stack

Interrogation — answer in your journal

§BS.1 · SET 04 — BINARY SEARCH

Theory

Redundancy it kills: a linear scan inspects every element, but against ordered structure one comparison decides half the candidates at once — if arr[mid] < target in a sorted array, every element at or left of mid is also < target, and checking them individually is pure repeated work. Binary search discards a provably-dead half per probe: O(n) → O(log n).

The senior reframe — it's not about sorted arrays. Binary search works on any monotonic predicate: a boolean P over an ordered domain that reads False…False True…True (once true, forever true). The task is always find the boundary. A sorted-array lookup is just the special case P(i) = "arr[i] ≥ target". This reframe is what unlocks half the mediums (Types D–F).

The core template (boundary / lower-bound form — the one that generalizes):

lo, hi = 0, n                  # answer lives in [lo, hi]
while lo < hi:
    mid = (lo + hi) // 2
    if P(mid):
        hi = mid               # mid might BE the first True — keep it
    else:
        lo = mid + 1           # mid is False — boundary strictly right
return lo                      # the first True (n if none)

Complexity tell: the search space halves every probe → after k probes, n/2ᵏ candidates remain → ⌈log₂ n⌉ probes. Constraint smell: answers ranging to 10⁹ with an O(n) feasibility check per guess ⇒ binary search on the answer, O(n log R) with log₂(10⁹) ≈ 30. Phrase-level tells: "minimize the maximum", "smallest X such that", "first/last position".

§BS.2 · TYPE A

Exact match — the closed-interval archetype

Easy-tier, included because it IS the archetype — and because a majority of engineers still write it with an off-by-one. There are two clean templates; the bugs come from mixing them.

Discard proof: if arr[mid] < target, sortedness certifies every index ≤ mid holds a value < target — none can be the answer; discard the closed left half including mid. Mirror for >.

def search(nums, target):
    lo, hi = 0, len(nums) - 1          # closed interval [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

§BS.3 · TYPE B

Boundary search (lower bound)

Brute force: find any occurrence, then scan outward — the equal-run can be the whole array → O(n).

Redundancy: the outward scan re-checks elements when one probe against the run's edge predicate decides half of them.

Insight: both edges are lower-bound queries. P(i) = "arr[i] ≥ target" is monotonic; its boundary is the first occurrence. The last occurrence needs no second template: it is lower_bound(target + 1) − 1. One tool, aimed twice — the same "reframe the second question as the first" move as §1.7's transform.

def searchRange(nums, target):
    def lower_bound(t):                # first index with nums[i] >= t
        lo, hi = 0, len(nums)          # half-open: answer in [lo, hi]
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= t:
                hi = mid
            else:
                lo = mid + 1
        return lo
    first = lower_bound(target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, lower_bound(target + 1) - 1]

§BS.4 · TYPE C

Repairing broken sortedness

The obstacle: global sortedness is gone, so the Type A discard proof doesn't apply. The repair: cut anywhere and at least one half is still fully sorted (the rotation point lies in only one half). The sorted half's endpoints form an O(1) certificate: target is inside its range, or provably not in that half at all.

Discard proof: if the left half is sorted and nums[lo] ≤ target < nums[mid], sortedness certifies target can only live there — discard the right. If target is outside that range, the sorted half provably doesn't contain it — discard it instead. Either way half the array dies per probe, exactly as before.

def searchRotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:      # left half sorted (== : one-cell half)
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                          # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

§BS.5 · TYPE D · THE HIGHEST-ROI VARIANT

Binary search on the answer

Brute force: try every speed 1..max(piles), checking feasibility in O(n) each → O(n · maxPile). With piles up to 10⁹, hopeless.

Redundancy: feasibility is monotonic in speed — if speed s works, every s′ > s works (eating faster never hurts). Testing speeds one by one re-establishes what monotonicity already implies about half of them.

Insight: there is no array anywhere. The domain is the answer space [1, max(piles)], the predicate is can(speed), and the question is a lower bound — the §BS.1 template verbatim. This is the reframe that converts "optimization problem" into "boundary of a monotonic predicate", and it's the single most-asked binary-search shape at FAANG.

def minEatingSpeed(piles, h):
    def can(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    lo, hi = 1, max(piles)             # smallest feasible speed lives here
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid                   # feasible — try slower
        else:
            lo = mid + 1               # infeasible — all slower speeds are too
    return lo

§BS.6 · TYPE E

Local monotonicity — peak finding

Brute force: scan for the first descending edge → O(n).

The surprise: the array is completely unsorted, yet binary search applies — because the needed predicate is still monotonic in the direction of travel. Look at the edge between mid and mid+1:

Discard proof: if nums[mid] > nums[mid+1] (descending edge), walk left from mid: either values keep rising toward index 0 — which is then a peak against the −∞ boundary — or they turn somewhere, and the turn is a peak. Either way a peak exists in [lo, mid]; the right half may be discarded without ever looking at it. Mirror for an ascending edge. We don't discard "no answer there" — we discard "an answer is guaranteed on this side", which is just as valid for an "any peak" question.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[mid + 1]:
            hi = mid                   # a peak is guaranteed in [lo, mid]
        else:
            lo = mid + 1               # a peak is guaranteed in [mid+1, hi]
    return lo

§BS.7 · TYPE F · THE BOSS

Partition search across two arrays

Brute force: merge → O(m+n). The demanded log bound rules out even looking at every element — a strong hint that the search is over cut positions, not values.

Derivation: a median splits the union into halves. Take i elements of A and j = (m+n+1)//2 − i of B for the left side — the size constraint eliminates one variable. A cut is correct iff every left element ≤ every right element; within each array that's free (sorted), so only the cross conditions remain: A[i−1] ≤ B[j] and B[j−1] ≤ A[i].

Why binary search applies: as i grows, A[i−1] rises and B[j] falls (j shrinks) — so the predicate "A[i−1] ≤ B[j]" is monotonic in i: true, true, …, false, false. The correct cut is its boundary. Search i over the shorter array so j = half − i can never leave [0, n].

def findMedianSortedArrays(A, B):
    if len(A) > len(B):
        A, B = B, A                    # search the shorter array
    m, n = len(A), len(B)
    half = (m + n + 1) // 2
    lo, hi = 0, m                      # i = how many of A go left
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        a_left  = A[i - 1] if i > 0 else float('-inf')
        a_right = A[i]     if i < m else float('inf')
        b_left  = B[j - 1] if j > 0 else float('-inf')
        b_right = B[j]     if j < n else float('inf')
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1                 # A gives too much — move the cut left
        else:
            lo = i + 1

When this feels derivable — size constraint kills a variable, cross-conditions form a monotonic predicate, sentinels close the edges — the set is yours. LC 410 (Split Array Largest Sum) is the other famous boss, and it's just Type D with a greedy counter.

§BS.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Blended templates: closed [lo, hi] + lo <= hi + mid ± 1 is one unit; half-open [lo, hi) + lo < hi + hi = mid is the other — mixing = off-by-one
• Infinite loop: lo = mid with a floor midpoint — needs ceil (lo + hi + 1) // 2; breaks on any 2-cell interval like [1, 2]
• (lo + hi) // 2 overflows int in Java/C++ — write lo + (hi − lo) / 2 there; Python ints don't overflow (say so, then write the safe form anyway)
• Predicate not actually monotonic → converges confidently to garbage — the quietest wrong answer in this lab
• Rotated + duplicates (LC 81): equal endpoints carry zero information — shrink by one, and admit the O(n) worst case ([1,1,1,1,0,1])
• Quiet linear: slicing per probe (nums[mid+1:] recursion) copies O(n) each level — pass indices, not slices
• Real-valued answer spaces: never test float equality — fix the iteration count (~100) or use an epsilon
• Answer-space bounds wrong: Koko's lo is 1, but LC 1011's lo is max(weights) — an infeasible lower bound breaks the invariant silently

Signals → pattern (added to the drill deck in §3.2)

"sorted array — exact / first / last position"    → lower-bound template (half-open)
"minimize the maximum / maximize the minimum"     → binary search the ANSWER + greedy check
"smallest X such that condition holds"            → boundary of a monotonic predicate
"rotated sorted array"                            → one half is always sorted — certify & discard
"find any peak / local extremum"                  → move toward the rising neighbor
"two sorted arrays, k-th / median"                → partition search on the shorter array

Interrogation — answer in your journal

§L.1 · SET 05 — LINKED LIST

Theory

The structural trade first: arrays give O(1) random access and O(n) splicing; linked lists invert it — O(1) splice/insert/delete given a handle to the node, but reaching position i costs O(i). Every pattern in this set exists because of that asymmetry.

Redundancy it kills — two flavors:

• Re-walking: the brute force re-traverses from the head every time it needs a position (a predecessor, the middle, the n-th from end) — O(n) per access → O(n²). The fix: carry the handles you'll need during one pass, instead of re-deriving positions.
• Copy-out: "dump to an array, do array things, rebuild" — correct, O(n) extra space, and it forfeits exactly the skill being graded. Name it as the baseline, then beat it in place.

The three primitives (this whole set is compositions of these):

# 1. dummy head — makes the head a normal node
dummy = ListNode(0, head)             # prev starts here, never None

# 2. fast/slow — positional identity: fast at 2k ⇒ slow at k
slow, fast = head, head

# 3. in-place reversal — one edge rewired per step
prev, cur = None, head
while cur:
    cur.next, prev, cur = prev, cur, cur.next
return prev                           # RHS evaluates fully before assignment

Complexity tell: every pointer here advances monotonically down the list and each node is visited a bounded number of times (once, or twice for check-then-reverse shapes) → O(n) time, O(1) space. Fifth appearance of the one-direction argument (§2.2 window, LC 128 walks, converging pointers, stack pops — now list pointers).

§L.2 · TYPE A

In-place reversal

Easy-tier, included because it IS the archetype — the rotation it teaches is a sub-routine of half the mediums and the boss.

Brute force: copy values to an array, reverse, rebuild → O(n) space. Or: repeatedly walk from the head to find each predecessor → O(n²).

Redundancy: re-walking for a predecessor you were standing on one step ago. Carry it instead.

def reverseList(head):
    prev, cur = None, head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    return prev

§L.3 · TYPE B

Fixed-gap pointers + dummy head

Brute force: pass 1 counts the length L, pass 2 walks to node L − n → two passes.

Redundancy: the second walk re-traverses exactly what the first walk already measured. Fold the measurement into the walk.

Derivation: start both pointers at a dummy before the head; advance lead by n + 1 first. Both then step together, so the gap stays n + 1 forever. When lead falls off the end (position L + 1 counting from dummy), trail sits at position L − n — exactly the predecessor of the node to delete. The gap is the proof; no counting needed.

Why the dummy is load-bearing: if the head itself is the target ([1], n = 1), trail must stand before the head — a position that doesn't exist without the dummy. This is the same "seed the empty case" move as {0:1} in §1.4 and the sentinels of §S.7/§BS.7.

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    lead = trail = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead, trail = lead.next, trail.next
    trail.next = trail.next.next
    return dummy.next

§L.4 · TYPE C

Composing the primitives

Brute force: array of node references, two-pointer indexing, rewire → O(n) space. Fine engineering; not the ask.

Insight: the target order is "first half interleaved with reversed second half" — so the solution is literally three primitives in sequence: middle (fast/slow), reverse the back half (Type A), interleave. Nothing new is invented; the skill being graded is recognizing the decomposition and keeping the seams clean.

def reorderList(head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    second = slow.next
    slow.next = None                   # cut — skipping this creates a cycle
    prev = None
    while second:
        second.next, prev, second = prev, second, second.next
    first, second = head, prev
    while second:
        nxt1, nxt2 = first.next, second.next
        first.next = second
        second.next = nxt1
        first, second = nxt1, nxt2

§L.5 · TYPE D

Floyd's cycle detection — with the actual proof

Brute force: hashset of visited nodes; first repeat is the cycle start → O(n) time average (hashing node identities), O(n) space. Correct — the O(1)-space demand is what forces Floyd.

Phase 1 — they must meet: once slow enters the cycle, fast is already inside it. Per tick the gap (measured around the cycle) shrinks by exactly 1 — relative speed is 2 − 1 = 1 — so it reaches 0 within c ticks. No jump-over is possible because the relative step is 1: proof by the gap arithmetic, not by intuition.

Phase 2 — the meeting point knows the start. Let a = distance head → cycle start, c = cycle length, b = distance cycle start → meeting point. At the meeting, slow has walked a + b and fast 2(a + b); the difference a + b must be a whole number of laps: a + b = kc, so a ≡ −b (mod c). Therefore a pointer from the head and one from the meeting point, both stepping by 1, arrive at the cycle start simultaneously — the head pointer walks a, the other walks a ≡ c − b positions around the cycle. The algebra is the algorithm.

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:               # node identity, never value equality
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None

§L.6 · TYPE E

Structure as the hashmap — interleaved cloning

Brute force (say it first): hashmap original → clone, one pass to create, one to wire next/random → O(n) time average, O(n) space. This is the canonical-key idea from §B.3: the map answers "which clone corresponds to this node?"

The O(1)-space insight: encode that map positionally. Interleave each clone right behind its original (A→A′→B→B′→…). Now "the clone of X" is simply X.next — the list's own structure stores the mapping, so clone.random = orig.random.next wires every random in O(1) each. Unweave to finish.

def copyRandomList(head):
    cur = head
    while cur:                         # 1. interleave clones
        cur.next = Node(cur.val, cur.next)
        cur = cur.next.next
    cur = head
    while cur:                         # 2. randoms via successor position
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next
    cur, dummy = head, Node(0)
    tail = dummy
    while cur:                         # 3. unweave — restore the original
        tail.next = cur.next
        tail = tail.next
        cur.next = cur.next.next
        cur = cur.next
    return dummy.next

§L.7 · TYPE F · THE BOSS

Grouped reversal with stitching

Brute force: array of nodes, reverse in slices, rebuild → O(n) space.

Insight: per group, three obligations — (1) prove k nodes exist before touching anything (a counting walk; the leftover rule forbids reversing a short tail), (2) reverse the group with the Type A rotation, seeded so the group's tail exits pointing at the next group's head, (3) stitch the previous group's tail to the group's new head. Seeding prev with the next group's start makes the first rotation do the exit-wiring for free — no patch-up pass.

Invariant per iteration: everything before group_prev is fully processed and correctly linked; the dummy seeds it (same role as §L.3). Each loop turn re-establishes it one group further.

def reverseKGroup(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        node, count = group_prev.next, 0
        while node and count < k:      # existence check — touch nothing yet
            node, count = node.next, count + 1
        if count < k:
            return dummy.next          # short tail stays as-is
        tail = group_prev.next         # old head becomes the group's tail
        prev, cur = node, tail         # seed prev = next group's head
        for _ in range(k):
            cur.next, prev, cur = prev, cur, cur.next
        group_prev.next = prev         # stitch: prev is the new group head
        group_prev = tail

When this feels derivable — check, rotate with a seeded prev, stitch, advance the invariant — the set is yours. LC 92 (Reverse Linked List II) is one group of this with explicit bounds.

§L.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Overwrote cur.next before capturing it — suffix orphaned (Java/JS: explicit temp first; Python tuple assignment is safe because the RHS evaluates first)
• No dummy head → head-mutation special case breaks ([1], n = 1 in LC 19)
• Forgot the cut (slow.next = None in LC 143) → accidental cycle, infinite loop far from the cause
• Null-check order: while fast and fast.next — touch fast.next.next only behind both guards
• Compared node VALUES where node IDENTITY was meant — [1, 1, 1] has no cycle; use is, not ==
• Quiet quadratic: "walk from head to position i" inside a loop — Θ(n²) on a list; carry handles instead
• LC 138: returned the copy but left the original interleaved — restore it
• Needed random access / index arithmetic on a list → copy to an array first and SAY the O(n)-space trade, don't fake it with re-walks

Signals → pattern (added to the drill deck in §3.2)

"reverse a list / a section in place"       → three-pointer rotation, invariant first
"n-th from the end, one pass"               → fixed-gap pointers + dummy head
"middle of the list / split in half"        → fast ×2, slow ×1
"is there a cycle / where does it begin"    → Floyd: meet, then head + meeting walk together
"deep copy with arbitrary extra pointers"   → map node→clone, or interleave clones for O(1)
"delete/insert where the head might change" → dummy head — the head becomes a normal node

Interrogation — answer in your journal

§TR.1 · SET 06 — TREES (DFS · BFS · BST)

Theory

Redundancy it kills: a tree already encodes the divide — every node's subtree is an independent subproblem. The brute force ignores that and re-derives structure per query: "is this subtree balanced?" recomputed heights for every ancestor, "what's on this level?" re-walks from the root — O(n) work per node, O(n²) total. Structural recursion kills it: visit each node once, compute its answer from its children's answers. Post-order ("children before parent") is the tree's version of the prefix sum — an aggregate computed once and reused upward. (Rusty on how recursive calls stack and unwind? §F.2 is the five-minute refresher.)

Three skeletons carry the whole set:

# 1. DFS — structural recursion (post-order shown)
def dfs(node):
    if not node:
        return BASE                    # the empty tree's answer
    left, right = dfs(node.left), dfs(node.right)
    return combine(node, left, right)

# 2. BFS — level snapshot
queue = deque([root])
while queue:
    for _ in range(len(queue)):        # freeze: exactly one level
        node = queue.popleft()
        # enqueue children

# 3. BST identity
# inorder traversal is sorted  ⟺  BST property holds

Complexity tell: "each node visited exactly once, O(1) combine per visit" → O(n) — the tree version of the one-direction argument. Space is the traversal frontier: DFS holds a root-to-leaf path → O(h), which is O(log n) balanced but O(n) skewed — always give both; BFS holds a level → O(w), up to n/2 on a complete tree's bottom level.

§TR.2 · TYPE A

Structural recursion

Easy-tier, included because it IS the archetype — the three-line shape every harder type decorates.

Derivation: the longest path from a node goes through whichever child has the deeper subtree, plus the node itself: depth(node) = 1 + max(depth(left), depth(right)), with the empty tree contributing 0. That recurrence is the code.

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

§TR.3 · TYPE B

BFS — the level snapshot

Brute force: for each depth d, DFS to find the rightmost node at depth d → O(n) per level, O(n²) on a right chain.

Redundancy: every per-level search re-walks the same upper tree. One traversal can classify every node by level as it goes.

Insight: the queue naturally holds levels — but only if you freeze the boundary. Snapshot len(queue) before the inner loop: exactly that many dequeues belong to the current level, and everything enqueued during them is the next level. The last node dequeued in the snapshot is the level's rightmost.

from collections import deque

def rightSideView(root):
    if not root:
        return []
    res, queue = [], deque([root])
    while queue:
        for _ in range(len(queue)):    # frozen level boundary
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(node.val)           # last dequeued = rightmost
    return res

§TR.4 · TYPE C

BST — range narrowing

The trap IS the problem: the BST property is global — every node in a left subtree is smaller than the root, not just the immediate child. The parent-child local check accepts [5, 1, 4, null, null, 3, 6]: node 3 sits in 5's right subtree but 3 < 5. Most wrong answers on this problem are exactly that.

Derivation: each edge adds one constraint — going left caps values above, going right floors them below. A node is legal iff it respects all ancestor constraints, and the pair (lo, hi) carries all of them in O(1): descend left → hi becomes node.val; descend right → lo does. Strict inequalities because duplicates are invalid here — always ask the duplicates policy before choosing < vs ≤.

def isValidBST(root):
    def valid(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return (valid(node.left, lo, node.val) and
                valid(node.right, node.val, hi))
    return valid(root, float('-inf'), float('inf'))

§TR.5 · TYPE D

Lowest common ancestor — post-order reporting

Brute force: record the root→p and root→q paths (two O(n) searches), then compare paths for the last shared node → O(n) time but O(n) extra space and two passes.

Redundancy: both path searches walk the same upper tree, and the comparison re-walks the paths. One post-order pass can do all three jobs.

Derivation — specify the return value, then trust it (§TR.1): let dfs(node) return the LCA if both p and q live in node's subtree; else p or q if that one is here; else None. Base: null or hitting p/q returns itself. Combine: if both children report a find, p and q lie in different subtrees — this node is the deepest split point, i.e. the LCA. If one side reports, pass it up unchanged. The early stop at p is safe even when q is p's descendant: the LCA is p itself in that case, so nothing below p needs visiting.

def lowestCommonAncestor(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root                    # p and q split here — the LCA
    return left or right

§TR.6 · TYPE E

Reconstruction from traversals

The identity: preorder = root, then the entire left subtree, then the right; inorder = left subtree, root, right. So preorder hands you each root in construction order, and the root's position in inorder splits the remaining values into the two subtrees.

The quiet quadratic (say it, then kill it): the natural code calls inorder.index(root) and slices both arrays per node — O(n) searching + O(n) copying per node → Θ(n²) on a chain like a strictly-decreasing sequence. It passes every small test. Two fixes, both from earlier sets: a value→position hashmap (the canonical-key payload, §B.3) kills the search; window bounds instead of slices kill the copying; and a single advancing pointer consumes preorder — the one-direction argument yet again.

def buildTree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}   # value -> inorder position
    pre_i = 0
    def build(lo, hi):                 # inorder window [lo, hi)
        nonlocal pre_i
        if lo >= hi:
            return None
        root = TreeNode(preorder[pre_i])
        pre_i += 1
        mid = idx[root.val]
        root.left = build(lo, mid)     # MUST build left first —
        root.right = build(mid + 1, hi)  # preorder is consumed in that order
        return root
    return build(0, len(inorder))

§TR.7 · TYPE F · THE BOSS

Max path sum — the two-quantity recursion

Brute force: enumerate all node pairs, sum the path between them → O(n²) pairs × O(n) path = O(n³); even with LCA tricks, O(n²).

The organizing observation: every path has a unique highest node — its turning point. Enumerate paths by turning point and each node need only answer: best path that turns here = node.val + best downward arm on the left + best downward arm on the right.

The two-quantity split (this is the whole problem): what a node reports upward is different from what it scores locally. Upward must be a single arm — node.val + max(one arm) — because a parent's path through this node cannot fork into both children (it would need to visit this node twice). Locally it may use both arms. Conflating these two is the classic wrong answer.

The clamp is a discard proof: max(arm, 0) — a negative arm strictly lowers every path that includes it, so the empty arm dominates it (the exchange argument, §T.4/§S.5, in one character). But the node itself can't be discarded — a path must contain at least one node — which is why best starts at −∞, not 0: on the tree [−3] the answer is −3.

def maxPathSum(root):
    best = float('-inf')
    def gain(node):                    # best single downward arm from node
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)   # path turning here
        return node.val + max(left, right)          # one arm continues up
    gain(root)
    return best

When this feels derivable — unique turning point, two quantities, clamp-as-discard — the set is yours. LC 543 (Diameter) is this with sum replaced by edge count; LC 687 with equality constraints.

§TR.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Local parent-child BST check — [5,1,4,null,null,3,6] passes it and isn't a BST; carry (lo, hi) or check inorder monotonicity
• Recursion depth: 10⁵-node chain blows Python's ~1000-frame default — go iterative or raise the limit and SAY it
• BFS level bug: reading len(queue) inside the loop while it mutates — freeze it first; and list.pop(0)/shift() = quiet O(n²), use a deque
• LC 105 with .index() + slicing — quiet Θ(n²) on a chain; index map + window bounds + preorder pointer
• LC 124: returned both arms upward (a parent's path would visit this node twice) — report one arm, score two locally
• Initialized the LC 124 best to 0 — all-negative trees ([−3]) must still return a node; −∞ start, clamp only the arms
• Strict vs inclusive bounds without asking the duplicates policy; Java int-extreme sentinels overflow — use longs/nullable bounds
• Input might contain a cycle or shared nodes (i.e., it's a graph) — tree DFS has no visited set and recurses forever; that's Set 09's tool

Signals → pattern (added to the drill deck in §3.2)

"depth / count / sum over a tree"               → post-order structural recursion
"level by level / right side view / zigzag"     → BFS with a frozen level snapshot
"validate BST / use the sorted structure"       → range narrowing, or inorder is sorted
"k-th smallest in a BST"                        → inorder = sorted stream, stop at k
"lowest common ancestor"                        → post-order: the node where both sides report
"rebuild a tree from traversals"                → preorder pointer + inorder index map
"best path / diameter through a tree"           → two arms locally, one arm reported upward

Interrogation — answer in your journal

§H.1 · SET 07 — HEAP & TOP-K

Theory

Redundancy it kills: full sorting when only the extreme is ever consumed. Sorting buys a total order — n log n of information — but "give me the current min" uses one bit of it, over and over. The naive alternatives both re-do work: re-scan for the min per extraction (O(n) each → O(n²)) or keep the collection sorted per insertion (O(n) shifting each). The heap maintains exactly the guarantee consumed — a partial order strong enough to certify the root — at O(log n) per update. Pay only for the order you use.

The structure: a complete binary tree stored flat in an array — children of index i at 2i+1 and 2i+2, no pointers. Min-heap property: every parent ≤ its children.

Two facts interviewers probe directly:

• heapify is O(n), not O(n log n). Build bottom-up with sift-downs: the n/2 leaves cost 0, and ≤ n/2ʰ⁺¹ nodes sit at height h costing h each → Σ h·n/2ʰ⁺¹ = n·Σ h/2ʰ⁺¹ = n·1 = O(n). (Sift-up building is genuinely O(n log n) — the deep, numerous nodes pay the tall cost. Direction matters.)
• The size-k inversion: to track the k LARGEST, keep a MIN-heap of size k — its root is the admission threshold. Anything ≤ the root is provably outside the top k (k items ≥ it already exist). Min for largest, max for smallest — the single most common recognition trip-up in this pattern.

Complexity tell: "n operations × log(heap size)" — and the heap size is a design choice: cap it at k and the bound is O(n log k), at 26 letters and log is a constant. Constraint smell: "stream", "online", "as they arrive" ⇒ heap; static array + single query ⇒ quickselect/buckets.

§H.2 · TYPE A

The size-k heap

Brute force: sort, index from the end → O(n log n).

Redundancy: a total order was purchased; one order statistic was consumed.

The discard proof: maintain a min-heap holding the k largest seen so far. When x ≤ heap[0], there are already k elements ≥ heap[0] ≥ x — so x can never be among the k largest, and skipping it is permanent (the discard sentence of §T.1, applied to values instead of positions). When x beats the root, the root is the element it displaces.

import heapq

def findKthLargest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)                # O(k) — bottom-up, not k pushes
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x) # pop root + push, one sift
    return heap[0]

§H.3 · TYPE B

Keyed comparison with payloads

What this adds to Type A: the ranking key is computed (distance), the payload (the point) must ride along, and the polarity flips — k closest means evicting the farthest, so the size-k heap must expose the current farthest: a max-heap, via negation in Python.

Skip the sqrt: x² + y² preserves the ordering because sqrt is monotonic — comparing through a monotonic transform never changes a comparison's outcome (§BS.1's monotonicity, used as a micro-optimization). Also dodges float precision entirely.

def kClosest(points, k):
    heap = []                          # (-dist², x, y): max-heap by negation
    for x, y in points:
        d = x*x + y*y
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif -d > heap[0][0]:
            heapq.heapreplace(heap, (-d, x, y))
    return [[x, y] for _, x, y in heap]

§H.4 · TYPE C

K-way merge — frontier expansion

Brute force: form all n·m sums, sort, take k → O(nm log nm). With n = m = 10⁵, the grid alone is 10¹⁰ — unbuildable.

Redundancy: the sum grid is sorted along every row and every column; a global sort ignores that almost all pairs are provably behind smaller ones.

The frontier insight: the smallest pair is (0,0). After popping (i, j), the only newly eligible candidate is its successor in one direction — seed the heap with column 0 (pairs (i, 0) for i < min(k, n)) and push (i, j+1) on each pop. Every pair then has exactly one predecessor that pushes it, so no visited set is needed — dedup by construction.

The proof: invariant — for every not-yet-popped pair, some ancestor of it (same i, smaller j, or its seed) sits in the heap with sum ≤ its sum, because sums rise along rows. So the heap's min is always the global next-smallest: nothing smaller can be hiding outside the heap. This "expand the cheapest frontier node" argument IS Dijkstra's — Set 09 will reuse it on graphs verbatim.

def kSmallestPairs(nums1, nums2, k):
    heap = [(nums1[i] + nums2[0], i, 0)
            for i in range(min(k, len(nums1)))]
    heapq.heapify(heap)
    res = []
    while heap and len(res) < k:
        s, i, j = heapq.heappop(heap)
        res.append([nums1[i], nums2[j]])
        if j + 1 < len(nums2):
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
    return res

§H.5 · TYPE D

Greedy scheduling by frequency

The greedy: at every slot, run the most-frequent ready task. Exchange argument (§T.4, §S.5): the most frequent task generates the most future cooldown constraints; swapping it earlier in any schedule never adds idle time, so greedy-by-frequency is never suboptimal. The heap is just the machine that serves "most frequent ready" in O(log 26).

The mechanism: a max-heap of remaining counts plus a FIFO cooldown queue of (ready_time, count) — a task pops off the heap to run, then waits in the queue until time+n+1. The queue is FIFO-correct because tasks re-become ready in the order they ran.

from collections import deque

def leastInterval(tasks, n):
    counts = {}
    for t in tasks:
        counts[t] = counts.get(t, 0) + 1
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)
    cooldown = deque()                 # (ready_time, negated remaining)
    time = 0
    while heap or cooldown:
        time += 1
        if cooldown and cooldown[0][0] == time:
            heapq.heappush(heap, cooldown.popleft()[1])
        if heap:
            c = heapq.heappop(heap) + 1        # run once (counts negated)
            if c:
                cooldown.append((time + n + 1, c))
        # else: forced idle tick

§H.6 · TYPE E · THE BOSS

Two heaps — the running median

Brute force: keep a sorted array — O(n) insertion shifting per add (or re-sort, O(n log n)).

Redundancy: full order maintained when only the boundary between halves is consumed — the mirror image of top-k, where only the extreme mattered.

The construction: a max-heap lo holding the smaller half and a min-heap hi holding the larger half — the median lives at their facing roots. Two invariants: order (max(lo) ≤ min(hi)) and balance (0 ≤ len(lo) − len(hi) ≤ 1).

The insertion dance, derived: pushing num into lo unconditionally may violate order — so immediately move lo's max across to hi. Now order holds whatever num was: what crossed over is ≥ everything left in lo, and it entered hi where it competes normally. But hi may now be too big — if so, move hi's min back. Each step repairs exactly one invariant and cannot break the other (prove that; it's interrogation H4). Three heap ops, all O(log n).

class MedianFinder:
    def __init__(self):
        self.lo = []                   # max-heap (negated): smaller half
        self.hi = []                   # min-heap: larger half
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # repair order
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))  # repair balance
    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2

When this feels derivable — two invariants, a dance that repairs them one at a time — the set is yours. The two-heap split generalizes to any "boundary statistic": percentiles, IPO-style capital problems (LC 502), scheduling with both ends.

§H.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Polarity inversion missed: k LARGEST needs a MIN-heap (root = admission threshold), and vice versa
• Python heapq is min-only — negate on push AND re-negate on read; half-negation is a silent wrong answer
• Tuple ties fall through to the payload → TypeError on uncomparable objects (LC 23's ListNode) — insert a counter: (key, i, node)
• Treated the heap array as sorted — heap[:k] is level-order, not the k smallest; sort the survivors if order matters
• heapreplace pops FIRST (returns the old root even if the new item is smaller) — guard with if x > heap[0], or use heappushpop
• Claimed O(n log n) for heapify or O(n) for n pushes — it's the reverse; know the sum-of-heights argument
• Tried to decrease-key in heapq (doesn't exist) — push the duplicate, skip stale entries on pop (lazy deletion; Dijkstra runs on this)
• Used a heap for a static one-shot top-k — quickselect O(n) avg or buckets (bounded domain) are cheaper; heaps are for streams and merges
• JS has no built-in heap — hand-roll it; sorting per step is a quiet O(n² log n)

Signals → pattern (added to the drill deck in §3.2)

"k largest / smallest / closest, especially streaming"  → size-k heap of the OPPOSITE polarity
"merge k sorted lists / arrays"                         → heap of heads: pop min, push its successor
"running median / percentile of a stream"               → two heaps, order + balance invariants
"schedule by frequency with cooldown"                   → max-heap + FIFO cooldown queue
"k smallest sums / products from sorted sources"        → frontier expansion, dedup by predecessor
"need current min AND max simultaneously"               → two heaps or a sorted container — one heap can't

Interrogation — answer in your journal

§G.1 · SET 08 — INTERVALS & GREEDY

Theory

Two redundancies, one set:

• Intervals: the brute force checks overlap pairwise — O(n²) comparisons — but overlap is a local property once you sort: an interval can only interact with the current open block, never with anything already closed. Sort once, sweep once converts a global pairwise question into an adjacent one: O(n²) → O(n log n).
• Greedy: the brute force explores orderings and subsets (exponential, or DP) when a provably-safe local rule decides everything. The redundancy is the exploration itself — every branch the proof rules out.

The merge-sweep skeleton:

intervals.sort(key=lambda iv: iv[0])   # by START — for merging
merged = [intervals[0]]
for s, e in intervals[1:]:
    if s <= merged[-1][1]:             # touches the open block
        merged[-1][1] = max(merged[-1][1], e)
    else:
        merged.append([s, e])          # block closes forever

Complexity tell: the sort dominates → O(n log n), sweep O(n) on top. Constraint smell: 10⁵ intervals ⇒ sort + sweep is what's expected; greedy sweeps without sorting (Jump Game, Gas Station) are O(n)/O(1).

§G.2 · TYPE A

Merge sweep

Brute force: repeatedly find any overlapping pair, merge, restart until a fixed point → O(n²) per pass, up to n passes.

Redundancy: almost every pair compared cannot overlap — sorting makes the only possible interaction "next interval vs the open block".

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)   # extend, don't replace
        else:
            merged.append([s, e])
    return merged

§G.3 · TYPE B

Interval scheduling — earliest end first

Reframe first: minimize removals = keep the maximum non-overlapping set — the classic interval scheduling problem.

The rule: sort by END; always keep the interval that ends earliest among those compatible. Exchange proof in full: let OPT be any optimal solution, ordered by end. Greedy's first pick g ends no later than OPT's first pick o (g is the earliest-ending interval, period). Replace o with g: still disjoint from the rest of OPT (everything else starts after o ends ≥ g ends), same size. Repeat down the sequence — greedy never falls behind. Ending earliest leaves maximal room; that intuition is now a theorem.

Both tempting greedies fail: earliest-START keeps [1,100] and loses [2,3],[4,5]; SHORTEST-first on [[1,10],[9,12],[11,20]] picks [9,12], which blocks both others (optimal keeps two). Counterexamples are how you earn the right to greedy.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda iv: iv[1])   # by END — this line is the algorithm
    kept, last_end = 0, float('-inf')
    for s, e in intervals:
        if s >= last_end:                  # touching allowed here
            kept += 1
            last_end = e
    return len(intervals) - kept

§G.4 · TYPE C

Max concurrency — the event sweep

Reframe: min rooms = maximum number of meetings running at once — a counting question over time.

The audacious move: sort starts and ends independently, destroying which end belongs to which start. Legal because room count over time depends only on the multiset of events — each start is +1, each end is −1, and the running sum doesn't care about pairing. (That running sum of deltas is literally a prefix sum over events — §1.1 has been here all along.)

The sweep: walk the starts; if the earliest un-consumed end is ≤ this start, a room has freed — reuse it. Otherwise open a new room. The end pointer only moves forward: the one-direction argument again.

def minMeetingRooms(intervals):
    starts = sorted(iv[0] for iv in intervals)
    ends   = sorted(iv[1] for iv in intervals)
    rooms, e = 0, 0
    for s in starts:
        if s >= ends[e]:
            e += 1                     # earliest-ending meeting freed a room
        else:
            rooms += 1
    return rooms

§G.5 · TYPE D

Reachability — the furthest-reach sweep

Brute force: DFS/DP over "which positions are reachable" → O(n²).

Redundancy: reachability from the left is an interval [0, reach] — tracking which cells are reachable re-derives what one frontier number already says.

Invariant: after processing index i, reach = the maximum index reachable using only positions 0..i. If i itself exceeds reach, there's a gap no earlier position can cross — reachability is monotone, so fail immediately. No sorting needed: greedy isn't intervals-only.

def canJump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False               # unreachable gap — nothing later helps
        reach = max(reach, i + step)
    return True

§G.6 · TYPE E

Circular start — discard the failed prefix

Brute force: simulate the full circle from every start → O(n²).

The discard proof (this is the problem): run with a tank from start s; suppose it first dips negative at i. Then no station in (s..i] can be the answer either: starting anywhere inside means arriving at i with a tank ≤ the one that just failed — you forfeited the non-negative fuel accumulated between s and there. One failure discards the whole prefix; restart at i+1. Same shape as §T's "the discarded region cannot contain the answer", applied to start positions.

The global certificate: if total gain Σ(gas−cost) ≥ 0, an answer exists — so the surviving candidate needs no second simulation lap. Two facts, one pass.

def canCompleteCircuit(gas, cost):
    total = tank = start = 0
    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:
            start, tank = i + 1, 0     # prefix dead — restart after i
    return start if total >= 0 else -1

§G.7 · TYPE F · THE BOSS

Regret greedy — take it back later

Brute force: subsets → exponential; even ordering choices explode.

Step 1 — sort by deadline: any feasible set can be scheduled in deadline order (exchange: swapping two adjacent courses out of deadline order never violates the earlier deadline). So only deadline order need be considered.

Step 2 — the regret rule: take every course as it comes; when the running time exceeds the current deadline, evict the longest course taken so far (max-heap root, §H). Swapping a longer course for a shorter one keeps the count and strictly frees time — an exchange argument executed at runtime, with the heap as the machine that finds the swap in O(log n).

def scheduleCourse(courses):
    courses.sort(key=lambda c: c[1])       # by deadline
    taken = []                             # max-heap of durations (negated)
    time = 0
    for dur, deadline in courses:
        time += dur
        heapq.heappush(taken, -dur)
        if time > deadline:
            time += heapq.heappop(taken)   # evict the longest (negated value)
    return len(taken)

When this feels derivable — deadline order justified by exchange, invariant with a minimality rider, heap as the regret machine — the set is yours. Same species: LC 871 (refuel with a regret heap of skipped stations), LC 502 (IPO, two-phase heap greedy).

§G.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Wrong sort key: merging needs START-sort, scheduling needs END-sort — each fails quietly under the other
• Boundary semantics unasked: does [1,2] overlap [2,3]? One ≤ vs < decides merge-vs-separate and room-freed-vs-not
• Replaced the block end instead of max()-ing it — [[1,10],[2,3]] shrinks the block
• "Feels greedy" with no exchange proof — shortest-first scheduling dies on [[1,10],[9,12],[11,20]]
• JS: sort() is LEXICOGRAPHIC by default — [10,2] sorts as strings; always pass (a,b) => a[0]−b[0]
• Jump Game: updated reach before checking i > reach — a cell you can't stand on contributes no reach
• Gas Station: returned start without the total ≥ 0 certificate — the surviving candidate is only valid if the circle nets non-negative
• LC 57 solved by re-sort + merge — O(n log n) where the three-phase linear insert is the ask
• Weighted intervals (profits attached) — greedy is the WRONG tool; that's DP + binary search (LC 1235, Set 12)

Signals → pattern (added to the drill deck in §3.2)

"merge / insert overlapping intervals"           → sort by START, grow the open block
"max non-overlapping / min removals"             → sort by END, earliest-end-first + exchange proof
"min rooms / max concurrent / peak load"         → event sweep (+1/−1) or starts-vs-ends pointers
"can I reach the end / min jumps"                → furthest-reach frontier, O(n) no sort
"circular tour, where to start"                  → running tank + discard the failed prefix
"max tasks under deadlines"                      → sort by deadline + regret heap (evict longest)

Interrogation — answer in your journal

§GR.1 · SET 09 — GRAPHS: BFS · DFS · TOPO · DIJKSTRA

Theory

Redundancy it kills: revisiting states. On a tree every node has one parent, so a walk can't return (§TR.1); on a graph, cycles and diamonds mean a memoryless walk re-explores the same node once per path reaching it — exponentially many on dense graphs, forever on cycles. The visited set is the entire pattern: each node is processed exactly once, and everything else in this set is a choice of processing order — FIFO (BFS), LIFO (DFS), by indegree (topo), by tentative distance (Dijkstra).

The BFS skeleton, with the two load-bearing choices:

adj = ...                              # adjacency list, built from edges
visited = {src}
queue = deque([src])
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if v not in visited:
            visited.add(v)             # mark ON ENQUEUE — see traps
            queue.append(v)

Complexity tell: O(V + E) — every node enqueued once, every edge examined a constant number of times. The proof is the charging argument (§2.2's lineage): charge each edge to its endpoints, each paying O(1). Dijkstra adds the heap: O(E log V). Constraint smell: 10⁵ nodes + 10⁵ edges ⇒ linear graph algorithms; V ≤ ~400 ⇒ O(V³) Floyd-Warshall is fair game.

§GR.2 · TYPE A

Connected components — flood fill

The grid IS a graph: cells are nodes, 4-direction adjacency is the edge set — no adjacency list needed, direction vectors generate edges on the fly.

Redundancy: asking "which island does this cell belong to?" per cell re-walks components endlessly. Flip it: iterate cells, and every unvisited land cell must be the first touch of a brand-new component — flood it entirely, count one.

Why the count is right: flooding consumes a whole component before the outer scan continues (DFS reaches everything connected), so components and flood-starts correspond one-to-one — no component counted twice, none missed.

def numIslands(grid):
    m, n = len(grid), len(grid[0])
    def sink(r, c):
        if not (0 <= r < m and 0 <= c < n) or grid[r][c] != '1':
            return
        grid[r][c] = '0'               # visited = sunk, in place
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

§GR.3 · TYPE B

Multi-source BFS — layers as time

Brute force: simulate minute-by-minute, re-scanning the whole grid per minute → O((mn)²) when rot crawls one cell a minute.

Redundancy: re-scanning cells whose state cannot change this minute. Only the frontier — last minute's newly rotten — can rot anything.

Insight: seed the queue with every rotten orange at time 0 — multi-source BFS behaves as if a virtual super-source connected to all of them. A fresh orange's rotting time = its BFS distance to the nearest initial rot, because rot advances exactly one layer per minute (the layer invariant of §GR.1, read as a clock). The frozen-layer loop is §TR.3's snapshot, verbatim.

def orangesRotting(grid):
    m, n = len(grid), len(grid[0])
    queue, fresh = deque(), 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:             # `and fresh`: no final empty layer
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2   # mark ON enqueue
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

§GR.4 · TYPE C

Topological sort — Kahn's algorithm

Reframe: finishable ⟺ the prerequisite graph has no cycle — a cycle is a set of courses each waiting on another, forever.

Kahn's derivation: a course with indegree 0 has no unmet prerequisite — take it now (safe by exchange: any valid order can be rearranged to put an available course first without breaking anything, §G.1's argument on orderings). Taking it decrements its dependents' indegrees; whoever hits 0 becomes available. The queue is just the availability set.

Cycle detection for free: every member of a cycle has an in-cycle predecessor that is never processed, so its indegree never reaches 0 and it never enters the queue. Hence processed < n ⟺ cycle — the leftover count IS the detector.

def canFinish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for course, pre in prerequisites:
        adj[pre].append(course)        # pre ──▶ course
        indeg[course] += 1
    queue = deque(i for i in range(numCourses) if indeg[i] == 0)
    done = 0
    while queue:
        u = queue.popleft()
        done += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return done == numCourses

§GR.5 · TYPE D

Dijkstra — the settle proof

Brute force: enumerate paths — exponential. Bellman-Ford relaxes all edges V−1 times → O(VE), correct but ignores an ordering gift.

Redundancy: re-relaxing nodes whose distance is already provably final.

The settle proof — LC 373's frontier argument, promised in §H.4, now on graphs: pop the frontier node u with the smallest tentative distance d. Any other route to u must leave the settled set through some frontier node with tentative ≥ d, and every additional edge adds ≥ 0 — so no route can undercut d. Popping = settled, permanently. Non-negativity is where the proof spends its assumption; that's the hidden requirement, not a footnote.

Lazy deletion (§H.7's decrease-key workaround): push improved (dist, node) duplicates freely; on pop, a node already settled is stale — skip it. The check-then-settle ordering is load-bearing.

def networkDelayTime(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = {}                          # settled nodes only
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                   # stale duplicate — lazy deletion
        dist[u] = d                    # settle: the proof happened here
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

§GR.6 · TYPE E · THE BOSS

Build the graph, then sort it

Why it's the boss: the graph isn't given — extracting it correctly IS the problem; the topo sort afterward is §GR.4 verbatim.

Edge extraction, derived: two adjacent sorted words agree on a prefix; their first differing characters a, b certify a < b — one edge, a→b. Characters after the first difference certify nothing (sorted order is decided at the first difference; everything later is noise). Non-adjacent word pairs add nothing: sortedness is transitive through the neighbors between them.

The impossibility case that isn't a cycle: ["abc", "ab"] — a word before its own proper prefix. No edge expresses that contradiction; it must be caught explicitly during extraction.

def alienOrder(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:    # dedup — or indegree inflates
                    adj[a].add(b)
                    indeg[b] += 1
                break
        else:                          # no difference found
            if len(w1) > len(w2):
                return ""              # word precedes its own prefix
    queue = deque(c for c in indeg if indeg[c] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return "".join(order) if len(order) == len(adj) else ""

When this feels derivable — first-difference certificates, the prefix contradiction, then Kahn's on autopilot — the set is yours. The general skill: many "hard graph" problems are ordinary traversals behind a non-obvious graph construction.

§GR.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• No visited set — the tree habit (§TR) meeting its first cycle loops forever
• Marked visited on DEQUEUE — grid cells enter the queue up to 4×; correct output, bloated memory; mark on enqueue
• BFS on weighted edges — the layer invariant is gone; Dijkstra (non-negative) or deque BFS (0/1 weights)
• Dijkstra with a negative edge — the settle proof dies; a node settles before its true shortest path exists
• Dropped the stale-skip (if u in dist: continue) — later, larger pops overwrite settled distances: wrong answers, not just slow
• Kahn's without the final count check — cycles quietly emit a partial order ([[1,0],[0,1]])
• Prerequisite edges built backward — pre → course, not course → pre
• Alien Dictionary: missed the prefix rule (["abc","ab"] → "") or skipped edge dedup (indegree inflates, valid input returns "")
• Deep grid DFS recursion (300×300 all-land ≈ 9·10⁴ frames) — go iterative; and mutating the grid as visited without asking
• Edges added over time / connectivity-only queries — that's Union-Find (Set 11), not repeated BFS

Signals → pattern (added to the drill deck in §3.2)

"connected regions / islands / provinces"        → flood fill — each fresh start is one component
"spread / infection / nearest X, unit steps"     → multi-source BFS, layers = time
"prerequisites / build order / can it finish"    → Kahn's topo sort — leftovers certify the cycle
"shortest path, weighted, non-negative"          → Dijkstra: lazy deletion, settle at pop
"recover an order from sorted examples"          → extract first-difference edges, then topo
"cheapest path with ≤ k stops / negative edges"  → Bellman-Ford relaxation — Dijkstra's proof breaks

Interrogation — answer in your journal

§K.1 · SET 10 — BACKTRACKING

Theory

Redundancy it kills — two, and both matter:

• Completing dead candidates: generate-then-filter builds every complete candidate (2ⁿ subsets, n! orderings) and tests each — but a partial candidate that already violates a constraint dooms every one of its completions. Pruning at the first violation discards the whole subtree in one comparison.
• Rebuilding shared prefixes: sibling candidates share almost their entire prefix. Copying state per candidate re-pays that prefix every time; backtracking keeps one mutable path and moves along the tree edge by edge — O(1) per choose/unchoose.

So: backtracking = DFS over the implicit tree of partial candidates, plus pruning, plus undo. The skeleton:

def backtrack(path, choices):
    if complete(path):
        results.append(path[:])        # COPY — the path is shared
        return
    for c in candidates(choices):      # the branching rule
        if not viable(c, path):        # prune BEFORE descending
            continue
        path.append(c)                 # choose
        backtrack(path, updated)       # explore
        path.pop()                     # unchoose — restore exactly

Complexity tell: O(branching^depth), refined to O(nodes surviving the prune × per-node cost) — and output-sensitive: at minimum O(#answers × answer length), because the leaf copy costs O(n). Count the copy; most people forget it.

§K.2 · TYPE A

Subsets — the start-index archetype

The canonical-order derivation: a subset equals a strictly increasing sequence of indexes — a unique canonical form (§B.3 again). Generate exactly those: from position start, choose any later index, recurse from just past it. Each subset is produced once because each increasing index sequence is produced once — no dedup, no visited set, by construction.

Every node of this tree IS an answer (subsets of every size), so the collect happens at every call, not just leaves.

def subsets(nums):
    res, path = [], []
    def backtrack(start):
        res.append(path[:])            # every node is an answer
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return res

§K.3 · TYPE B

Target-driven pruning with reuse

Two levers on top of Type A:

• Reuse: recurse with start = i, not i+1 — the current candidate may appear again, but nothing earlier may, preserving the canonical non-decreasing order (each combination generated once).
• The sorted break-prune: sort first; when a candidate exceeds the remaining target, break, don't continue — sortedness certifies every later candidate also exceeds it (§BS.1's monotonic discard, inside a loop). One comparison kills the rest of the level and all their subtrees.

def combinationSum(candidates, target):
    candidates.sort()                  # enables break, not continue
    res, path = [], []
    def backtrack(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break                  # sorted: all later ones too big
            path.append(candidates[i])
            backtrack(i, remain - candidates[i])   # i, not i+1: reuse
            path.pop()
    backtrack(0, target)
    return res

§K.4 · TYPE C

Permutations with duplicates — the same-level skip

Brute force: generate all n! permutations (LC 46 with a used[] array), dedup through a set → O(n! · n) plus hashing, and the duplicate subtrees were fully explored before being thrown away.

Redundancy: two equal values swapped produce identical subtrees — the entire subtree is re-explored once per ordering of the equal copies.

The rule, derived: sort, then at each level skip nums[i] when nums[i] == nums[i−1] and used[i−1] is False. Meaning: among equal copies, a copy may enter the path only if the previous copy is already in it — equal copies are consumed in index order, one canonical ordering survives, so each distinct permutation is generated exactly once. It's a canonical form imposed at the point of divergence, pruning duplicates before they cost anything.

def permuteUnique(nums):
    nums.sort()                        # the skip rule needs equal values adjacent
    res, path = [], []
    used = [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue               # equal copies: index order only
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False            # both undos — symmetric restore

§K.5 · TYPE D

Grid backtracking — path-visited, then undone

The conceptual hinge of this set: Set 09's visited set is traversal-visited — permanent, because "reached once" answers reachability forever. Here a cell is blocked only while it's on the current path: a different path may legally reuse it. So the mark must be undone on exit — path-visited. Confusing the two breaks both directions: permanent marks here miss valid words (a failed probe poisons later probes); undo-marks in flood fill (§GR.2) go quietly exponential.

The prune: mismatch at character k kills the subtree immediately — 3 branches per step after the first (never walk back into the cell you came from — it's marked).

def exist(board, word):
    m, n = len(board), len(board[0])
    def dfs(r, c, k):
        if k == len(word):
            return True
        if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[k]:
            return False
        board[r][c] = '#'              # path-visited
        found = (dfs(r+1, c, k+1) or dfs(r-1, c, k+1) or
                 dfs(r, c+1, k+1) or dfs(r, c-1, k+1))
        board[r][c] = word[k]          # undo — other paths may need this cell
        return found
    return any(dfs(r, c, 0)
               for r in range(m) for c in range(n))

§K.6 · TYPE E · THE BOSS

N-Queens — constraint sets

Brute force: choose n cells from n² → C(n², n) candidates; even one-per-row placement without pruning is nⁿ with O(n) validity scans per node.

Two derivations do all the work:

• Canonical order: every solution has exactly one queen per row — so place row by row. The branching collapses from "any cell" to "which column in this row": nⁿ shape, and the row constraint holds by construction.
• O(1) validity via the diagonal identities: cells on the same "\" diagonal share a constant r − c; on the same "/" diagonal, constant r + c (derive: moving one step down-right changes r and c by +1 each — difference invariant; down-left changes them oppositely — sum invariant). Three hash sets — cols, r−c, r+c — replace the O(n) board scan. §B.1's payload question, answered with set-membership.

def solveNQueens(n):
    res, board = [], []                # board[r] = column of the queen in row r
    cols, diag, anti = set(), set(), set()
    def place(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue               # prune before choosing
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board.append(c)
            place(r + 1)
            board.pop()
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)
    place(0)
    return res

When this feels derivable — canonical order collapses a dimension, algebraic identities make validity O(1), every choose mirrored — the set is yours. Same species: Sudoku Solver (LC 37), Palindrome Partitioning (LC 131).

§K.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• res.append(path) without the copy — every collected answer aliases ONE list; results end up identical/empty. THE backtracking bug, Python and JS alike
• Asymmetric choose/unchoose — an early return or prune between append and pop leaks state into every later branch
• Permanent visited in Word Search — a failed probe poisons later probes; path marks must be undone
• The reverse: undo-marking in flood fill (§GR.2) — quietly exponential; reachability marks are permanent
• LC 39: passed i+1 (killed legal reuse) or LC 40: passed i (illegal reuse) — know which lever is which
• Skip rule without the sort — [1,2,1] leaves equal values non-adjacent and duplicates leak through
• continue where sorted order justified break — correct but forfeits the level-wide prune
• Building path + [c] / s + ch per node instead of mutate-and-undo — an O(n) allocation on every node of an exponential tree
• Only a count or best value is asked and subproblems overlap — that's DP (Set 12); backtracking enumerates, DP aggregates
• Didn't say the output bound out loud — subsets are Θ(2ⁿ), permutations Θ(n!); no algorithm beats its own output size

Signals → pattern (added to the drill deck in §3.2)

"all subsets / combinations / partitions"      → start-index backtracking, canonical order
"combination sum, reuse allowed"               → recurse with i (not i+1), sort + break prune
"all permutations, input has duplicates"       → sort + same-level skip (not used[i-1] ⇒ skip)
"trace a word / path through a grid"           → DFS: mark, recurse, UNMARK
"place n pieces under mutual constraints"      → row-by-row + O(1) constraint sets
"count ways / best value only, no listing"     → DP, not backtracking — enumerate vs aggregate

Interrogation — answer in your journal

§U.1 · SET 11 — UNION-FIND & TRIE

Theory

One economy, two structures: pay a small maintenance cost on every update so a repeated question becomes nearly free.

• Union-Find kills: re-running BFS/DFS per connectivity query. Static connectivity is Set 09's job — but when edges arrive over time, re-traversing costs O(V+E) per query, O(q(V+E)) total (§GR.7 named this trap). The DSU maintains the partition as data: find + union in amortized near-O(1).
• Trie kills: re-comparing shared prefixes. A hashset compares whole keys and — being exact-equality-only (§B.1's limit) — cannot answer "does any word start with X?" at all. The trie stores every shared prefix once; a query walks it once.

The DSU skeleton (path compression + union by size — both, always):

parent = list(range(n))
size = [1] * n
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path halving — compress as you go
        x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                    # already connected — a cycle signal
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                     # link ROOTS, never raw nodes
    size[ra] += size[rb]
    return True

Complexity tells: DSU: m operations on n elements → O(m α(n)) — inverse Ackermann, ≤ 4 for any physically possible n; say "amortized, effectively constant, formally α(n)" — precision is the senior signal. Trie: every operation is O(L) in the key length, independent of dictionary size n — ask "does my cost scale with how many words, or how long the query?" — that question picks the structure.

§U.2 · TYPE A

Counting components by union

Honest framing: this input is static, so §GR.2's flood fill also works — this is the DSU hello-world, and the counting idea is what transfers: start with n components; every union that succeeds merges two into one, so count −= 1 per successful union. No recount, ever — the running count is exact by induction.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    size = [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    count = n
    for i in range(n):
        for j in range(i + 1, n):      # symmetric matrix: upper half only
            if isConnected[i][j]:
                ri, rj = find(i), find(j)
                if ri != rj:
                    if size[ri] < size[rj]:
                        ri, rj = rj, ri
                    parent[rj] = ri
                    size[ri] += size[rj]
                    count -= 1
    return count

§U.3 · TYPE B

The failed union is the answer

Brute force: for each edge, remove it and BFS the rest for connectivity + acyclicity → O(E²).

The derivation: feed edges through the DSU in order. While the structure is a forest, every edge joins two different roots and the union succeeds. The moment an edge arrives whose endpoints already share a root, a path between them exists — adding this edge closes the (unique) cycle. With exactly one extra edge, exactly one union fails, and that edge is the answer. Find-before-union is the check-before-insert ordering (§1.4) — query the state, then mutate it.

def findRedundantConnection(edges):
    parent = list(range(len(edges) + 1))   # nodes are 1..n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]              # closes the cycle — the answer
        parent[rb] = ra

§U.4 · TYPE C

Union over arbitrary keys

The recognition step: "shares an email with" generates an equivalence relation over accounts (transitive through chains: A–B via one email, B–C via another ⇒ A–C). Equivalence classes under growing evidence = DSU, verbatim.

Brute force: repeatedly scan account pairs for shared emails and merge until fixed point → O(n² · emails) with set intersections, re-discovering the same links per pass.

Mechanics worth naming: DSU over strings — either hash each email to an integer id, or parent as a dict keyed by email (below). Union each account's emails to its first email; then one pass groups every email under its root. The root is the canonical representative doing exactly §B.3's canonical-key job.

def accountsMerge(accounts):
    parent = {}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        parent.setdefault(a, a)
        parent.setdefault(b, b)
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
    email_name = {}
    for acc in accounts:
        for email in acc[1:]:
            email_name[email] = acc[0]
            union(acc[1], email)       # everything unions to the first email
    groups = {}
    for email in parent:
        groups.setdefault(find(email), []).append(email)
    return [[email_name[root]] + sorted(g) for root, g in groups.items()]

§U.5 · TYPE D

The trie — prefixes stored once

Brute force: a list of words — startsWith scans all n words × L chars → O(n·L) per query. A hashset fixes exact search but cannot answer startsWith at all (exact equality only).

Redundancy: ["apple", "apply", "applied"] store "appl" three times and every prefix query re-compares it. In the trie each prefix exists once as a path; both queries are the same walk, differing only in what they require at the end — which is why the end-of-word marker is load-bearing: without it, inserting "apple" makes search("app") wrongly True.

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True               # end marker: word, not just prefix
    def search(self, word):
        node = self._walk(word)
        return node is not None and '$' in node
    def startsWith(self, prefix):
        return self._walk(prefix) is not None
    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

§U.6 · TYPE E · THE BOSS

Trie + backtracking — all words at once

Brute force: run LC 79 (§K.5) per word → O(W · mn · 3^L). The promised upgrade arrives here.

Redundancy: words sharing prefixes force the board to re-walk identical paths once per word — "cat" and "car" walk c→a twice.

Insight: put the dictionary in a trie and walk board and trie in lockstep — one DFS explores all words simultaneously; a board path dies the moment no dictionary word continues it (dead trie node = the prune). Two refinements that interviewers watch for: pop '$' on collection (each word reported once, however many paths spell it), and delete emptied trie branches so exhausted words stop guiding the search.

def findWords(board, words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w                  # store the word at its end node
    m, n = len(board), len(board[0])
    res = []
    def dfs(r, c, node):
        if not (0 <= r < m and 0 <= c < n):
            return
        ch = board[r][c]
        nxt = node.get(ch)             # '#' is never a trie key
        if nxt is None:
            return                     # no word continues — prune
        word = nxt.pop('$', None)
        if word is not None:
            res.append(word)           # popped: reported exactly once
        board[r][c] = '#'              # path-visited (§K.5)
        dfs(r+1, c, nxt); dfs(r-1, c, nxt)
        dfs(r, c+1, nxt); dfs(r, c-1, nxt)
        board[r][c] = ch
        if not nxt:
            del node[ch]               # emptied branch: shrink the trie live
    for r in range(m):
        for c in range(n):
            dfs(r, c, root)
    return res

When this feels derivable — dictionary as a trie, lockstep walk, prune at dead nodes, pop to dedup, delete to shrink — the set is yours. This is also the cleanest example of the lab's meta-lesson: two patterns composed (Set 10's backtracking + this set's trie) beat either alone.

§U.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• No compression AND no by-size union — sequential unions build a chain; find degrades to O(n), the whole run to a quiet O(n²)
• Linked raw nodes instead of roots (parent[b] = a) — corrupts the forest and the size table
• Recursive find — a 10⁵ chain overflows the stack before compression can help; write it iteratively (§TR's caveat, third appearance)
• DSU where edges get DELETED — wrong tool; connectivity must only grow
• Trie without the end marker — insert "apple", search("app") wrongly True; prefix ≠ word
• '$'-sentinel leaking into child iteration — guard every loop over node keys
• LC 212 as a per-word LC 79 loop — a quiet W× blowup; and without the '$'-pop, duplicated results
• Trie for exact-membership-only workloads — the hashset wins on constants and memory; the trie earns its keep only when prefixes matter
• Claimed "O(1)" for DSU ops — it's amortized α(n); say inverse Ackermann and that it's ≤ 4 in practice

Signals → pattern (added to the drill deck in §3.2)

"are X and Y connected, edges arriving over time"  → union-find — amortized α(n)
"count groups/components as things merge"          → DSU: count −= each successful union
"which edge creates a cycle"                       → the first union that returns False
"merge records sharing any identifier"             → hash to ids → union → group by root
"dictionary + prefix queries / autocomplete"       → trie — O(L), independent of word count
"many words searched in one grid"                  → trie + backtracking, lockstep walk

Interrogation — answer in your journal

§D.1 · SET 12 — DP I: 1D · GRID · KNAPSACK

Theory

Redundancy it kills: re-solving overlapping subproblems. Set 10's recursion tree contains the same subproblem over and over — fib(n)'s tree has ~2ⁿ nodes but only n distinct states; coin-change's tree explodes while only (amount) distinct remainders exist. DP collapses the tree onto the DAG of distinct states: each state solved once, then reused.

The identity worth journaling: DP = path counting / shortest-longest paths on a DAG. States are nodes, transitions are edges, and a valid iteration order is a topological order (§GR.4). Memoized recursion is DFS post-order over the same DAG (§TR.1's "children before parent"). You already know both machines; DP is choosing what the nodes mean.

The five-step derivation discipline (this replaces "seeing the trick"):

1. State, in words: "dp[i] = the answer for the problem restricted to …" — one precise sentence.
2. Recurrence: condition on one decision (the last step, take-or-skip the last item).
3. Base cases: the states where the recurrence can't fire.
4. Order: top-down memo, or a loop order whose dependencies are already final.
5. Space: if dp[i] reads only a fixed window, keep the window (rolling variables/row).

Complexity tell: #states × work per transition. n items × target T ⇒ O(n·T) — and say the word pseudo-polynomial: T is a value, not an input size; at T = 10⁹ the "polynomial" DP is dead and you need math/greedy/BFS instead. Constraint smell: n ≤ 10³ with target ≤ 10⁴ is the interviewer telling you O(n·T) is intended.

§D.2 · TYPE A

The 1D archetype

Easy-tier, included because it IS the archetype — the five steps on the smallest possible problem.

The derivation: (1) dp[i] = number of ways to stand on step i. (2) Condition on the last move: it was a 1-step from i−1 or a 2-step from i−2, and the ways are disjoint → dp[i] = dp[i−1] + dp[i−2]. (3) dp[0] = dp[1] = 1 (one way to be at the start: do nothing — the {0:1}-style empty seed). (4) Increasing i. (5) Only a two-state window is read → two variables.

def climbStairs(n):
    a, b = 1, 1                        # ways(0), ways(1)
    for _ in range(2, n + 1):
        a, b = b, a + b                # roll the window
    return b

§D.3 · TYPE B

Folding a constraint into the state

Brute force: every independent subset of houses → 2ⁿ, Set 10 style.

The state-design lesson: the adjacency constraint means "how much did I steal" isn't enough — the future needs to know whether the previous house was robbed. That's the Markov property speaking: fold the constraint into the state. Two accumulators — best ending in a rob, best ending in a skip — carry exactly the needed bit.

Recurrence: rob i ⇒ previous must be a skip: take′ = skip + nums[i]. Skip i ⇒ previous was either: skip′ = max(take, skip). Conditioning on one decision, twice.

def rob(nums):
    take = skip = 0                    # best ending with rob / with skip
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

§D.4 · TYPE C

Unbounded knapsack — and greedy's grave

Why greedy dies here (say this unprompted): coins [1, 3, 4], amount 6 — largest-first gives 4+1+1 = 3 coins; optimal is 3+3 = 2. No exchange argument exists: swapping a big coin for smaller ones changes the remaining capacity structure, so no local swap is provably safe (§G.1's rule: no proof, no greedy). This is the canonical boundary marker between Sets 08 and 12.

The derivation: dp[t] = fewest coins for amount t. Condition on the last coin c: dp[t] = 1 + min over c of dp[t−c]. Base dp[0] = 0; unreachable stays ∞.

def coinChange(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for t in range(1, amount + 1):
        for c in coins:
            if c <= t and dp[t - c] + 1 < dp[t]:
                dp[t] = dp[t - c] + 1
    return dp[amount] if dp[amount] < INF else -1

§D.5 · TYPE D

Grid DP — counting with a rolling row

The derivation: dp[r][c] = paths reaching (r, c). Condition on the last move — it came from above or from the left, disjointly → dp[r][c] = dp[r−1][c] + dp[r][c−1]. First row and column: exactly one path each (all-right / all-down). Counting uses +, optimizing uses max/min — same skeleton, different monoid; mixing them up is a real bug.

Space: each cell reads only the current and previous rows → keep one row and fold in place: row[c] += row[c−1] reads row[c] as "up" (previous row's value, not yet overwritten) and row[c−1] as "left" (already updated) — the in-place trick IS a dependency-order proof in miniature.

def uniquePaths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]       # up (old value) + left (new value)
    return row[-1]

§D.6 · TYPE E

0/1 knapsack — the reversed loop, proved

Reframe: total odd → impossible; else: can some subset hit total/2? — subset-sum, the canonical 0/1 knapsack (each item used at most once).

The loop-order proof (the most important two lines in DP I): dp[t] = "t reachable with items so far". Adding item x: dp[t] |= dp[t−x]. Iterate t downward: dp[t−x] then still holds the previous item set's value — x can't feed itself. Iterate upward and dp[t−x] may already include x — the single 3 in nums=[3] marks dp[3] then dp[6]: one item used twice. The direction of a loop is enforcing "read the old state before writing the new" — the check-before-insert discipline (§1.4) expressed as an iteration order.

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for t in range(target, x - 1, -1):   # DOWNWARD: each item once
            if dp[t - x]:
                dp[t] = True
    return dp[target]

§D.7 · TYPE F · THE BOSS

When forward state fails — DP from the exit

Why the obvious DP is wrong (this is the whole problem): walking forward, a path's quality is TWO numbers — health accumulated so far AND the worst dip along the way — and they conflict: one forward path may have more current health, another a gentler dip, and either could win later. No single forward scalar is sufficient — a concrete Markov property violation (§D.1). More state won't save it cheaply; changing direction will.

The backward reframe: define need[r][c] = minimum health entering (r, c) that suffices to reach the princess. From (r, c) you'll take the cheaper onward branch: need = min(need[r+1][c], need[r][c+1]) − dungeon[r][c], clamped at max(1, ·) — health may never sit below 1, and surpluses don't carry backward (the clamp is a discard: excess future headroom cannot reduce what you must arrive with). The future is now a single summarizable number — Markov restored by reversing time.

def calculateMinimumHP(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    need = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    need[m][n - 1] = need[m - 1][n] = 1    # sentinels: exit alive with ≥ 1
    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            best = min(need[r + 1][c], need[r][c + 1])
            need[r][c] = max(1, best - dungeon[r][c])
    return need[0][0]

When this feels derivable — spot the two-number conflict, flip the direction, clamp as discard — the set is yours. LC 139 (Word Break) and LC 91 (Decode Ways) are the ladder's connective tissue on the way here.

§D.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• 0/1 knapsack with a FORWARD inner loop — nums=[3], target 6: one item used twice; downward = use-once
• Counting loop order: coins-outer counts combinations (LC 518), amount-outer counts permutations (LC 377) — [1,2]→3 gives 2 vs 3
• Missing dp[0] = 1 seed in counting DP — "one empty way" is load-bearing, the {0:1} of §1.4 again
• Sequential instead of simultaneous update in rolled DP — take reads the NEW skip; use tuple assignment / a temp
• INF + 1 overflow in Java/C++ (MAX_VALUE wraps negative) — guard before adding; Python is immune, say so
• @lru_cache on list-typed state — unhashable; convert to tuples (§B.1's hashability)
• Top-down at 10⁴+ depth — recursion limit; go bottom-up (§TR's caveat, again)
• Called O(n·T) "polynomial" — it's pseudo-polynomial; T = 10⁹ kills it and the interviewer knows
• State too small — circular robber (LC 213), dungeon forward: wrong answers, not slowness; audit the Markov property
• DP where greedy has a proof (interval scheduling §G.3) — correct but slower and it signals you can't tell them apart

Signals → pattern (added to the drill deck in §3.2)

"count ways to reach / climb / decode"        → 1D DP, condition on the last step, dp[0]=1
"max/min with adjacency or usage limits"      → fold the constraint into the state (take/skip)
"fewest coins/items to hit a target, reuse"   → unbounded knapsack — forward loop
"can a subset hit a target, each item once"   → 0/1 knapsack — REVERSED inner loop
"count / best paths in a grid"                → grid DP, rolling row; + for count, min/max for best
"minimum starting resource to survive"        → backward DP from the exit, clamp at the floor

Interrogation — answer in your journal

§X.1 · SET 13 — DP II (SUBSEQUENCES) & DP III (STATE MACHINES)

Theory

Two redundancies, two state designs:

• DP II kills: enumerating subsequences — 2ⁿ per string — when the future of a comparison depends only on positions, never on which characters got matched. The pair-of-prefixes state (i, j) collapses a 2ⁿ × 2ᵐ candidate space onto an n·m grid.
• DP III kills: re-deriving "what situation am I in" per step. When the situation is one of finitely many modes (holding a stock, in cooldown, free), carry one optimum per mode per day — the state machine is a layered DAG, day-layers × modes, and the DP is literally longest-path on it (§D.1's identity, drawn).

The DP II skeleton (LCS form — the grid everything else decorates):

dp = [[0] * (m + 1) for _ in range(n + 1)]   # dp[i][j]: answer for s1[:i], s2[:j]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s1[i - 1] == s2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1  # both last chars consumed
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Complexity tells: pair-of-prefixes ⇒ O(n·m) time, rollable to O(m) space. Day × modes ⇒ O(n·k) with k a small constant ⇒ O(n). LIS: O(n²) grid-thinking, O(n log n) with binary search inside the DP.

§X.2 · TYPE A

Longest common subsequence — the archetype grid

Brute force: enumerate one string's 2ⁿ subsequences, check each against the other → O(2ⁿ · m).

The conditioning move, proved: look at the last characters of both prefixes.

• Equal: take the match — dp[i−1][j−1] + 1. Never skip a match (exchange argument: any optimal solution not using this pair can be rewritten to use it, at no loss — pair the last equal chars instead of whatever it matched them to).
• Unequal: the two last chars cannot both end a common subsequence, so at least one is disposable — every common subsequence of (i, j) survives inside (i−1, j) or (i, j−1). Dropping one each way and taking the max is exhaustive AND safe; that's the whole correctness proof.

def longestCommonSubsequence(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

§X.3 · TYPE B

LIS — and the binary-search upgrade

Round 1 — the O(n²) DP: dp[i] = LIS ending exactly at i = 1 + max over j < i with nums[j] < nums[i]. The "ending at" state is the trick to remember: it makes the recurrence local.

Round 2 — patience: keep tails, where tails[k] = the smallest possible tail of any increasing subsequence of length k+1. Two proofs make it work:

• tails is always strictly increasing: if tails[a] ≥ tails[b] for a < b, then the length-(b+1) subsequence's first a+1 elements end in something < tails[b] ≤ tails[a] — a better length-(a+1) tail, contradiction.
• Processing x: replace the first tail ≥ x (a lower bound — §BS.3, verbatim): x extends everything shorter and is a cheaper tail for that length. Appending when no tail ≥ x means x extends the longest — length grows.

from bisect import bisect_left

def lengthOfLIS(nums):
    tails = []                     # tails[k] = min tail of an IS of length k+1
    for x in nums:
        i = bisect_left(tails, x)  # lower bound — strict increase
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

§X.4 · TYPE C

Edit distance — three-way conditioning

The derivation: condition on how the last characters get resolved. Equal → free, diagonal. Unequal → exactly one of three last operations happened: delete w1's last (dp[i−1][j] + 1), insert w2's last (dp[i][j−1] + 1), or replace (dp[i−1][j−1] + 1). The three neighbors of the grid cell ARE the three operations — exhaustive by construction. Base cases: row 0 = build by j inserts, column 0 = erase by i deletes.

def minDistance(w1, w2):
    n, m = len(w1), len(w2)
    dp = list(range(m + 1))            # row 0: j inserts build w2[:j]
    for i in range(1, n + 1):
        prev = dp[0]                   # carries dp[i-1][j-1]
        dp[0] = i
        for j in range(1, m + 1):
            cur = dp[j]
            if w1[i - 1] == w2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j - 1])
            prev = cur
    return dp[m]

§X.5 · TYPE D

Interval DP on one string

Two routes, know both: the transform (§1.7's move): LPS(s) = LCS(s, reverse(s)) — one line of insight and Type A does the rest. And the direct interval DP, worth coding because window-shaped states recur (burst balloons, matrix chains): dp[i][j] = LPS inside s[i..j]. Ends equal → both join: 2 + dp[i+1][j−1]. Unequal → at least one end is disposable (same disposability proof as Type A): max(dp[i+1][j], dp[i][j−1]).

The order proof: a window depends only on shorter windows — iterate i descending, j ascending, and both dependencies (i+1 row, j−1 column) are final when read. Choosing the loop order by asking "what must already be final?" is §D.1's step 4 in its purest form.

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):     # i descending: row i+1 is final
        dp[i][i] = 1
        for j in range(i + 1, n):      # j ascending: dp[i][j-1] is final
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

§X.6 · TYPE E · DP III

The stock state machine

Draw the machine first — it IS the solution: three modes: hold (own the stock), sold (sold today — cooling), rest (free to buy). Transitions per day, each justified:

• hold(t) = max(hold(t−1), rest(t−1) − p) — keep holding, or buy; buying requires yesterday free, not cooling — that's where the cooldown constraint lives, in the edge, not in extra state.
• sold(t) = hold(t−1) + p — selling requires holding.
• rest(t) = max(rest(t−1), sold(t−1)) — cooling ends after exactly one day.

One optimum per mode per day is sufficient — the Markov audit (§D.1): the future needs your mode and profit, nothing else about history.

def maxProfit(prices):
    hold, sold, rest = float('-inf'), 0, 0
    for p in prices:
        hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
    return max(sold, rest)             # never end holding

§X.7 · TYPE F · THE BOSS

Counting on the grid

Brute force: enumerate s's 2ⁿ subsequences, compare each to t.

The derivation: dp[i][j] = ways s[:i] contains t[:j]. Condition on whether s's last character participates: it never has to (dp[i−1][j]); it can pair with t's last only when they match (+ dp[i−1][j−1]). Counting ⇒ the branches add (disjoint by "does s[i−1] match t's end or not"). Base dp[i][0] = 1 — one way to contain the empty string — the {0:1} seed carrying a whole hard problem.

Rolling exposes the boss move: one row, inner loop downward — dp[j−1] must still be the previous row's value or s's character feeds its own update. This is §D.6's reversed-loop proof, resurfacing because counting (unlike min in Coin Change) is not idempotent — duplicates corrupt sums.

def numDistinct(s, t):
    n, m = len(s), len(t)
    dp = [1] + [0] * m                 # dp[j]: ways vs t[:j]; dp[0] = empty seed
    for i in range(1, n + 1):
        for j in range(m, 0, -1):      # DOWNWARD: dp[j-1] is the old row
            if s[i - 1] == t[j - 1]:
                dp[j] += dp[j - 1]
    return dp[m]

When this feels derivable — participation conditioning, the additive split, the seed, the downward roll — both DP sets are yours. The full arc from §D.2 to here is the same five steps at increasing state sophistication; that arc, not any single recurrence, is what transfers to unseen problems.

§X.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• dp[i] ↔ s[i−1] mapping slipped — the (n+1) grid pairs cell i with character i−1; fix the contract before writing cells
• Subsequence vs SUBSTRING — LC 516 vs LC 5: gaps allowed vs contiguous, different recurrences entirely
• bisect_left vs bisect_right — strict vs non-decreasing LIS; [2, 2] answers 1 vs 2; ask the duplicates policy
• Treated tails as an actual LIS — it's length evidence only; reconstruction needs parent links
• Rolled a grid and lost the diagonal — edit distance needs the prev temp; overwrite-then-read is the silent killer
• LC 115 with an ascending inner loop — s = "aaa", t = "aa" over-counts; counting isn't idempotent (§D.6's proof, again)
• State machine with sequential assignment — a mode reads today's value instead of yesterday's; tuple-assign or temps
• hold initialized to 0 — sells stock never bought; −∞ or first-day buy
• "Is t a subsequence of s?" solved with a grid — that's a two-pointer O(n) scan (LC 392, §T); don't DP what a scan answers
• Java: counting overflow (use long / take the modulus); O(n·m) at 10⁵ × 10⁵ — 10¹⁰ cells, find the O(n log n) or greedy escape

Signals → pattern (added to the drill deck in §3.2)

"longest common subsequence / min supersequence"  → pair-of-prefixes grid, empty row-0 seed
"longest increasing subsequence"                  → O(n²) 'ending-at' DP → patience + lower_bound
"min operations to transform one string"          → 3-way conditioning — the neighbors ARE the ops
"palindromic SUBSEQUENCE"                         → interval DP by window size, or LCS vs reverse
"stock trading with cooldowns / fees / k trades"  → state machine — one optimum per mode per day
"count ways one string contains another"          → counting grid: +, seed dp[i][0]=1, roll downward

Interrogation — answer in your journal

§V.1 · SET 14 — DESIGN DATA STRUCTURES

Theory

Redundancy it kills: design problems hand you an operations contract — a class where every method must hit a per-op bound. The brute force uses one structure and pays a linear scan somewhere, and that scan always re-derives a fact (recency order, an element's position, the latest version ≤ t) that a second structure could have maintained incrementally. The pattern: compose structures so each maintains exactly the fact one operation needs, wired so every mutation updates every view in O(1).

The skeleton is a procedure, not code:

1. Write the contract as a table — op → required bound (and ask: amortized or worst-case?).
2. Per op, name the fact it needs instantly — membership? recency order? a random slot? latest ≤ t?
3. Pick the minimal structure per fact — hashmap = membership/location; doubly linked list = order with O(1) splice; array = O(1) random index; append-only sorted list = lower bound. This is §B.1's payload question promoted to whole structures.
4. Wire them — every mutation updates every view before returning.

Complexity tell: per-operation bounds, frequently amortized — the dynamic array's O(1) append is the doubling argument, and the queue-from-two-stacks is §2.2's charging argument in a new costume (each element pays for its own two moves). The giveaway phrasing: "implement a class supporting X, Y, Z in O(1)".

§V.2 · TYPE A

Snapshot pairing — Min Stack

Easy-tier, included because it IS the archetype: one auxiliary fact ("the min of everything below me") maintained per element.

Brute force: scan the stack on every getMin → O(n) per query.

The derivation: the min of a stack's contents is a prefix property — it depends only on the elements below, which never change while you're above them (LIFO's gift). So snapshot it: push (value, min-so-far). A popped snapshot can never be needed again, because the elements that produced it left with it. This is §1.1's prefix idea with min instead of sum, stored in the structure itself.

class MinStack:
    def __init__(self):
        self.stack = []                # (value, min of stack up to here)
    def push(self, val):
        m = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, m))
    def pop(self):
        self.stack.pop()
    def top(self):
        return self.stack[-1][0]
    def getMin(self):
        return self.stack[-1][1]

§V.3 · TYPE B

Array + map — the swap-with-last delete

Why one structure can't do it: a hashmap gives O(1) insert/remove but cannot be indexed uniformly (buckets are sparse and unordered); an array gives O(1) random access but O(n) deletes. Each structure covers the other's gap — the composition is forced by step 2 of §V.1.

The O(1) delete, derived: arrays delete cheaply only at the END. Any element can become the end: overwrite the victim's slot with the last element, then pop. The map (value → index) keeps positions honest. Update order is load-bearing: re-point the moved element's index before deleting the victim's entry — when the victim IS the last element (self-swap), the reverse order corrupts the map. The check-before-insert ordering discipline (§1.4), in structure-maintenance form.

class RandomizedSet:
    def __init__(self):
        self.arr = []
        self.idx = {}                  # value -> position in arr
    def insert(self, val):
        if val in self.idx:
            return False
        self.idx[val] = len(self.arr)
        self.arr.append(val)
        return True
    def remove(self, val):
        if val not in self.idx:
            return False
        i, last = self.idx[val], self.arr[-1]
        self.arr[i] = last             # tail fills the hole
        self.idx[last] = i             # BEFORE deleting val's entry
        self.arr.pop()
        del self.idx[val]
        return True
    def getRandom(self):
        return random.choice(self.arr)

§V.4 · TYPE C

Versioned reads — append + lower bound

Brute force: per get, scan all versions of the key → O(versions).

The gift in the contract (read the constraints!): timestamps are strictly increasing per the API — so appending keeps each key's version list sorted for free. Manufactured monotonicity (§BS.1's requirement, supplied by the problem), which turns get into a boundary search: the rightmost timestamp ≤ t is bisect_right − 1 (§BS.3's upper-bound sibling).

from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.store = {}                # key -> ([timestamps], [values])
    def set(self, key, value, timestamp):
        ts, vs = self.store.setdefault(key, ([], []))
        ts.append(timestamp)           # contract: strictly increasing
        vs.append(value)
    def get(self, key, timestamp):
        if key not in self.store:
            return ""
        ts, vs = self.store[key]
        i = bisect_right(ts, timestamp)   # first ts > t
        return vs[i - 1] if i else ""

§V.5 · TYPE D · THE MOST-ASKED

LRU Cache — hashmap + doubly linked list

The contract → the composition: O(1) lookup ⇒ hashmap. O(1) "move to most-recent" ⇒ a list you can splice anywhere in O(1) ⇒ doubly linked (unlinking needs the predecessor; the prev pointer IS the O(1) — a singly linked list pays O(n) to find it, an array pays O(n) to shift). O(1) eviction ⇒ the LRU end of that same list. Map values point at list nodes: the map answers where, the list answers when.

Two details that decide the interview: (1) a read is a use — get must move the node to the front, or recency is wrong (the classic failing trace lives in V3). (2) nodes carry their key — eviction discovers the victim via the list but must delete it from the map, and only the key unlocks that. Sentinels at both ends (§L.3's dummy, doubled) erase every empty/first/last edge case.

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                          # key -> node
        self.head, self.tail = Node(), Node()  # sentinels: MRU | LRU ends
        self.head.next, self.tail.prev = self.tail, self.head
    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._unlink(node)                     # a read IS a use
        self._push_front(node)
        return node.val
    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.val = value                   # update AND refresh recency
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]              # the key lives in the node
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

§V.6 · TYPE E · THE BOSS

LFU Cache — frequency buckets + a pointer that never searches

The contract's hard part: eviction needs "minimum frequency, then LRU among those" in O(1). A heap gives O(log n) and stale entries; the O(1) answer is one LRU list per frequency (each bucket is Type D's list, reused) plus a min_freq pointer.

Why min_freq never needs a search — the proof that makes this O(1): it changes in exactly two ways. (1) On insert, a frequency-1 key now exists → min_freq = 1, unconditionally. (2) On touch, the accessed key moves f → f+1; if it emptied bucket f and f was the min, nothing below f exists (f was minimal) and the departed key is now at f+1 → min_freq = f+1, a rise of exactly 1. Enumerate the cases, and the pointer is always right — a one-direction argument (§2.2's family) on a counter.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.vals = {}                          # key -> (value, freq)
        self.buckets = defaultdict(OrderedDict) # freq -> keys, LRU order
        self.min_freq = 0
    def _touch(self, key):
        val, f = self.vals[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1           # the only way it rises
        self.buckets[f + 1][key] = None
        self.vals[key] = (val, f + 1)
    def get(self, key):
        if key not in self.vals:
            return -1
        self._touch(key)
        return self.vals[key][0]
    def put(self, key, value):
        if self.cap == 0:
            return                              # the classic forgotten guard
        if key in self.vals:
            self._touch(key)
            self.vals[key] = (value, self.vals[key][1])
            return
        if len(self.vals) == self.cap:
            evict, _ = self.buckets[self.min_freq].popitem(last=False)
            del self.vals[evict]                # LRU within the min bucket
        self.vals[key] = (value, 1)
        self.buckets[1][key] = None
        self.min_freq = 1                       # a fresh key is always minimal

When this feels derivable — contract → facts → structures → wiring, with the min_freq proof replacing a search — the set is yours, and so is the atlas. Same species at scale: LC 355 (Design Twitter = hashmaps + §H.4's k-way merge), LC 1396, LC 895.

§V.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Partial update — mutated one view, forgot the other (arr popped, map stale): all views agree, audit every path
• LC 380 delete order — moved element's index must update BEFORE the victim's entry dies; removing the LAST element breaks the reverse order
• LRU get without move-to-front, or put-on-existing without a recency refresh — capacity-2 traces expose both
• No key inside the node — eviction finds the node but can't clean the map
• Singly linked list for LRU — unlink needs the predecessor: O(n); the prev pointer is the whole answer
• LFU: min_freq not reset to 1 on insert; capacity 0 unguarded; bucket eviction not LRU-ordered
• Time-based KV: assumed sorted timestamps without the contract saying so — bisect on unsorted data is silent garbage
• Claimed O(1) where it's amortized (append, two-stack queue) or average (hash ops) — name the right adjective, every time
• getRandom served from a hashmap alone — buckets can't be indexed uniformly; the array is not optional
• Language gaps: JS plain objects reorder integer-like keys (use Map); Python dict order is guaranteed only ≥ 3.7; Java LinkedHashMap needs accessOrder=true for LRU

Signals → pattern (added to the drill deck in §3.2)

"implement a class, every op O(1)"            → compose structures — one per fact, wire all views
"O(1) insert + delete + uniform random"       → array + map, swap-with-last delete
"cache evicting by recency"                   → hashmap + DLL with sentinels, move-to-front on use
"evict by frequency, ties by recency"         → per-frequency LRU buckets + min_freq pointer
"store versions, read the latest ≤ t"         → append-only per key + bisect_right − 1
"queue from stacks / amortized transfer"      → two containers, each element pays for its two moves

Interrogation — answer in your journal

§O.1 · SET 15 — ODDS & ENDS: DEQUE · QUICKSELECT · BITS · SAMPLING

Theory

This set is four specialists. Each replaces a general tool you already own with something strictly better in one narrow, recognizable situation — the skill is the recognition, because the general tool also works and costs you the follow-up:

• Monotonic deque replaces the heap for window extremes. The heap (§H) carries stale elements and pays log; the deque discards from both ends — dominated elements from the back (§S.1's shadow proof), expired elements from the front (§2.1's window) — the two discard rules this lab opened with, finally fused.
• Quickselect replaces sort for a single order statistic: partition once, discard a whole side.
• Bit algebra replaces bookkeeping structures when the fact needed is parity/pairing — XOR answers in O(1) space what a counting map answers in O(n).
• Math & sampling replace simulation and storage: squaring halves an exponent; a reservoir keeps a uniform sample of an unbounded stream in O(1) memory.

The flagship skeleton — the windowed monotonic deque:

dq = deque()                       # indices; values strictly decreasing
for i, x in enumerate(nums):
    while dq and nums[dq[-1]] <= x:
        dq.pop()                   # dominated: older AND ≤ x — never max again
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()               # expired by age
    if i >= k - 1:
        record(nums[dq[0]])        # front = window max

Complexity tells: deque → O(n) amortized; quickselect → T(n) = T(≈n/2) + O(n) → O(n) expected (a geometric series, derived in Type C); fast pow → the halving tell of §BS.1 → O(log n); reservoir → one pass, O(1) memory, unknown stream length.

§O.2 · TYPE A

XOR algebra

Easy-tier, included because it IS the archetype — three axioms do all the work.

The derivation: XOR is associative and commutative (reorder freely), self-inverse (a⊕a = 0), with identity 0 (a⊕0 = a). Fold the whole array: mentally reorder so pairs sit together — every pair annihilates to 0, and the singleton survives. The hashmap brute force is also O(n) time but O(n) space; the algebra is the bookkeeping.

def singleNumber(nums):
    acc = 0
    for x in nums:
        acc ^= x                       # pairs cancel: a ^ a = 0
    return acc

§O.3 · TYPE B

Fast exponentiation — halve, square

Brute force: n multiplications — at n = 2³¹ that's dead on arrival.

The identity: xⁿ = (x²)^(n/2), with an odd n peeling off one factor. Iteratively: walk n's binary digits — square the base each step (building the x^(2^k) ladder), multiply into the result whenever the current bit is set. The halving is §BS.1's tell arriving in arithmetic: the problem size is the exponent, and each step halves it.

def myPow(x, n):
    if n < 0:
        x, n = 1 / x, -n               # convert FIRST — see the trap
    res = 1.0
    while n:
        if n & 1:
            res *= x
        x *= x                         # the x^(2^k) ladder
        n >>= 1
    return res

§O.4 · TYPE C

Quickselect — partition and discard a side

The redundancy left on the table in §H.2: even the size-k heap maintains order information you never consume when the query is one-shot. Partition around a random pivot: the pivot lands at its final sorted position p. If p is the target index, done. Otherwise recurse into one side only — the other side is discarded wholesale: every element there is on the wrong side of rank p (the §BS discard, earned by O(n) partitioning work instead of sortedness).

Expected O(n), derived: a random pivot lands in the middle half with probability 1/2, shrinking the problem to ≤ 3n/4; expected work forms the geometric series n(1 + 3/4 + (3/4)² + …) = 4n. Worst case O(n²) exists (adversarial order vs a deterministic pivot) — say "expected", name the randomized pivot as the fix and median-of-medians as the worst-case-O(n) theory answer.

import random

def findKthLargest(nums, k):
    target = len(nums) - k             # k-th largest = this ascending index
    lo, hi = 0, len(nums) - 1
    while True:
        p = partition(nums, lo, hi)
        if p == target:
            return nums[p]
        if p < target:
            lo = p + 1                 # left of p: all < pivot — discarded
        else:
            hi = p - 1

def partition(nums, lo, hi):
    r = random.randint(lo, hi)         # randomization IS the guarantee
    nums[r], nums[hi] = nums[hi], nums[r]
    pivot, store = nums[hi], lo
    for i in range(lo, hi):
        if nums[i] < pivot:
            nums[store], nums[i] = nums[i], nums[store]
            store += 1
    nums[store], nums[hi] = nums[hi], nums[store]
    return store

§O.5 · TYPE D

Weighted random pick — three old friends

The construction is three earlier sets composed: build the prefix sums of the weights (§1.1) — a monotonically increasing array (§BS.1's requirement, manufactured on purpose) — draw r uniformly from [1, total], and return the lower bound (§BS.3): the first prefix ≥ r.

The uniformity proof (never skip it): index i is chosen iff r lands in (prefix[i−1], prefix[i]] — an interval containing exactly w[i] of the total integers — so P(i) = w[i]/total, exactly. The proof is two lines; presenting the structure with its proof is what separates the senior answer.

from bisect import bisect_left

class Solution:
    def __init__(self, w):
        self.prefix = []
        total = 0
        for x in w:
            total += x
            self.prefix.append(total)
    def pickIndex(self):
        r = random.randint(1, self.prefix[-1])   # inclusive both ends
        return bisect_left(self.prefix, r)

§O.6 · TYPE E

Reservoir sampling — uniform from an unknown stream

Brute force: copy values to an array, index randomly — O(n) memory; or two passes (count, then walk) — needs the stream twice. The interesting constraint: one pass, O(1) memory, length unknown until the stream ends.

The rule: keep the i-th element with probability 1/i, replacing the current champion. The induction (this IS the answer): after i elements, each has probability exactly 1/i — the newcomer by construction; any previous element had 1/(i−1) and survives the newcomer with probability 1 − 1/i, giving 1/(i−1) · (i−1)/i = 1/i. The invariant "everything seen so far is equally likely" is maintained one arrival at a time.

class Solution:
    def __init__(self, head):
        self.head = head
    def getRandom(self):
        node, i, choice = self.head, 1, 0
        while node:
            if random.randint(1, i) == 1:   # keep i-th with prob 1/i
                choice = node.val
            node, i = node.next, i + 1
        return choice

§O.7 · TYPE F · THE BOSS

Sliding window maximum — the deque earns its place

The escalation: re-scan per window O(nk) → heap with lazy deletion (§H.7) O(n log n) — correct, and the interviewer will ask for better. The deque is the better.

Two discard proofs, one structure:

• Back (dominance): an element older than the newcomer AND ≤ it can never be a window max again — every future window containing it also contains the newcomer, which beats it (§S.1's shadow proof, with the window guaranteeing co-membership). Pop it forever.
• Front (expiry): indices ≤ i − k have aged out of the window (§2.1's expiry). Pop from the front.

Evictions from both ends ⇒ a deque, and what survives is decreasing with the max at the front — Set 01's window and Set 03's monotonic discard, fused into one structure. This is the lab's arguments compounding, literally.

def maxSlidingWindow(nums, k):
    dq, out = deque(), []              # indices; values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                   # dominated — never a max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()               # aged out
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

When this feels derivable — two eviction rules, each with its own proof, composed into one pass — the set is yours, and so is the lab's core method: name the redundancy, prove the discard, count the amortized total.

§O.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• Deque stored values instead of indices — expiry breaks on duplicates ([2,2,2], k = 2)
• Dominance comparison inverted — pop while the BACK is ≤ the newcomer, not the reverse
• Quickselect with a fixed pivot on sorted input — quiet O(n²); randomize, and disclose the mutation
• Python: right-shifting a negative n never terminates (infinite sign bits) — convert n < 0 before the loop; Java: −2³¹ negation overflows int
• JS bitwise ops coerce to 32-bit signed — big prefix sums / masks silently corrupt; know >>> vs >>
• XOR applied without exact pairing structure — two singletons need the lowest-set-bit split (LC 260), triples need mod-3 counters (LC 137)
• randint is inclusive (Python), Math.random() exclusive (JS) — sampling ranges off by one; and rand() % n has modulo bias
• Reservoir with a fixed probability (1/k) — non-uniform, and NO functional test catches it; the induction is the only witness
• Deque used where eviction isn't age+dominance — arbitrary removals need the heap + lazy deletion (§H.7), not this

Signals → pattern (added to the drill deck in §3.2)

"max/min of every k-window"                     → monotonic deque — dominance from the back, age from the front
"k-th largest, one shot, array mutable"         → quickselect — expected O(n), say the worst case
"every element twice except one"                → XOR fold — O(1) space, exact-pairing required
"x to the power n"                              → halve the exponent, square the base — O(log n)
"pick an index proportional to weight"          → prefix sums + lower bound + uniform draw
"uniform sample from a stream, unknown length"  → reservoir — keep the i-th with probability 1/i

Interrogation — answer in your journal

§SR.1 · SET 16 — STRINGS RESIDUE

Theory — two halves, honestly labeled

Most "string questions" are pattern questions wearing string clothing — windows, stacks, tries, subsequence grids — and this lab already routes them there. What remains is exactly two things, and they could not be more different:

• Expand-around-center — a real technique with a real redundancy to kill (palindromic substrings).
• Parsing / simulation — a category with no redundancy and no trick. The brute force IS the solution; what interviews grade is spec discipline. Recognizing that there is nothing to recognize — and saying so — is itself the senior move.

Half 1 — the redundancy expand-around-center kills: the brute force checks all O(n²) substrings with an O(n) palindrome scan each → O(n³), re-comparing the same interior characters for every enclosing candidate. The fix rests on an identity:

every palindrome ↔ exactly one (center, radius) pair
centers: n characters (odd lengths) + n−1 gaps (even lengths) = 2n−1

Expanding outward from a center makes verification incremental: pal(l−1, r+1) = pal(l, r) AND s[l−1] == s[r+1] — one comparison per growth step instead of re-scanning the interior. The interior's verdict is carried, never recomputed — the same compute-once-reuse economy as §1.1's prefix sums, applied to palindromicity.

Half 2 — the parsing "template": translate the spec into an ordered checklist (whitespace → sign → digits → clamp), implement it as a small state machine, then run the edge-case ritual. The one guarantee: parsing is a single pass, O(n) always — if your parse loop is quadratic, you're re-scanning or re-concatenating (see traps).

Complexity tells: centers ⇒ O(n²) worst ("aaaa…" expands every center to a boundary) but with early exit on real text — say "quadratic worst-case, typically far better". Parsing ⇒ O(n), one pass, O(1) or O(n) space depending on output. Constraint smell: palindromic-substring problems cap n around 10³ — the setter telling you O(n²) is intended (§F.5).

§SR.2 · TYPE A · THE MISSING TECHNIQUE

Longest palindromic substring

The three-rung ladder (walk it in the interview): brute force O(n³) → DP table dp[i][j] = "s[i..j] is a palindrome", O(n²) time and O(n²) space → expand-around-center: same O(n²) time, O(1) space, and much faster on real text because most centers die after one comparison. The DP table buys nothing here — knowing why (you only ever need the verdicts along a center's ray, not the whole triangle) is the senior answer.

The derivation: enumerate every center — each character (odd lengths) and each gap between characters (even lengths). From a center, grow while the ends match; the invariant (§SR.1) makes each growth step a single comparison. Track the best window seen.

def longestPalindrome(s):
    best_l, best_r = 0, 0              # inclusive bounds of the best
    def expand(l, r):
        nonlocal best_l, best_r
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        if (r - 1) - (l + 1) > best_r - best_l:
            best_l, best_r = l + 1, r - 1   # undo the failed step
    for c in range(len(s)):
        expand(c, c)                   # odd length: centered on a char
        expand(c, c + 1)               # even length: centered on a gap
    return s[best_l:best_r + 1]

§SR.3 · TYPE B

Counting with the same centers

The move: same 2n−1 centers, different aggregation — count every successful expansion step instead of keeping the max. Each step outward is one distinct palindrome, because palindromes correspond one-to-one with (center, radius) pairs: same center → different radii, different centers → different palindromes. No double-count is possible by the bijection, not by luck.

This is the max-vs-count switch you've seen before (§S.7: "max forgives, sum doesn't") — except here the bijection makes counting exactly as safe as maxing.

def countSubstrings(s):
    count = 0
    for center in range(2 * len(s) - 1):
        l = center // 2
        r = l + center % 2             # even center-index = char, odd = gap
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1                 # each expansion step IS one palindrome
            l -= 1
            r += 1
    return count

§SR.4 · TYPE C · THE PARSING ARCHETYPE

String to integer — the spec is the problem

Say it out loud first: "there's no algorithmic trick here — the test is whether I cover the spec." Then turn the spec into an ordered checklist and implement it as a straight-line state machine: whitespace* → sign? → digit* → clamp. Every interview failure on this problem is a skipped spec line, not a wrong algorithm.

def myAtoi(s):
    INT_MAX, INT_MIN = 2**31 - 1, -2**31
    i, n = 0, len(s)
    while i < n and s[i] == ' ':       # 1. spaces only — not all whitespace
        i += 1
    sign = 1
    if i < n and s[i] in '+-':         # 2. at most ONE sign
        sign = -1 if s[i] == '-' else 1
        i += 1
    num = 0
    while i < n and s[i].isdigit():    # 3. digits until first non-digit
        num = num * 10 + (ord(s[i]) - 48)
        if sign * num <= INT_MIN:      # 4. clamp DURING accumulation
            return INT_MIN
        if sign * num >= INT_MAX:
            return INT_MAX
        i += 1
    return sign * num

§SR.5 · TYPE D

Expression evaluation — precedence as stack discipline

The one idea: precedence = which operators may wait. Addition and subtraction commute with waiting — push each operand with its sign and sum at the end (associativity makes deferral safe). Multiplication and division bind only their immediate left operand — they must fire now, against the stack top. That single distinction, encoded as §S's stack, is the whole algorithm.

def calculate(s):
    stack = []
    num, op = 0, '+'
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in '+-*/' or i == len(s) - 1:   # flush on operator or end
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))  # truncate toward ZERO
            num, op = 0, ch
    return sum(stack)

§SR.6 · TYPE E · THE BOSS

Text justification — pure spec, maximum discipline

Why it's the boss: zero algorithmic content, maximum spec surface — it's hard because every sub-rule is a place to slip. Decompose into three phases and conquer each in isolation:

1. Fit: a line takes the next word while chars + min-spaces + len(word) ≤ maxWidth, where min-spaces = current word count (each existing word will need at least one gap if the new word joins). The greedy fill isn't an optimization choice — the spec mandates "pack as many as possible".
2. Distribute: spaces = maxWidth − chars, gaps = words − 1; divmod(spaces, gaps) gives every gap base, and the first extra gaps one more — the spec's "left gaps get more".
3. The two special lines: a single-word line and the final line are left-justified, padded right. Both are separate branches; forgetting either fails hidden tests.

def fullJustify(words, maxWidth):
    res, line, length = [], [], 0      # length = chars only, no spaces
    for w in words:
        if length + len(line) + len(w) > maxWidth:
            spaces = maxWidth - length
            gaps = len(line) - 1
            if gaps == 0:
                res.append(line[0] + ' ' * spaces)
            else:
                base, extra = divmod(spaces, gaps)
                out = ''
                for i, word in enumerate(line[:-1]):
                    out += word + ' ' * (base + (1 if i < extra else 0))
                res.append(out + line[-1])
            line, length = [], 0
        line.append(w)
        length += len(w)
    res.append(' '.join(line).ljust(maxWidth))   # last line: left-justified
    return res

§SR.7 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• SUBSTRING vs SUBSEQUENCE, again — expand-around-center cannot drop characters; LC 516 is §X.5's interval DP
• Odd centers only — "abba" has a gap center; 2n−1 centers or even-length palindromes vanish
• Slicing inside the expand loop (s[l:r+1] == s[l:r+1][::-1]) — O(n) per step, quietly back to O(n³)
• atoi: clamped after building in Java/C++ — the int overflowed before the test; pre-check against (MAX − digit) / 10
• Calculator: -3 // 2 = -2 — Python floor ≠ spec's truncation; use int(a/b); JS needs Math.trunc; Java ints truncate natively
• Justification: extras to the RIGHT gaps, or the single-word / last-line branches missing — three separate hidden-test failures
• String += in a loop — immutable strings can make this quietly quadratic; build a list, join once (§F.4)
• Hunting for a clever pattern in a parsing problem — there isn't one; the checklist is the solution, say so and start

Signals → pattern (added to the drill deck in §3.2)

"longest / count palindromic SUBSTRING"      → expand around 2n−1 centers, O(1) space
"palindromic SUBSEQUENCE"                    → interval DP (Set 13) — the sibling, not this
"implement atoi / parse this format"         → spec → checklist → state machine; no trick exists
"evaluate an expression, no parentheses"     → defer +/− on a stack, fire * and / immediately
"format / justify / render text by rules"    → greedy fit + divmod distribution + special-case lines

Interrogation — answer in your journal

§M.1 · SET 17 — MATRIX MOVES

Theory — matrices are index algebra

Redundancy it kills: the O(mn) auxiliary copy. The brute force for almost every matrix transform allocates a second matrix, computes each cell's destination, and copies — paying full extra memory to represent what is really a relabeling of indices. When the relabeling has clean algebra, the transform happens in place; when the walk has clean geometry, four boundary pointers replace a visited matrix. Time stays O(mn) either way (you must touch every cell); this set's entire game is space: O(mn) → O(1).

The two sub-skills:

• Index identities — transpose: (r, c) → (c, r); horizontal reflect: (r, c) → (r, n−1−c); 90° CW rotation: (r, c) → (c, n−1−r); diagonals: r−c and r+c constant (the §K.6 N-Queens identities, back again). Complex transforms are compositions of simple involutions — and involutions (self-inverse swaps) are exactly what can run in place.
• In-place state discipline — the matrix stores its own bookkeeping: flags in row 0 / column 0 (Type C), old-and-new states packed into bits of the same cell (Type D). The "structure stores the map" economy of §L.6's interleaved clone, at matrix scale.

The boundary-walk skeleton (spiral form — four pointers, all monotone):

top, bottom, left, right = 0, m - 1, 0, n - 1
while top <= bottom and left <= right:
    emit row `top` left→right;    top += 1
    emit col `right` top→bottom;  right -= 1
    if top <= bottom:  emit row `bottom` right→left;  bottom -= 1
    if left <= right:  emit col `left` bottom→top;    left += 1

Complexity tell: every cell touched a constant number of times → O(mn) time always; the interviewer's real question is the space bound — answer it before they ask. Constraint smell: matrix problems cap around 200×200 — time is never the issue; the follow-up "can you do it in place?" is the actual exam.

§M.2 · TYPE A · THE ARCHETYPE

Rotate image — composition of involutions

Brute force: allocate b, set b[c][n−1−r] = a[r][c] → O(n²) time and O(n²) space. The redundancy IS the copy.

The derivation: where does (r, c) go under 90° CW? Its row index becomes the column (top row becomes right column), and its distance-from-left becomes distance-from-top: (r, c) → (c, n−1−r). Now factor it: transpose sends (r, c) → (c, r); horizontal reflect then sends (c, r) → (c, n−1−r). Transpose ∘ reflect = rotate — and both factors are involutions (pure swaps), so both run in place with zero memory. Composing two O(1)-space moves is the whole trick.

def rotate(matrix):
    n = len(matrix)
    for r in range(n):
        for c in range(r + 1, n):          # STRICT upper triangle only
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
    for row in matrix:
        row.reverse()

§M.3 · TYPE B

Spiral order — the boundary walk

Brute force: simulate a walker with a direction vector and a visited matrix — correct, O(mn) extra space, and fiddly turn logic.

Redundancy: per-cell visited bookkeeping, when four numbers summarize everything already emitted — the live window's boundaries ARE the visited set, compressed to O(1).

Why exactly two guards, derived: the top pass consumes a row and the right pass consumes a column unconditionally. If the window had only one row, the top pass just emptied it — the bottom pass would re-emit that same row reversed. Symmetrically for one column and the left pass. The first two passes can never collide with each other (the while-condition guaranteed a non-empty window when they started); only the third and fourth passes race against a window the first two may have exhausted. Hence guards on exactly those two.

def spiralOrder(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bottom:                  # the row may have just vanished
            for c in range(right, left - 1, -1):
                res.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:                  # the column may have just vanished
            for r in range(bottom, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

§M.4 · TYPE C

Set matrix zeroes — the matrix stores its own flags

The escalation: O(mn) copy → O(m+n) flag arrays ("which rows/cols must die") → O(1): reuse row 0 and column 0 AS the flag arrays.

Why it's legal, derived: the flags are idempotent booleans — a row "must die" whether one zero or five triggered it. Writing a 0 into matrix[r][0] as a flag can only ever coincide with information we're storing anyway. The only casualties are row 0 and column 0's own original states — so capture those in two scalars before any marking (read-before-overwrite: §1.4's ordering discipline as a phase structure). And why no sentinel? The domain is all integers — there is no out-of-band value to mark with; contrast §K.5's '#', which existed only because the domain was letters.

The phase order is the algorithm: ① capture the two scalars → ② mark flags from the interior → ③ zero the interior from the flags → ④ settle row 0 / column 0 last. Zeroing the first row before step ③ wipes the flags the interior still needs.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][c] == 0 for c in range(n))
    first_col = any(matrix[r][0] == 0 for r in range(m))
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0           # column 0 holds row-flags
                matrix[0][c] = 0           # row 0 holds column-flags
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row:
        for c in range(n):
            matrix[0][c] = 0
    if first_col:
        for r in range(m):
            matrix[r][0] = 0

§M.5 · TYPE D

Simultaneous update — two generations in one cell

The problem inside the problem: "simultaneously" means every read must see the OLD generation — but in-place writes destroy it as you go. This is §D.3's sequential-assignment bug at matrix scale: update cell (0,0) naively and cell (0,1) reads the future.

The insight: a cell's value is 0 or 1 — one bit — but the cell can hold an integer. Pack both generations into one cell: bit 0 = current, bit 1 = next. Neighbors read & 1 (always the old state, even after the cell is "updated"); a final sweep shifts everything right by one. §O.2's bit algebra doing state management instead of arithmetic.

def gameOfLife(board):
    m, n = len(board), len(board[0])
    for r in range(m):
        for c in range(n):
            live = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and board[nr][nc] & 1:
                        live += 1              # & 1: ALWAYS the old generation
            if board[r][c] & 1:
                if live in (2, 3):
                    board[r][c] |= 2           # bit 1 = survives
            elif live == 3:
                board[r][c] |= 2               # bit 1 = born
    for r in range(m):
        for c in range(n):
            board[r][c] >>= 1                  # promote next → current

§M.6 · TYPE E

Staircase search — a corner is a comparator

Brute force: scan O(mn); binary search each row O(m log n) — both ignore that the two sort orders interact.

The discard proof (the §T sentence, twice per position): stand at the top-right corner — the minimum of its row, the maximum of its column. If the value is too big, every cell below it in this column is bigger still — the whole column dies. If too small, every cell to its left is smaller — the whole row dies. One comparison retires an entire row or column, permanently. Start top-left instead and both moves make things bigger — no discard exists; only the top-right and bottom-left corners are comparators.

def searchMatrix(matrix, target):
    r, c = 0, len(matrix[0]) - 1       # top-right: row-min, column-max
    while r < len(matrix) and c >= 0:
        v = matrix[r][c]
        if v == target:
            return True
        if v > target:
            c -= 1                     # column below: all larger — dead
        else:
            r += 1                     # row to the left: all smaller — dead
    return False

§M.7 · TYPE F · THE BOSS

Longest increasing path — the lab in one problem

Brute force: DFS every increasing path from every cell — exponential; the same "longest path from (r,c)" recomputed once per visitor.

The chain of recognitions (three sets composing):

1. Grid-as-graph (§GR.2): cells are nodes, increasing adjacencies are directed edges.
2. Strictness ⇒ DAG: a cycle would need values a < b < … < a — impossible. So this graph has no cycles, and — the beautiful consequence — no visited set is needed: DFS cannot revisit along a path (§GR.7's mandatory visited set was for graphs that CAN cycle).
3. Overlapping subproblems on a DAG ⇒ memoize (§D.1's identity, purest form): memo[r][c] = longest path starting at (r,c); memoized DFS computes each state once, in an order the recursion discovers for itself — post-order IS a topological order.

def longestIncreasingPath(matrix):
    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]
    def dfs(r, c):
        if memo[r][c]:
            return memo[r][c]          # check before compute — §1.4, final form
        best = 1
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        memo[r][c] = best
        return best
    return max(dfs(r, c) for r in range(m) for c in range(n))

§M.8 · BEFORE YOU SUBMIT + INTERROGATION

Traps, signals & interrogation

• [[0]*n]*m — m aliases of ONE row (§F.4); writing any cell writes the whole column. Use a comprehension
• Transpose over the full square — every pair swapped twice; a confident identity function
• Rotating a rectangle in place — the shape changes (m×n → n×m); allocate and say why
• Spiral without the two guards — [[1,2,3]] emits six values; single-row/column windows double-emit
• Set Zeroes zeroing while scanning — introduced zeros cascade ([[1,0],[1,1]] wipes everything); mark, THEN apply
• Set Zeroes settling row 0 / col 0 before the interior — the flags die while still needed; phase order is the algorithm
• Game of Life reading updated neighbors — the blinker dies instead of turning; pack generations in bits
• Staircase from the top-LEFT — both moves increase the value; no discard proof exists at that corner
• LC 329 with a visited set — unnecessary (strictness ⇒ DAG) and dangerous next to the memo
• zip(*matrix) "transposes" into NEW tuples — fine for reading, not an in-place answer; know what the one-liner hides

Signals → pattern (added to the drill deck in §3.2)

"rotate / flip an image in place"            → compose involutions: transpose + reflect
"traverse in spiral / layer order"           → four shrinking boundaries + the two guards
"zero/mark by full row and column, O(1)"     → borrow row 0 and column 0 as the flag arrays
"all cells update SIMULTANEOUSLY"            → pack old + new generations into bits, shift last
"sorted by rows AND columns, find target"    → staircase from top-right — one comparison kills a line
"longest strictly ordered path in a grid"    → strictness ⇒ DAG ⇒ memoized DFS, no visited set

Interrogation — answer in your journal

§3.5 · RUN THE FULL PROTOCOL ON EACH

Practice ladder

Mark a problem solved and the app stamps today's date and schedules the +3 and +10 day re-solves. Amber = due.

§3.6 · ANSWERS NOT INCLUDED, ON PURPOSE

Interrogation questions

Answer in the journal boxes below — they save automatically in this browser. Export everything as markdown when you want a copy.