LC Patterns — Searching & Selection

The partition — the engine under half this file

def partition(nums, lo, hi):          # Lomuto: simple, interview-safe
    p = random.randint(lo, hi)        # random pivot — NOT optional (see pitfalls)
    nums[p], nums[hi] = nums[hi], nums[p]
    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                      # pivot's final, correct position

After one partition: everything left of store is smaller than the pivot, everything right is ≥ — and store is exactly where the pivot would land in a full sort. That last fact is what quickselect exploits.

• Lomuto vs Hoare: Lomuto (above) is easier to get right live; Hoare does fewer swaps but its return value is not the pivot's final index — mixing up the two conventions is a classic silent bug. Pick Lomuto and say why.
• Know the index vocabulary: "k-th largest" = index n − k in sorted (ascending) order. Convert once, at the top, and work with the sorted-position index from then on.

Universal pitfalls

1. Fixed pivot = O(n²) on adversarial input. Sorted (or all-equal) arrays kill first/last-element pivots. Randomize the pivot and say "expected O(n)"; name median-of-medians as the guaranteed-O(n) variant (know it exists and its idea — groups of 5, recursive median — but never code it in an interview).
2. Quickselect mutates the input. Say so; if the problem forbids it, that's a point for the heap instead.
3. Duplicates stalling partitions — all-equal arrays make < pivot put nothing on the left, shrinking by 1 per pass. The fix is 3-way partitioning (Pattern 2) — recognize when duplicates are heavy.
4. Off-by-one between "k-th" (1-based, human) and array indices (0-based). One conversion line up front; never juggle both mid-loop.
5. Reaching for rung 3 when rung 4 is sitting there — frequencies are bounded by n, h-index is bounded by n, digits are bounded by 10: when the range is small, counting beats comparing, every time.

What it is: Find the k-th smallest/largest element in O(n) average time, in place, without sorting: run one partition — the pivot lands at its true sorted position — then recurse into only the side that contains index k, unlike quicksort which recurses into both.

Intuition: one partition tells you the pivot's exact rank. If that rank is k, done. If k is smaller, the answer lives entirely in the left chunk — the right chunk can be thrown away unread (and vice versa). Discarding one side per round gives the geometric series n + n/2 + n/4 + … = 2n = O(n) expected — that series is the proof, and it's the sentence to say when asked "why is this linear when quicksort isn't?" (quicksort keeps both sides: n log n; quickselect keeps one: n). Median (462) is selection at k = n//2: to make all elements equal with fewest ±1 moves, meet at the median (not the mean — the median minimizes the sum of absolute distances; moving away from it makes more elements farther than closer, a one-line exchange argument), so the whole problem is one quickselect plus one sum.

Approach: convert k-th largest → sorted index n − k; loop (iterative beats recursive here — no stack, no tail-call fiddling): partition, compare returned index with target, shrink lo/hi to the surviving side. K closest points (973): same code with squared distance as the comparison key — quickselect doesn't need the order, only the comparisons (no sqrt: monotone, so skip it and say why). Always offer the ladder first: "sort O(n log n), heap O(n log k) — cross-ref file 08 — or quickselect O(n) average; for k ≪ n the heap may actually win, and it doesn't mutate input."

What it is: Sometimes you don't need any k-th element — the partitioned arrangement itself is the answer: evens before odds, colors in 0/1/2 order, small-median-large blocks. One pass, pointer regions, in place.

Intuition: maintain regions with meanings, and an invariant that every step preserves. Two-way (905, evens first): left = boundary of the settled-evens region; scan with i, swap evens back into the region. Three-way — the Dutch National Flag (75, sort 0s/1s/2s): three regions and a scanner — [0..lo) all 0s, [lo..mid) all 1s, [hi+1..end] all 2s, [mid..hi] unknown; look at nums[mid]: 0 → swap to lo (both advance), 1 → just advance mid, 2 → swap to hi (only hi shrinks — the swapped-in element is unexamined, so mid must stay: the classic bug of this algorithm, and the reason to state the invariant before coding). Wiggle Sort II (324) is the boss fight: quickselect the median (Pattern 1), then Dutch-flag around it — with a virtual index mapping that interleaves the halves; know the two-phase plan (select, then 3-way partition into interleaved slots) and be honest that the index mapping is fiddly.

Approach: write the region meanings as a comment first (# [0..lo) zeros | [lo..mid) ones | [mid..hi] unknown | (hi..] twos), then each branch of the loop is forced by "restore the invariant." Loop condition mid <= hi (the unknown region is inclusive — off-by-one #2). For 905-style 2-way, the same discipline with two regions. This "regions + invariant" discipline is exactly the binary-search file's advice (§0 there) transplanted to partitioning — one mental model, two files.

What it is: Find the element appearing more than n/2 times (169) — or the up-to-two elements appearing more than n/3 times (229) — in one pass and O(1) space, by letting different elements cancel each other out and keeping only a candidate and a counter.

Intuition: pair up every majority-element occurrence with one non-majority occurrence and destroy both — the majority appears more than everything else combined, so after all the canceling, it must be what's left standing. The scan implements this: keep candidate + count; same element → count++, different → count−− (a mutual kill), count hits 0 → adopt the current element as the new candidate. For n/3 (229): at most two elements can exceed n/3 (three would need > n total — say this pigeonhole first), so run the same game with two candidate/count pairs; a new element only decrements both when it matches neither. Crucial asterisk: the scan finds the only possible candidates — if the problem doesn't guarantee a majority exists (229 doesn't), you must verify with a second counting pass.

Approach: 169: one pass, two variables; if a majority is guaranteed, return the candidate. 229: two pairs with a strict branch order — match candidate1? match candidate2? adopt into an empty (count-0) slot? only then decrement both — then a verification pass keeping counts > n/3. The check-adoption-before-decrement order matters: get it wrong and a legitimate candidate gets evicted by its own supporters.

What it is: When the values you're selecting over live in a small, known range — counts are between 0 and n, an h-index can't exceed n, gaps obey a pigeonhole bound — replace comparison-based work with addressing: drop items into indexed buckets, then read the buckets in order. O(n) worst case, no randomness, no log factors.

Intuition: h-index (274): h is capped at n, so make count buckets 0..n (citations above n clamp to n — they can't help beyond h = n); sweep h from n downward accumulating "papers with ≥ h citations", stop when the running total first reaches h. No sort — the answer space was small, so you counted it. Top-k frequent (347): frequencies are between 1 and n → bucket elements by frequency and read buckets from n down until k are collected — the O(n) answer to the heap's O(n log k) (file 08, Pattern 1's follow-up, closed here). Maximum gap (164) is pigeonhole at its prettiest: with n numbers spanning [min, max], the largest adjacent-in-sorted-order gap is at least (max − min)/(n − 1) — so make buckets slightly smaller than that bound, and no two numbers in the same bucket can form the max gap: only per-bucket min/max matter, and the answer is a gap between buckets. Sorting avoided by an argument, not a trick.

Approach: identify the bounded quantity (value? count? rank?), allocate range+1 buckets, one pass to fill, one ordered pass to read. 274: clamp-then-count, suffix-sum downward. 347: Counter, then buckets[freq].append(elem), read high→low. 164: bucket width max(1, (hi − lo) // (n − 1)), keep (min, max) per bucket, then one sweep comparing each nonempty bucket's min with the previous nonempty bucket's max. State the pigeonhole sentence before coding 164 — it's the entire justification for ignoring within-bucket pairs.

What it is: Search a matrix whose rows and columns are each sorted. Stand at the top-right corner (or bottom-left): one comparison either eliminates a whole column (too big → step left) or a whole row (too small → step down). O(m + n), no binary search needed.

Intuition: the top-right element is the largest in its row and the smallest in its column — so if it's bigger than the target, its entire column is bigger (gone); if smaller, its entire row is smaller (gone). Each comparison permanently discards a full line of the matrix, and you take at most m + n steps before running out. This is "one test eliminates a provable chunk" (the master insight) with the chunk being a row/column instead of a half. Distinguish the two classic matrices: 74 is fully sorted (each row continues the last) — that's a single sorted list wearing a matrix costume: one binary search on indices 0..m·n−1 with divmod decoding, O(log mn). 240 is only row-and-column sorted (rows don't continue) — binary search per row costs O(m log n); the staircase does O(m + n). Count negatives (1351, rows/cols sorted descending): same walk, but count what each step eliminates instead of hunting one target — the staircase as an accumulator.

Approach: 240: r, c = 0, n − 1; loop while in bounds: equal → found; matrix[r][c] > target → c -= 1; else r += 1. 74: compute mid = (lo+hi)//2, decode matrix[mid // n][mid % n], standard binary search (cross-ref file 05 Template A). 1351: walk from a corner keeping a running count of eliminated negatives per step. Choosing the corner: it must be a max-of-one-line and min-of-the-other — top-right or bottom-left work; top-left doesn't (it's the min of both — a comparison eliminates nothing; say this when explaining the choice).

[1,  4,  7, 11]
[2,  5,  8, 12]
[3,  6,  9, 16]

What it is: "K-th smallest in a sorted matrix / among all pairs / in a multiplication table" — the element count is huge or implicit, and three different files of this series each offer a tool. This pattern is the decision procedure; the mechanics live in the cross-referenced files.

Intuition: three tools, three preconditions. (a) Heap frontier (file 08, Pattern 4): treat the space as k sorted sequences and pop k times — O(k log k)-ish; right when k is small and you can enumerate "successors" of an element. (b) Binary search on the value (file 05, Pattern 6): if you can count elements ≤ x quickly (sorted rows → staircase count — Pattern 5 of this file doing the counting!), binary-search the smallest x with count ≥ k — O(n log(range)); right when k is huge (popping k times is too slow) but counting is cheap. (c) Quickselect (Pattern 1): only when the candidates can be materialized in memory — then it's O(n) on the flattened data. The deciding questions, in order: Can I hold all elements? (yes → quickselect/sort). Is k small? (yes → heap). Can I count ≤ x cheaply? (yes → binary search the value). For 378 (n×n matrix) all three genuinely work — which is why interviewers love it: the conversation is the comparison. For 668 / 719, k and the space are enormous → only (b) survives.

Approach: say the three-question decision procedure out loud, pick, then execute from the owning file's template. For 378 specifically, know the staircase-count subroutine cold (start bottom-left; walk up/right accumulating "elements ≤ x per column" — O(n) per count) since it's the piece this file contributes to the file-05 template.