Algorithm patterns

Interview problems are not infinite. There are roughly a dozen shapes, and most questions are one shape with the labels changed. This file is organized around recognition: for each pattern, the signal in the problem statement that should make you reach for it, the template, and the variants that appear.

Every implementation here was executed — 12 pattern families in Python, and the TypeScript versions of the ones where the JS idiom differs. Graph and tree patterns are in Graphs and trees; dynamic programming is in Dynamic programming.

Table of contents

• 1. Pattern recognition cheat sheet
• 2. Two pointers
• 3. Fast and slow pointers
• 4. Sliding window
• 5. Prefix sums and difference arrays
• 6. Monotonic stack and monotonic deque
• 7. Intervals and sweep line
• 8. Cyclic sort and index-as-hash
• 9. Backtracking
• 10. Greedy
• 11. Bit manipulation
• 12. String algorithms
• 13. Matrix patterns
• 14. Test run
• 15. Interview questions

1. Pattern recognition cheat sheet

graph TD
    A{"Sorted array, or two ends<br/>converge monotonically?"} -->|yes| P1["Two pointers"]
    A -->|no| B{"Contiguous subarray/substring<br/>with a monotone constraint?"}
    B -->|yes| P2["Sliding window"]
    B -->|no| C{"Linked list, or repeated<br/>application of a function?"}
    C -->|yes| P3["Fast and slow pointers"]
    C -->|no| D{"Next greater/smaller element,<br/>spans, histogram areas?"}
    D -->|yes| P4["Monotonic stack or deque"]
    D -->|no| E{"Enumerate all subsets,<br/>permutations, combinations?"}
    E -->|yes| P5["Backtracking with pruning"]
    E -->|no| F{"Numbers 1..n in an array,<br/>find missing/duplicate?"}
    F -->|yes| P6["Cyclic sort /<br/>index-as-hash"]

Two meta-heuristics that are worth as much as the table. Read the constraints: n <= 20 means exponential/bitmask, n <= 500 means O(n^3), n <= 5,000 means O(n^2), n <= 1e5 means O(n log n), n <= 1e7 means O(n) with no allocation. And when stuck, ask what the brute force is, then ask what it recomputes — every pattern in this file is a way of not recomputing something.

2. Two pointers

Signal: a sorted array, or a problem where moving one end of a range monotonically improves or worsens the objective. Also: any “do it in place with O(1) space”.

Opposite ends converging

def two_sum_sorted(a, t):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == t: return (i, j)
        if s < t: i += 1          # need bigger -> only moving i can help
        else:     j -= 1          # need smaller -> only moving j can help
    return None

The correctness argument is the important part: at each step, one of the two moves is provably safe because the array is sorted, so we never skip a valid answer. That argument is what an interviewer wants to hear, and it transfers to every problem below.

def three_sum(nums):
    """Fix one element, two-pointer the rest. O(n^2), and the dedup is the hard part."""
    nums = sorted(nums); res = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i-1]: continue          # skip duplicate ANCHORS
        if nums[i] > 0: break                            # sorted: no way back to zero
        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]])
                while l < r and nums[l] == nums[l+1]: l += 1   # skip duplicate PAIRS
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
    return res

3sum generalizes: kSum is “fix one, recurse to (k-1)Sum”, bottoming out at the two-pointer scan, for O(n^(k-1)).

def container_water(h):
    """Max area between two lines. The insight: move the SHORTER side."""
    i, j, best = 0, len(h) - 1, 0
    while i < j:
        best = max(best, (j - i) * min(h[i], h[j]))
        if h[i] < h[j]: i += 1
        else: j -= 1
    return best

def trapping_rain(h):
    """Two pointers carrying running maxima. O(n) time, O(1) space."""
    i, j, li, rj, total = 0, len(h) - 1, 0, 0, 0
    while i < j:
        if h[i] < h[j]:
            li = max(li, h[i]); total += li - h[i]; i += 1
        else:
            rj = max(rj, h[j]); total += rj - h[j]; j -= 1
    return total

Why moving the shorter side is safe in container-water: the area is bounded by the shorter line, so keeping it and shrinking the width can only make things worse — the only hope is to replace it. That exchange argument is the whole problem.

Same-direction (read and write cursors)

def remove_dups_inplace(a):
    """Write cursor lags the read cursor. The template for every in-place filter/compaction."""
    if not a: return 0
    w = 1
    for r in range(1, len(a)):
        if a[r] != a[w-1]:
            a[w] = a[r]; w += 1
    return w                                   # a[:w] is the answer

This shape covers: remove duplicates, remove element, move zeroes, sort colors (three cursors), partition by predicate, and “compact an array in place”. Recognize it by “in place” plus “return the new length”.

def is_palindrome_alnum(s):
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum(): i += 1
        while i < j and not s[j].isalnum(): j -= 1
        if s[i].lower() != s[j].lower(): return False
        i += 1; j -= 1
    return True

function twoSumSorted(a: readonly number[], t: number): [number, number] | null {
  let i = 0, j = a.length - 1;
  while (i < j) {
    const s = a[i]! + a[j]!;
    if (s === t) return [i, j];
    if (s < t) i++; else j--;
  }
  return null;
}

Pitfalls

• while i < j versus while i <= j: use < when the two pointers must be distinct elements (pairs), <= when a single element is a valid answer (binary search, palindrome of odd length).
• Deduplication in kSum needs to happen at two places — the anchor loop and after recording a hit.
• Forgetting that two pointers requires sorted input, and then paying O(n log n) to sort when a hash map would have been O(n). For unsorted two-sum, a hash map is the right answer.

3. Fast and slow pointers

Signal: a linked list, or any structure where “next” is a function of the current state — so the traversal is a functional graph and must eventually cycle.

def find_duplicate(nums):
    """One duplicate in [1..n] inside an array of length n+1. O(1) space, input unmodified.
       Treat i -> nums[i] as a linked list; the duplicate is the cycle entry."""
    slow = fast = nums[0]
    while True:
        slow = nums[slow]; fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]                          # phase 2: reset one pointer to the start
    while slow != fast:
        slow = nums[slow]; fast = nums[fast]
    return slow

def happy(n):
    """Repeatedly sum the squares of the digits. Cycles, so Floyd applies."""
    def nxt(x): return sum(int(c) ** 2 for c in str(x))
    slow = fast = n
    while True:
        slow = nxt(slow); fast = nxt(nxt(fast))
        if fast == 1: return True
        if slow == fast: return slow == 1

The phase-2 proof, because it is the follow-up: let mu be the distance from the start to the cycle entry and lambda the cycle length. When the pointers meet, the slow pointer has travelled some distance d that is a multiple of lambda past the entry. Walking mu more steps from the meeting point therefore lands on the entry — and mu steps from the start also lands there. So resetting one pointer to the head and advancing both by one meets exactly at the entry.

Uses beyond linked lists: cycle detection in any iterated function (Pollard’s rho for integer factorization is the same trick), finding the middle of a list in one pass, and finding the kth-from-end by opening a gap of k first.

4. Sliding window

Signal: contiguous subarray or substring, plus a constraint that is monotone in the window — adding an element can only make the constraint harder, removing one can only make it easier.

Fixed size

def max_sum_window(a, k):
    s = sum(a[:k]); best = s
    for i in range(k, len(a)):
        s += a[i] - a[i-k]                   # add the entering element, subtract the leaving one
        best = max(best, s)
    return best

Variable size — the template

left = 0
for right in range(n):
    include a[right] in the window state
    while the window is INVALID:
        remove a[left] from the window state
        left += 1
    # here the window [left, right] is the largest valid window ending at right
    update the answer

The whole family is that shape with different definitions of “window state” and “invalid”. Because left only ever moves forward, the total work is O(n) even though the code looks nested — see Complexity §7.2.

def longest_unique(s):
    """Longest substring without repeating characters. State: last index of each char."""
    last = {}; best = start = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1             # jump, do not step
        last[ch] = i
        best = max(best, i - start + 1)
    return best

def longest_repeat_replace(s, k):
    """Longest substring of one repeated char with at most k replacements.
       State: character counts + the max frequency seen. Invalid when window - maxfreq > k."""
    cnt = Counter(); left = maxf = best = 0
    for right, ch in enumerate(s):
        cnt[ch] += 1
        maxf = max(maxf, cnt[ch])            # NOTE: never decreased — see the note below
        while (right - left + 1) - maxf > k:
            cnt[s[left]] -= 1; left += 1
        best = max(best, right - left + 1)
    return best

def min_subarray_len(target, a):
    """Smallest window with sum >= target. Shrink while still valid -> minimize."""
    left = s = 0; best = float('inf')
    for right, v in enumerate(a):
        s += v
        while s >= target:
            best = min(best, right - left + 1)
            s -= a[left]; left += 1
    return 0 if best == float('inf') else best

def min_window_substring(s, t):
    """Smallest window containing all of t (with multiplicity). The classic hard one."""
    if not t or not s: return ""
    need = Counter(t); missing = len(t)
    best = (float('inf'), 0, 0); left = 0
    for right, ch in enumerate(s):
        if need[ch] > 0: missing -= 1        # this char was actually needed
        need[ch] -= 1                        # counts can go negative: surplus
        while missing == 0:                  # valid -> shrink from the left
            if right - left < best[0] - 1: best = (right - left + 1, left, right)
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2]+1]

The maxf subtlety in longest_repeat_replace is a favourite follow-up. maxf is never decreased when the window shrinks, which looks like a bug. It is not: the answer only improves when maxf grows, so a stale (too large) maxf can only cause the window to be not shrunk — it never produces an answer larger than the true optimum. Being able to explain that is a genuine differentiator.

Two distinct goals, two loop structures. For “longest valid window”, shrink only while invalid and record after the while. For “shortest valid window”, shrink while valid and record inside the while. Getting these backwards is the most common sliding-window bug.

Windows with a monotonic deque

When the window statistic is a max or min, you need more than a running sum — you need a structure that can drop dominated elements.

def sliding_window_max(a, k):
    """Max of every window of size k, O(n) total. deque holds INDICES, values decreasing."""
    dq, res = deque(), []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v: dq.pop()      # v dominates: those can never be a future max
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()            # front fell out of the window
        if i >= k - 1: res.append(a[dq[0]])
    return res

function slidingWindowMax(a: readonly number[], k: number): number[] {
  const dq: number[] = [];       // indices
  const res: number[] = [];
  let head = 0;                  // cursor instead of shift(): keeps it O(n), not O(n^2)
  for (let i = 0; i < a.length; i++) {
    while (dq.length > head && a[dq[dq.length - 1]!]! <= a[i]!) dq.pop();
    dq.push(i);
    if (dq[head]! <= i - k) head++;
    if (i >= k - 1) res.push(a[dq[head]!]!);
  }
  return res;
}

The TypeScript version uses a head cursor instead of shift(). Array.prototype.shift is O(n), so the naive translation is O(n·k) — the single most common JavaScript translation bug for this pattern.

When sliding window does NOT apply

If the array contains negative numbers and the constraint is “sum >= target”, the window is not monotone (adding an element can decrease the sum), so the two-pointer shrink is invalid. Use prefix sums plus a hash map or a monotonic deque instead. Recognizing this is the mark of someone who understands the pattern rather than pattern-matching it.

5. Prefix sums and difference arrays

Signal: repeated range queries on a static array, or counting subarrays with a property.

def subarray_sum_equals_k(a, k):
    """Count subarrays summing to k. Works with negatives, unlike sliding window.
       Key identity: sum(i..j) == prefix[j] - prefix[i-1]."""
    seen = defaultdict(int); seen[0] = 1       # the empty prefix — do NOT forget this
    running = count = 0
    for v in a:
        running += v
        count += seen[running - k]             # every earlier prefix that completes a valid subarray
        seen[running] += 1
    return count

That seen[0] = 1 seed is the single most common bug in this pattern: without it you miss every subarray that starts at index 0.

Variants on the same identity:

def longest_subarray_equal_01(a):
    """Map 0 -> -1, then it becomes 'longest subarray with sum 0'."""
    seen = {0: -1}; running = best = 0
    for i, v in enumerate(a):
        running += 1 if v else -1
        if running in seen: best = max(best, i - seen[running])
        else: seen[running] = i                # keep the FIRST index for maximum length
    return best

2D prefix sums

def range_sum_2d(mat):
    m, n = len(mat), len(mat[0])
    ps = [[0]*(n+1) for _ in range(m+1)]       # 1-indexed padding removes all boundary checks
    for i in range(m):
        for j in range(n):
            ps[i+1][j+1] = mat[i][j] + ps[i][j+1] + ps[i+1][j] - ps[i][j]
    def query(r1, c1, r2, c2):
        return ps[r2+1][c2+1] - ps[r1][c2+1] - ps[r2+1][c1] + ps[r1][c1]
    return query

Inclusion-exclusion: add the big rectangle, subtract the two overlapping strips, add back the corner you subtracted twice. The +1 padding is what makes it boundary-check-free.

Suffix and bidirectional products

def product_except_self(a):
    """No division allowed. One left pass, one right pass, O(1) extra space."""
    n = len(a); res = [1]*n
    left = 1
    for i in range(n): res[i] = left; left *= a[i]
    right = 1
    for i in range(n-1, -1, -1): res[i] *= right; right *= a[i]
    return res

The “prefix from the left, suffix from the right” shape also solves trapping rain water, “candy”, “maximum product subarray”, and any problem where each position needs information from both directions.

Difference array

The dual of prefix sums: O(1) range updates, one O(n) pass at the end.

def difference_array(n, updates):
    """Each update adds v to [l, r]. O(1) per update, O(n) to materialize."""
    d = [0]*(n+1)
    for l, r, v in updates:
        d[l] += v; d[r+1] -= v                 # mark the start and one-past-the-end
    out, run = [], 0
    for i in range(n):
        run += d[i]; out.append(run)
    return out

Use it whenever you have many range updates and only need the final array — booking calendars, “corporate flight bookings”, “car pooling”, and any “count how many intervals cover each point”. If you need interleaved updates and queries, upgrade to a Fenwick or segment tree (TypeScript §20).

6. Monotonic stack and monotonic deque

Signal: “next greater element”, “previous smaller element”, “how far until…”, histogram areas, spans, and any problem where an element becomes irrelevant once a bigger (or smaller) one appears.

The invariant: the stack holds indices whose values are monotonically increasing (or decreasing). When a new element breaks the invariant, everything it dominates is popped — and that pop is the moment you learn the answer for the popped element.

Total work is O(n) because each index is pushed once and popped at most once.

def next_greater(a):
    res = [-1]*len(a); st = []                 # stack of indices with DECREASING values
    for i, v in enumerate(a):
        while st and a[st[-1]] < v:
            res[st.pop()] = v                  # v is the next greater element for the popped index
        st.append(i)
    return res

def daily_temperatures(t):
    """Same skeleton; the answer is the DISTANCE rather than the value."""
    res = [0]*len(t); st = []
    for i, v in enumerate(t):
        while st and t[st[-1]] < v:
            j = st.pop(); res[j] = i - j
        st.append(i)
    return res

def largest_rectangle(h):
    """Largest rectangle in a histogram. A sentinel 0 at the end flushes the stack."""
    st, best = [], 0
    for i, v in enumerate(h + [0]):
        while st and h[st[-1]] >= v:
            top = st.pop()
            left = st[-1] + 1 if st else 0     # the element below is the previous SMALLER bar
            best = max(best, h[top] * (i - left))
        st.append(i)
    return best

def trapping_rain_stack(h):
    """The stack formulation of rain water: each pop closes a basin."""
    st, total = [], 0
    for i, v in enumerate(h):
        while st and h[st[-1]] < v:
            mid = st.pop()
            if not st: break
            width = i - st[-1] - 1
            height = min(h[st[-1]], v) - h[mid]
            total += width * height
        st.append(i)
    return total

def remove_k_digits(num, k):
    """Smallest number after removing k digits. Greedy + monotonic stack."""
    st = []
    for ch in num:
        while k and st and st[-1] > ch:        # a bigger digit in front is always worse
            st.pop(); k -= 1
        st.append(ch)
    st = st[:len(st)-k] if k else st           # leftover k: drop from the end (already increasing)
    return ''.join(st).lstrip('0') or '0'

The sentinel trick in largest_rectangle deserves a callout: appending a 0 guarantees every bar is eventually popped, so you do not need a separate drain loop after the main pass. Prepending a sentinel does the same for the left boundary. Sentinels remove edge cases, and interviewers notice.

Related problems on the same skeleton: “sum of subarray minimums” (each element’s contribution is count of subarrays where it is the min = left span x right span), “maximal rectangle in a binary matrix” (largest-rectangle per row over a running histogram), “stock span”, “132 pattern”, “next greater element in a circular array” (iterate 2n and mod).

The monotonic deque is the windowed version — same domination idea, but you also evict from the front when an index leaves the window. See sliding_window_max in section 4.

7. Intervals and sweep line

Signal: pairs (start, end). Almost always: sort first. Which key you sort by is the entire problem.

def merge_intervals(iv):
    iv = sorted(iv); res = []
    for s, e in iv:
        if res and s <= res[-1][1]:
            res[-1][1] = max(res[-1][1], e)    # max, not e: [1,10] then [2,3] must stay [1,10]
        else:
            res.append([s, e])
    return res

def insert_interval(iv, new):
    res, i, n = [], 0, len(iv)
    while i < n and iv[i][1] < new[0]: res.append(iv[i]); i += 1     # strictly before
    s, e = new
    while i < n and iv[i][0] <= e:                                   # overlapping: absorb
        s = min(s, iv[i][0]); e = max(e, iv[i][1]); i += 1
    res.append([s, e]); res.extend(iv[i:])
    return res

def erase_overlap(iv):
    """Minimum removals to make intervals non-overlapping = n - (max non-overlapping)."""
    iv = sorted(iv, key=lambda x: x[1])         # EARLIEST END is the correct greedy
    count, end = 0, float('-inf')
    for s, e in iv:
        if s >= end: count += 1; end = e
    return len(iv) - count

def min_rooms(iv):
    """Minimum meeting rooms = maximum concurrent intervals. Heap of end times."""
    heap = []
    for s, e in sorted(iv):
        if heap and heap[0] <= s: heapq.heappop(heap)   # a room freed up before this meeting starts
        heapq.heappush(heap, e)
    return len(heap)

def sweep_line_max_overlap(iv):
    """The other formulation: +1 at each start, -1 at each end, scan in time order."""
    ev = []
    for s, e in iv: ev.append((s, 1)); ev.append((e, -1))
    ev.sort()                                    # ties: (t,-1) sorts before (t,+1) since -1 < 1,
    cur = best = 0                               # which treats intervals as half-open [s, e)
    for _, d in ev:
        cur += d; best = max(best, cur)
    return best

Why “earliest end time” is the right greedy for maximum non-overlapping intervals: exchange argument. Take any optimal solution; its first interval ends no earlier than the globally earliest-ending interval, so swapping it in leaves the solution valid and no smaller. Repeat. Sorting by start time or by shortest duration both have easy counterexamples — be ready to produce one ([0,10],[1,2],[3,4] breaks sort-by-start).

The tie-breaking detail in the sweep line determines whether intervals that merely touch ([1,2] and [2,3]) count as overlapping. Processing -1 before +1 at the same timestamp treats them as half-open and non-overlapping. Ask the interviewer which convention they want; not asking is the mistake.

8. Cyclic sort and index-as-hash

Signal: the array contains numbers from a known small range, usually 1..n or 0..n, and the problem asks for a missing or duplicated value with O(1) extra space. The array itself is the hash table.

def missing_number(a):
    """Numbers 0..n with one missing. Gauss, or XOR to avoid overflow."""
    n = len(a)
    return n * (n + 1) // 2 - sum(a)

def find_disappeared(a):
    """Values in 1..n. Mark presence by negating a[v-1]. O(1) space, destroys signs."""
    for v in a:
        i = abs(v) - 1
        if a[i] > 0: a[i] = -a[i]
    return [i + 1 for i, v in enumerate(a) if v > 0]

def first_missing_positive(a):
    """Hardest of the family: O(n) time, O(1) space. Cyclic sort puts v at index v-1."""
    n = len(a)
    for i in range(n):
        while 1 <= a[i] <= n and a[a[i] - 1] != a[i]:      # while a[i] is misplaced AND placeable
            a[a[i] - 1], a[i] = a[i], a[a[i] - 1]
    for i in range(n):
        if a[i] != i + 1: return i + 1
    return n + 1

Two details. The while loop looks like it could be quadratic but is not: every successful swap puts one value in its final position, so there are at most n swaps total across the entire outer loop. And the loop condition must include a[a[i]-1] != a[i] — without it, duplicates cause an infinite swap between two equal values.

The three-way marking techniques (negation, adding n, XOR, or swapping) are all “use the input as storage”. They destroy or mutate the input, so the follow-up is always “what if the array is read-only?” — then it is a hash set (O(n) space) or binary search on the value range with a count predicate (O(n log n) time, O(1) space).

9. Backtracking

Signal: “all”, “every”, “how many ways”, “is it possible to arrange”, a board to fill, a set to enumerate. The state space is a tree; you DFS it, and you undo state on the way back up.

The template:

def backtrack(state):
    if state is a solution: record it; return
    if state cannot lead to a solution: return            # <- pruning is where the speed lives
    for each choice:
        apply choice
        backtrack(new state)
        undo choice                                        # <- the "backtracking"

def subsets(nums):
    """2^n subsets. Include/exclude formulation — the clearest for explaining the recursion tree."""
    res, cur = [], []
    def go(i):
        if i == len(nums): res.append(cur[:]); return       # cur[:] — COPY, or every entry aliases
        go(i + 1)                                           # exclude nums[i]
        cur.append(nums[i]); go(i + 1); cur.pop()           # include nums[i]
    go(0)
    return res

def permutations(nums):
    """n! permutations by swapping into position. O(1) extra space beyond the output."""
    res = []
    def go(start):
        if start == len(nums): res.append(nums[:]); return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            go(start + 1)
            nums[start], nums[i] = nums[i], nums[start]      # undo
    go(0)
    return res

def combination_sum(cands, target):
    """Unlimited reuse of each candidate. `go(i, ...)` (not i+1) is what allows reuse."""
    res, cur = [], []
    def go(i, remain):
        if remain == 0: res.append(cur[:]); return
        if remain < 0 or i == len(cands): return             # pruning
        cur.append(cands[i]); go(i, remain - cands[i]); cur.pop()
        go(i + 1, remain)
    go(0, target)
    return res

def subsets_with_dup(nums):
    """Duplicates in the input. Sort, then skip duplicate SIBLINGS (not duplicate ancestors)."""
    nums = sorted(nums); res, cur = [], []
    def go(start):
        res.append(cur[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: continue  # i > start, not i > 0
            cur.append(nums[i]); go(i + 1); cur.pop()
    go(0)
    return res

def n_queens(n):
    """Pruning with three sets: columns, and the two diagonal families r-c and r+c."""
    cols, d1, d2, res, board = set(), set(), set(), [], []
    def go(r):
        if r == n: res.append(board[:]); return
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2: continue
            cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
            go(r + 1)
            board.pop(); cols.remove(c); d1.remove(r - c); d2.remove(r + c)
    go(0)
    return res

def word_search(board, word):
    """Grid DFS with in-place visited marking — no separate visited set needed."""
    R, C = len(board), len(board[0])
    def go(r, c, i):
        if i == len(word): return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]: return False
        tmp, board[r][c] = board[r][c], '#'                 # mark
        found = any(go(r+dr, c+dc, i+1) for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)))
        board[r][c] = tmp                                    # unmark
        return found
    return any(go(r, c, 0) for r in range(R) for c in range(C))

Verified: n_queens(8) finds exactly 92 solutions, n_queens(4) finds 2.

The four things that go wrong

1. Not copying the accumulated state. res.append(cur) appends a reference; every entry ends up empty. cur[:] or list(cur) or [*cur].
2. Not undoing. The pop() / remove() / restore after the recursive call.
3. Wrong duplicate skip. i > start skips duplicate siblings at this level; i > 0 would also skip legitimate repeats deeper in the tree.
4. No pruning. Backtracking without pruning is brute force with extra steps. Prune on: exceeded target, insufficient remaining elements, already-worse-than-best, and any problem-specific invariant.

Bitmask as an alternative

For n <= ~20, an explicit bitmask is often shorter and faster than recursion:

function subsets<T>(nums: readonly T[]): T[][] {
  const res: T[][] = [];
  for (let mask = 0; mask < (1 << nums.length); mask++) {
    const cur: T[] = [];
    for (let i = 0; i < nums.length; i++) if (mask >> i & 1) cur.push(nums[i]!);
    res.push(cur);
  }
  return res;
}

And in TypeScript a lazy generator version is often the better API, because the caller can stop early without you enumerating 8! permutations:

function* permuteLazy<T>(nums: T[], start = 0): Generator<T[]> {
  if (start === nums.length) { yield [...nums]; return; }
  for (let i = start; i < nums.length; i++) {
    [nums[start], nums[i]] = [nums[i]!, nums[start]!];
    yield* permuteLazy(nums, start + 1);
    [nums[start], nums[i]] = [nums[i]!, nums[start]!];
  }
}

Python’s equivalent is simply making the function a generator and yielding instead of appending — and itertools.permutations/combinations/product already do it lazily in C.

10. Greedy

Signal: an optimization where a locally optimal choice is provably globally safe. The danger is that greedy feels right far more often than it is right, so the interview skill is being able to justify it — or to notice that you need DP instead.

Two proof techniques to name:

• Exchange argument: take any optimal solution, show you can swap in the greedy choice without making it worse. (Used above for earliest-end-time interval scheduling.)
• Greedy stays ahead: show by induction that after k steps the greedy solution is at least as good as any other solution’s first k steps.

def jump_game(a):
    """Can you reach the end? Track the furthest reachable index."""
    reach = 0
    for i, v in enumerate(a):
        if i > reach: return False
        reach = max(reach, i + v)
    return True

def jump_game_min(a):
    """Minimum jumps. This is BFS by levels, written as a scan."""
    jumps = end = far = 0
    for i in range(len(a) - 1):
        far = max(far, i + a[i])
        if i == end:                     # exhausted the current level
            jumps += 1; end = far        # commit to the next level
    return jumps

def gas_station(gas, cost):
    """Circular route. If total >= 0 a solution exists, and the start is just after the worst dip."""
    if sum(gas) < sum(cost): return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0: start = i + 1; tank = 0
    return start

def partition_labels(s):
    """Split so each letter appears in one part. Extend the current part to the last occurrence."""
    last = {c: i for i, c in enumerate(s)}
    res, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end: res.append(end - start + 1); start = i + 1
    return res

def task_scheduler(tasks, n):
    """Minimum time with a cooldown n between identical tasks. Closed form, no simulation."""
    cnt = Counter(tasks)
    mx = max(cnt.values())
    ties = sum(1 for v in cnt.values() if v == mx)
    return max(len(tasks), (mx - 1) * (n + 1) + ties)

The task_scheduler formula is worth understanding rather than memorizing: lay out the most frequent task with gaps, giving (mx-1) full frames of width (n+1), plus the final occurrences of every task tied at the maximum. If there are enough other tasks to fill the gaps, no idling is needed and the answer is just len(tasks) — hence the max.

Classic greedy problems and their sort keys

When greedy fails and you need DP: 0/1 knapsack (cannot take fractions), coin change with non-canonical denominations ([1, 3, 4], target 6: greedy gives 4+1+1, optimal is 3+3), longest increasing subsequence, and edit distance. The tell is that a choice now constrains future choices in a way you cannot evaluate locally.

11. Bit manipulation

Signal: “without extra space”, XOR-flavoured problems, subsets of a small set, “count set bits”, anything about powers of two, and state compression in DP.

x & 1          test the lowest bit (odd/even)
x >> k & 1     test bit k
x | (1 << k)   set bit k
x & ~(1 << k)  clear bit k
x ^ (1 << k)   flip bit k
x & (x - 1)    clear the LOWEST set bit          -> loop for popcount (Kernighan)
x & -x         isolate the LOWEST set bit        -> Fenwick trees, lowest differing bit
x | (x + 1)    set the lowest ZERO bit
x & (x - 1) == 0   is a power of two (for x > 0)
a ^ b ^ b == a     XOR is its own inverse        -> the whole "single number" family

def single_number(a):
    """Every element appears twice except one. XOR cancels the pairs."""
    r = 0
    for v in a: r ^= v
    return r

def single_number_two_uniques(a):
    """TWO elements appear once. Partition by the lowest bit where they differ."""
    xor = 0
    for v in a: xor ^= v                  # xor == x ^ y
    low = xor & -xor                      # a bit where x and y must differ
    x = y = 0
    for v in a:
        if v & low: x ^= v
        else:       y ^= v
    return sorted((x, y))

def count_bits(n):
    """Popcount for 0..n in O(n). dp[i] = dp[i >> 1] + (i & 1)."""
    dp = [0] * (n + 1)
    for i in range(1, n + 1): dp[i] = dp[i >> 1] + (i & 1)
    return dp

def is_power_of_two(n): return n > 0 and n & (n - 1) == 0

def reverse_bits32(n):
    r = 0
    for _ in range(32): r = (r << 1) | (n & 1); n >>= 1
    return r

def add_without_plus(a, b):
    """XOR is the sum without carry; (a & b) << 1 is the carry. Loop until no carry.
       Python needs an explicit 32-bit mask because its ints are unbounded."""
    MASK = 0xFFFFFFFF
    while b:
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)

Language differences that matter

Python’s unbounded ints make it unexpectedly pleasant for bitmask problems (no overflow to reason about), but they also mean you must mask explicitly when emulating fixed-width arithmetic — as add_without_plus shows. In JavaScript the opposite applies: everything is silently 32-bit, so Math.imul exists for 32-bit multiplication and >>> 0 is how you force an unsigned interpretation. Getting that wrong produces the exact bug documented in Data structures §22.

Bitmask DP (subsets of up to ~20 elements as a state) is in Dynamic programming.

12. String algorithms

def kmp_search(text, pat):
    """Knuth-Morris-Pratt. O(n + m), no backtracking in the text. The LPS table is the whole idea."""
    if not pat: return 0
    lps = [0] * len(pat); k = 0                # lps[i] = length of the longest proper prefix
    for i in range(1, len(pat)):               #          of pat[:i+1] that is also a suffix
        while k and pat[i] != pat[k]: k = lps[k-1]
        if pat[i] == pat[k]: k += 1
        lps[i] = k
    k = 0
    for i, ch in enumerate(text):
        while k and ch != pat[k]: k = lps[k-1] # fall back within the PATTERN, never rewind the text
        if ch == pat[k]:
            k += 1
            if k == len(pat): return i - k + 1
    return -1

def rabin_karp(text, pat, base=256, mod=(1 << 61) - 1):
    """Rolling hash. O(n + m) expected; ALWAYS verify on a hash match — hashes collide."""
    n, m = len(text), len(pat)
    if m > n: return -1
    hp = ht = 0
    power = pow(base, m - 1, mod)
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % mod
        ht = (ht * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if hp == ht and text[i:i+m] == pat: return i        # the verification step
        if i + m < n:
            ht = ((ht - ord(text[i]) * power) * base + ord(text[i+m])) % mod
    return -1

def longest_palindrome_expand(s):
    """Expand around 2n-1 centers. O(n^2) time, O(1) space — the answer to give unless asked for O(n)."""
    if not s: return ""
    best = (0, 0)
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):                   # odd and even centers
            while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1
            if r - l - 2 > best[1] - best[0]: best = (l + 1, r - 1)
    return s[best[0]:best[1]+1]

def group_anagrams(words):
    g = defaultdict(list)
    for w in words: g[''.join(sorted(w))].append(w)          # sorted string as the canonical key
    return list(g.values())

def encode_decode(strs):
    """Length-prefixed encoding: delimiter-safe, unlike joining on a separator."""
    enc = ''.join(f"{len(s)}#{s}" for s in strs)
    res, i = [], 0
    while i < len(enc):
        j = enc.index('#', i); n = int(enc[i:j])
        res.append(enc[j+1:j+1+n]); i = j + 1 + n
    return res

Two things to say about the built-ins: Python’s in and str.find use a Crochemore-Perrin variant that is near-linear in practice, so “just use in” is usually correct and the interviewer is asking for KMP to test your understanding, not your judgement. And re is a backtracking engine, so a pattern like (a+)+$ against 'aaaa...b' is exponential — catastrophic backtracking is a real availability bug (ReDoS), and the fixes are atomic groups / possessive quantifiers (Python 3.11+), rewriting the pattern, or using a non-backtracking engine.

13. Matrix patterns

def rotate90(m):
    """Rotate clockwise in place: reverse the rows, then transpose."""
    m.reverse()
    for i in range(len(m)):
        for j in range(i + 1, len(m)):
            m[i][j], m[j][i] = m[j][i], m[i][j]
    return m

def spiral(m):
    """Peel the top row, rotate the rest counter-clockwise, repeat. Short and clear."""
    res = []
    while m:
        res += m.pop(0)
        m = [list(r) for r in zip(*m)][::-1]
    return res

def set_zeroes(m):
    """If a cell is 0, zero its row and column. O(1) extra space by using row 0 / col 0 as markers."""
    R, C = len(m), len(m[0])
    first_col = any(m[r][0] == 0 for r in range(R))       # col 0 needs its own flag
    for r in range(R):
        for c in range(1, C):
            if m[r][c] == 0: m[r][0] = 0; m[0][c] = 0
    for r in range(R - 1, -1, -1):                        # write BACKWARDS so markers survive
        for c in range(C - 1, 0, -1):
            if m[r][0] == 0 or m[0][c] == 0: m[r][c] = 0
        if first_col: m[r][0] = 0
    return m

The recurring matrix techniques:

• Direction vectors: for dr, dc in ((0,1),(1,0),(0,-1),(-1,0)) for 4-connectivity, plus the four diagonals for 8-connectivity. Write it once at the top.
• Bounds check as a helper: in_bounds(r, c) beats four inline comparisons repeated six times.
• In-place visited marking (overwrite with a sentinel) when you are allowed to mutate; a set of (r, c) otherwise.
• Layer-by-layer traversal with four boundary variables (top, bottom, left, right) for spiral and rotation when you cannot allocate.
• Diagonals are indexed by r + c (anti-diagonal) and r - c (main diagonal) — the same trick as N-Queens, and the key to “diagonal traversal” and “toeplitz matrix”.
• Row/column as storage for the O(1)-space marking trick above.

Grid BFS/DFS, islands, shortest path in a maze, and multi-source BFS are in Graphs and trees; grid DP (unique paths, minimum path sum) is in Dynamic programming.

14. Test run

  ok  two pointers: two-sum sorted, 3sum w/ dedup, in-place dedup, container, rain water, palindrome
  ok  fast/slow beyond linked lists: find-duplicate, happy number (cycle in a functional graph)
  ok  sliding window: fixed, variable, min-window-substring, char-replace, min-len, monotonic-deque max
  ok  prefix sums: subarray-sum-k, 2D prefix, product-except-self, difference array, 0/1 balance
  ok  monotonic stack: next-greater, daily-temps, largest-rectangle, rain water, remove-k-digits
  ok  intervals: merge, insert, erase-overlap (sort by END), meeting rooms via heap and via sweep line
  ok  cyclic sort / index-as-hash: missing number, disappeared numbers, first missing positive
  ok  backtracking: subsets, permutations, combination-sum, dedup subsets, n-queens(8)=92, word search
  ok  greedy: jump game (+min jumps), gas station, partition labels, task scheduler
  ok  bits: xor single number, two uniques via lowest set bit, count-bits DP, bitmask subsets, add without +
  ok  strings: KMP (with LPS), Rabin-Karp rolling hash, expand-around-center, anagram grouping, encode/decode
  ok  matrix: rotate 90 in place, spiral order, set-zeroes with O(1) extra space

ALL PATTERN ASSERTIONS PASSED (12 families)

  ok  TypeScript: two pointers, sliding window (index cursor, not shift), prefix-sum map, monotonic deque
  ok  TypeScript: monotonic stack, interval merge, bitmask subsets, permutations (eager + lazy generator), KMP

15. Interview questions

Q: How do you decide between sliding window and prefix sums?

A: Sliding window needs the constraint to be monotone in the window — adding an element only makes it harder, removing only easier. That holds for “sum >= k” with non-negative values, and fails with negatives. When it fails, prefix sums plus a hash map still work because they consider all O(n^2) pairs implicitly in O(n).

Q: Why is a nested while inside a for still O(n)?

A: Because the inner pointer never resets. Count total iterations, not nesting depth: left advances at most n times across the whole run, so the total is O(n). If left were reset each outer iteration it really would be quadratic.

Q: When would you use a monotonic stack instead of a heap?

A: When the question is about positional relationships — next greater element, spans, histogram areas — and each element becomes permanently irrelevant once a dominating element appears. A heap gives you the global extremum; a monotonic stack gives you the nearest one in a direction.

Q: Explain the sliding-window-maximum deque invariant.

A: The deque holds indices with strictly decreasing values. Before pushing i, pop every index whose value is <= a[i], because those can never be the maximum of any window containing i. Then evict the front if it has left the window. The front is always the current maximum, and each index is pushed and popped once, so it is O(n).

Q: Sort intervals by start or by end?

A: By start for merging and for “how many concurrent”; by end for “maximum non-overlapping” and minimum-removals. The exchange argument justifies earliest-end: the globally earliest-ending interval can always be swapped into an optimal solution.

Q: How do you prove a greedy algorithm correct?

A: Exchange argument (transform any optimal solution into the greedy one without loss) or “greedy stays ahead” (induct on prefixes). If neither works, look for a counterexample — and if you find one, the answer is DP.

Q: Give an example where greedy fails but DP works.

A: Coin change with [1, 3, 4] and target 6: greedy takes 4 then 1 then 1 (three coins); optimal is 3+3 (two). Also 0/1 knapsack — the fractional version is greedy, the integral version is not.

Q: Backtracking versus DP — how do you tell?

A: Backtracking enumerates or searches for a solution and undoes state. DP applies when the subproblems overlap and you only need an optimum or a count, so you memoize instead of re-exploring. “Count the ways” with overlapping states is DP; “list all the ways” is backtracking.

Q: How do you handle duplicates in subsets/permutations?

A: Sort the input, then at each level skip a candidate equal to its immediate predecessor within that level (if i > start and a[i] == a[i-1]: continue). For permutations with duplicates, a count map or a per-level used-set is cleaner.

Q: Why cur[:] and not cur when recording a backtracking solution?

A: cur is mutated by the rest of the search, so appending a reference makes every recorded solution end up identical (usually empty). You must snapshot.

Q: What is the complexity of generating all subsets?

A: O(n·2^n), not O(2^n) — there are 2^n subsets and copying each costs O(n). People routinely drop the n.

Q: How do you find a duplicate in an array of n+1 integers from 1..n without modifying it and in O(1) space?

A: Floyd’s cycle detection on the functional graph i -> nums[i]. The duplicate is the cycle entry. Alternative: binary search on the value range, counting how many elements are <= mid — O(n log n) time, also O(1) space, and it works when the array is read-only and you distrust the pointer trick.

Q: XOR tricks — what is the single most useful identity?

A: a ^ a == 0 and a ^ 0 == a, so XOR-ing a whole array cancels every pair. That solves the entire “single number” family, “missing number”, and “find the two unique numbers” (partition by xor & -xor, the lowest differing bit).

Q: When does binary search apply to something that is not a sorted array?

A: Whenever the predicate is monotone. Examples: binary searching the answer for “minimize the maximum” problems, integer square root, peak finding in a bitonic array (a local comparison suffices), and exponential search over an unbounded sequence.

Q: How do you avoid re-deriving the sliding-window loop under pressure?

A: Memorize one template — expand with right, shrink with a while, record the answer — and learn which side of the while the recording goes on: after the loop for “longest”, inside it for “shortest”.

Q: What is catastrophic backtracking and why should you care?

A: A regex whose nested quantifiers cause exponential matching time ((a+)+$ against 'aaaa...b'). It is a real denial-of-service vector on any service that applies user-supplied or user-influenced patterns. Fixes: atomic groups/possessive quantifiers (Python 3.11+), rewriting the pattern, input length limits, or a non-backtracking engine (RE2).

Q: KMP or Rabin-Karp?

A: KMP for a single pattern with a worst-case guarantee. Rabin-Karp when you have many patterns of equal length, or need 2D pattern matching, or want a simpler implementation — but you must verify on hash equality, because a hash match is not a match.

Q: How do you rotate a matrix 90 degrees in place?

A: Reverse the rows, then transpose (for clockwise); transpose then reverse rows for counter-clockwise. Both are O(n^2) time, O(1) space. The layer-by-layer four-way swap is the alternative and is easier to get wrong.

Q: Give me a problem where the “obvious” O(n) space can be reduced to O(1).

A: “Set matrix zeroes” — use row 0 and column 0 as the marker arrays, with one extra boolean for column 0 itself, and write back in reverse order so the markers survive until they are read.

Q: In JavaScript, what is the most common way to accidentally make a linear algorithm quadratic?

A: arr.shift() or arr.splice(0, 1) as a queue dequeue — both O(n). Use an index cursor or a ring buffer. In Python the equivalent is list.pop(0) instead of collections.deque.popleft.

Q: How would you approach a problem you have never seen?

A: State the brute force and its complexity; identify what it recomputes; match the “what it recomputes” to a pattern from the table (repeated range sums -> prefix sums; repeated maxima -> heap or monotonic structure; repeated subproblems -> DP; repeated membership -> hash set); then check the constraints to confirm the target complexity.

Next: Graphs and trees and Dynamic programming.

Verify it yourself

pat/p.py

from collections import defaultdict, deque, Counter
from typing import List
import heapq, bisect
out=[]
def ok(m): out.append("  ok  "+m)

# ---------- two pointers ----------
def two_sum_sorted(a, t):
    i, j = 0, len(a)-1
    while i < j:
        s = a[i]+a[j]
        if s == t: return (i, j)
        if s < t: i += 1
        else: j -= 1
    return None
def three_sum(nums):
    nums = sorted(nums); res = []
    for i in range(len(nums)-2):
        if i and nums[i] == nums[i-1]: continue            # skip duplicate anchors
        if nums[i] > 0: break
        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]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
    return res
def remove_dups_inplace(a):
    if not a: return 0
    w = 1
    for r in range(1, len(a)):
        if a[r] != a[w-1]: a[w] = a[r]; w += 1
    return w
def container_water(h):
    i, j, best = 0, len(h)-1, 0
    while i < j:
        best = max(best, (j-i)*min(h[i], h[j]))
        if h[i] < h[j]: i += 1                              # move the SHORTER side
        else: j -= 1
    return best
def trapping_rain(h):
    i, j, li, rj, total = 0, len(h)-1, 0, 0, 0
    while i < j:
        if h[i] < h[j]:
            li = max(li, h[i]); total += li - h[i]; i += 1
        else:
            rj = max(rj, h[j]); total += rj - h[j]; j -= 1
    return total
def is_palindrome_alnum(s):
    i, j = 0, len(s)-1
    while i < j:
        while i < j and not s[i].isalnum(): i += 1
        while i < j and not s[j].isalnum(): j -= 1
        if s[i].lower() != s[j].lower(): return False
        i += 1; j -= 1
    return True
assert two_sum_sorted([2,7,11,15], 9) == (0,1)
assert three_sum([-1,0,1,2,-1,-4]) == [[-1,-1,2],[-1,0,1]]
a=[1,1,2,2,3]; assert remove_dups_inplace(a)==3 and a[:3]==[1,2,3]
assert container_water([1,8,6,2,5,4,8,3,7])==49
assert trapping_rain([0,1,0,2,1,0,1,3,2,1,2,1])==6
assert is_palindrome_alnum("A man, a plan, a canal: Panama") and not is_palindrome_alnum("race a car")
ok("two pointers: two-sum sorted, 3sum w/ dedup, in-place dedup, container, rain water, palindrome")

# ---------- fast/slow ----------
def find_duplicate(nums):        # Floyd on the index->value functional graph
    slow = fast = nums[0]
    while True:
        slow = nums[slow]; fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast: slow = nums[slow]; fast = nums[fast]
    return slow
def happy(n):
    def nxt(x): return sum(int(c)**2 for c in str(x))
    slow = fast = n
    while True:
        slow = nxt(slow); fast = nxt(nxt(fast))
        if fast == 1: return True
        if slow == fast: return slow == 1
assert find_duplicate([1,3,4,2,2])==2 and find_duplicate([3,1,3,4,2])==3
assert happy(19) and not happy(2)
ok("fast/slow beyond linked lists: find-duplicate, happy number (cycle in a functional graph)")

# ---------- sliding window ----------
def max_sum_window(a, k):                                  # fixed size
    s = sum(a[:k]); best = s
    for i in range(k, len(a)):
        s += a[i] - a[i-k]; best = max(best, s)
    return best
def longest_unique(s):                                     # variable size, shrink on violation
    last = {}; best = start = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start: start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best
def min_window_substring(s, t):
    if not t or not s: return ""
    need = Counter(t); missing = len(t); best = (float('inf'), 0, 0); left = 0
    for right, ch in enumerate(s):
        if need[ch] > 0: missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left < best[0] - 1: best = (right-left+1, left, right)
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2]+1]
def longest_repeat_replace(s, k):                          # at most k character replacements
    cnt = Counter(); left = maxf = best = 0
    for right, ch in enumerate(s):
        cnt[ch] += 1; maxf = max(maxf, cnt[ch])
        while (right-left+1) - maxf > k:
            cnt[s[left]] -= 1; left += 1
        best = max(best, right-left+1)
    return best
def min_subarray_len(target, a):                           # smallest window with sum >= target
    left = s = 0; best = float('inf')
    for right, v in enumerate(a):
        s += v
        while s >= target: best = min(best, right-left+1); s -= a[left]; left += 1
    return 0 if best == float('inf') else best
def sliding_window_max(a, k):                              # monotonic deque
    dq, res = deque(), []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v: dq.pop()              # pop smaller values: they can never win
        dq.append(i)
        if dq[0] <= i-k: dq.popleft()                      # drop out-of-window index
        if i >= k-1: res.append(a[dq[0]])
    return res
assert max_sum_window([2,1,5,1,3,2],3)==9
assert longest_unique("abcabcbb")==3 and longest_unique("bbbbb")==1 and longest_unique("pwwkew")==3
assert min_window_substring("ADOBECODEBANC","ABC")=="BANC"
assert longest_repeat_replace("AABABBA",1)==4
assert min_subarray_len(7,[2,3,1,2,4,3])==2
assert sliding_window_max([1,3,-1,-3,5,3,6,7],3)==[3,3,5,5,6,7]
ok("sliding window: fixed, variable, min-window-substring, char-replace, min-len, monotonic-deque max")

# ---------- prefix sums ----------
def subarray_sum_equals_k(a, k):
    seen = defaultdict(int); seen[0] = 1; running = count = 0
    for v in a:
        running += v
        count += seen[running - k]                          # how many prefixes make a valid suffix
        seen[running] += 1
    return count
def range_sum_2d(mat):
    m, n = len(mat), len(mat[0])
    ps = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            ps[i+1][j+1] = mat[i][j] + ps[i][j+1] + ps[i+1][j] - ps[i][j]
    def q(r1,c1,r2,c2): return ps[r2+1][c2+1]-ps[r1][c2+1]-ps[r2+1][c1]+ps[r1][c1]
    return q
def product_except_self(a):
    n = len(a); res = [1]*n
    left = 1
    for i in range(n): res[i] = left; left *= a[i]
    right = 1
    for i in range(n-1,-1,-1): res[i] *= right; right *= a[i]
    return res
def difference_array(n, updates):                           # range add, O(1) each, then one pass
    d = [0]*(n+1)
    for l, r, v in updates: d[l] += v; d[r+1] -= v
    out2, run = [], 0
    for i in range(n): run += d[i]; out2.append(run)
    return out2
def longest_subarray_equal_01(a):
    seen = {0: -1}; running = best = 0
    for i, v in enumerate(a):
        running += 1 if v else -1
        if running in seen: best = max(best, i - seen[running])
        else: seen[running] = i
    return best
assert subarray_sum_equals_k([1,1,1],2)==2 and subarray_sum_equals_k([1,2,3],3)==2
q = range_sum_2d([[1,2],[3,4]]); assert q(0,0,1,1)==10 and q(1,1,1,1)==4
assert product_except_self([1,2,3,4])==[24,12,8,6]
assert difference_array(5,[(1,3,2),(0,1,1)])==[1,3,2,2,0]
assert longest_subarray_equal_01([0,1,0,1,1,0])==6
ok("prefix sums: subarray-sum-k, 2D prefix, product-except-self, difference array, 0/1 balance")

# ---------- monotonic stack ----------
def next_greater(a):
    res = [-1]*len(a); st = []
    for i, v in enumerate(a):
        while st and a[st[-1]] < v: res[st.pop()] = v
        st.append(i)
    return res
def daily_temperatures(t):
    res = [0]*len(t); st = []
    for i, v in enumerate(t):
        while st and t[st[-1]] < v: j = st.pop(); res[j] = i - j
        st.append(i)
    return res
def largest_rectangle(h):
    """Monotonic increasing stack of indices; a sentinel 0 at the end flushes it."""
    st, best = [], 0
    for i, v in enumerate(h + [0]):
        while st and h[st[-1]] >= v:
            top = st.pop()
            left = st[-1] + 1 if st else 0
            best = max(best, h[top] * (i - left))
        st.append(i)
    return best
def trapping_rain_stack(h):
    st, total = [], 0
    for i, v in enumerate(h):
        while st and h[st[-1]] < v:
            mid = st.pop()
            if not st: break
            width = i - st[-1] - 1
            height = min(h[st[-1]], v) - h[mid]
            total += width*height
        st.append(i)
    return total
def remove_k_digits(num, k):
    st = []
    for ch in num:
        while k and st and st[-1] > ch: st.pop(); k -= 1
        st.append(ch)
    st = st[:len(st)-k] if k else st
    return ''.join(st).lstrip('0') or '0'
assert next_greater([2,1,2,4,3])==[4,2,4,-1,-1]
assert daily_temperatures([73,74,75,71,69,72,76,73])==[1,1,4,2,1,1,0,0]
assert largest_rectangle([2,1,5,6,2,3])==10
assert trapping_rain_stack([0,1,0,2,1,0,1,3,2,1,2,1])==6
assert remove_k_digits("1432219",3)=="1219" and remove_k_digits("10200",1)=="200"
ok("monotonic stack: next-greater, daily-temps, largest-rectangle, rain water, remove-k-digits")

# ---------- intervals ----------
def merge_intervals(iv):
    iv = sorted(iv); res = []
    for s,e in iv:
        if res and s <= res[-1][1]: res[-1][1] = max(res[-1][1], e)
        else: res.append([s,e])
    return res
def insert_interval(iv, new):
    res, i, n = [], 0, len(iv)
    while i < n and iv[i][1] < new[0]: res.append(iv[i]); i += 1
    s, e = new
    while i < n and iv[i][0] <= e: s = min(s, iv[i][0]); e = max(e, iv[i][1]); i += 1
    res.append([s,e]); res.extend(iv[i:])
    return res
def erase_overlap(iv):                                       # min removals = n - max non-overlapping
    iv = sorted(iv, key=lambda x: x[1])                      # by EARLIEST END
    count, end = 0, float('-inf')
    for s,e in iv:
        if s >= end: count += 1; end = e
    return len(iv)-count
def min_rooms(iv):
    heap = []
    for s,e in sorted(iv):
        if heap and heap[0] <= s: heapq.heappop(heap)
        heapq.heappush(heap, e)
    return len(heap)
def sweep_line_max_overlap(iv):
    ev = []
    for s,e in iv: ev.append((s,1)); ev.append((e,-1))
    ev.sort()                                                # ties: -1 before +1 because -1 < 1
    cur = best = 0
    for _, d in ev: cur += d; best = max(best, cur)
    return best
assert merge_intervals([[1,3],[2,6],[8,10],[15,18]])==[[1,6],[8,10],[15,18]]
assert insert_interval([[1,3],[6,9]],[2,5])==[[1,5],[6,9]]
assert erase_overlap([[1,2],[2,3],[3,4],[1,3]])==1
assert min_rooms([[0,30],[5,10],[15,20]])==2
assert sweep_line_max_overlap([[0,30],[5,10],[15,20]])==2
ok("intervals: merge, insert, erase-overlap (sort by END), meeting rooms via heap and via sweep line")

# ---------- cyclic sort / index-as-hash ----------
def missing_number(a):
    n = len(a); return n*(n+1)//2 - sum(a)
def find_disappeared(a):                                     # index as hash, O(1) space
    for v in a:
        i = abs(v)-1
        if a[i] > 0: a[i] = -a[i]
    return [i+1 for i,v in enumerate(a) if v > 0]
def first_missing_positive(a):
    n = len(a)
    for i in range(n):
        while 1 <= a[i] <= n and a[a[i]-1] != a[i]:
            a[a[i]-1], a[i] = a[i], a[a[i]-1]                # cyclic sort: put v at index v-1
    for i in range(n):
        if a[i] != i+1: return i+1
    return n+1
assert missing_number([3,0,1])==2
assert find_disappeared([4,3,2,7,8,2,3,1])==[5,6]
assert first_missing_positive([3,4,-1,1])==2 and first_missing_positive([1,2,0])==3
ok("cyclic sort / index-as-hash: missing number, disappeared numbers, first missing positive")

# ---------- backtracking ----------
def subsets(nums):
    res, cur = [], []
    def go(i):
        if i == len(nums): res.append(cur[:]); return
        go(i+1)                                              # exclude
        cur.append(nums[i]); go(i+1); cur.pop()               # include
    go(0); return res
def permutations(nums):
    res = []
    def go(start):
        if start == len(nums): res.append(nums[:]); return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            go(start+1)
            nums[start], nums[i] = nums[i], nums[start]
    go(0); return res
def combination_sum(cands, target):
    res, cur = [], []
    def go(i, remain):
        if remain == 0: res.append(cur[:]); return
        if remain < 0 or i == len(cands): return
        cur.append(cands[i]); go(i, remain-cands[i]); cur.pop()   # reuse allowed
        go(i+1, remain)
    go(0, target); return res
def subsets_with_dup(nums):
    nums = sorted(nums); res, cur = [], []
    def go(start):
        res.append(cur[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: continue   # skip duplicate siblings
            cur.append(nums[i]); go(i+1); cur.pop()
    go(0); return res
def n_queens(n):
    cols, d1, d2, res, board = set(), set(), set(), [], []
    def go(r):
        if r == n: res.append(board[:]); return
        for c in range(n):
            if c in cols or (r-c) in d1 or (r+c) in d2: continue
            cols.add(c); d1.add(r-c); d2.add(r+c); board.append(c)
            go(r+1)
            board.pop(); cols.remove(c); d1.remove(r-c); d2.remove(r+c)
    go(0); return res
def word_search(board, word):
    R, C = len(board), len(board[0])
    def go(r, c, i):
        if i == len(word): return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]: return False
        tmp, board[r][c] = board[r][c], '#'                  # mark visited in place
        found = any(go(r+dr, c+dc, i+1) for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)))
        board[r][c] = tmp
        return found
    return any(go(r,c,0) for r in range(R) for c in range(C))
assert len(subsets([1,2,3]))==8
assert len(permutations([1,2,3]))==6
assert sorted(combination_sum([2,3,6,7],7))==sorted([[2,2,3],[7]])
assert subsets_with_dup([1,2,2])==[[],[1],[1,2],[1,2,2],[2],[2,2]]
assert len(n_queens(8))==92 and len(n_queens(4))==2
assert word_search([list("ABCE"),list("SFCS"),list("ADEE")],"ABCCED")
ok("backtracking: subsets, permutations, combination-sum, dedup subsets, n-queens(8)=92, word search")

# ---------- greedy ----------
def jump_game(a):
    reach = 0
    for i, v in enumerate(a):
        if i > reach: return False
        reach = max(reach, i+v)
    return True
def jump_game_min(a):
    jumps = end = far = 0
    for i in range(len(a)-1):
        far = max(far, i+a[i])
        if i == end: jumps += 1; end = far                   # BFS-by-levels in disguise
    return jumps
def gas_station(gas, cost):
    if sum(gas) < sum(cost): return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i]-cost[i]
        if tank < 0: start = i+1; tank = 0
    return start
def partition_labels(s):
    last = {c:i for i,c in enumerate(s)}
    res, start, end = [], 0, 0
    for i,c in enumerate(s):
        end = max(end, last[c])
        if i == end: res.append(end-start+1); start = i+1
    return res
def task_scheduler(tasks, n):
    cnt = Counter(tasks); mx = max(cnt.values()); ties = sum(1 for v in cnt.values() if v == mx)
    return max(len(tasks), (mx-1)*(n+1)+ties)
assert jump_game([2,3,1,1,4]) and not jump_game([3,2,1,0,4])
assert jump_game_min([2,3,1,1,4])==2
assert gas_station([1,2,3,4,5],[3,4,5,1,2])==3
assert partition_labels("ababcbacadefegdehijhklij")==[9,7,8]
assert task_scheduler(list("AAABBB"),2)==8
ok("greedy: jump game (+min jumps), gas station, partition labels, task scheduler")

# ---------- bit manipulation ----------
def single_number(a):
    r = 0
    for v in a: r ^= v
    return r
def single_number_two_uniques(a):
    xor = 0
    for v in a: xor ^= v
    low = xor & -xor                                          # lowest differing bit
    x = y = 0
    for v in a:
        if v & low: x ^= v
        else: y ^= v
    return sorted((x,y))
def count_bits(n):
    dp = [0]*(n+1)
    for i in range(1, n+1): dp[i] = dp[i >> 1] + (i & 1)
    return dp
def subsets_bitmask(a):
    n = len(a)
    return [[a[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]
def is_power_of_two(n): return n > 0 and n & (n-1) == 0
def swap_no_temp(a, b): return b ^ (a ^ b) ^ 0, a ^ (a ^ b) ^ 0
def reverse_bits32(n):
    r = 0
    for _ in range(32): r = (r << 1) | (n & 1); n >>= 1
    return r
def add_without_plus(a, b):
    MASK = 0xFFFFFFFF
    while b:
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)
assert single_number([4,1,2,1,2])==4
assert single_number_two_uniques([1,2,1,3,2,5])==[3,5]
assert count_bits(5)==[0,1,1,2,1,2]
assert len(subsets_bitmask([1,2,3]))==8
assert is_power_of_two(16) and not is_power_of_two(18)
assert reverse_bits32(0b1)==1<<31
assert add_without_plus(7,5)==12 and add_without_plus(-3,5)==2
assert bin(12).count('1')==2 and (12).bit_count() if hasattr(int,'bit_count') else True
ok("bits: xor single number, two uniques via lowest set bit, count-bits DP, bitmask subsets, add without +")

# ---------- strings ----------
def kmp_search(text, pat):
    if not pat: return 0
    lps = [0]*len(pat); k = 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]: k = lps[k-1]
        if pat[i] == pat[k]: k += 1
        lps[i] = k
    k = 0
    for i, ch in enumerate(text):
        while k and ch != pat[k]: k = lps[k-1]
        if ch == pat[k]:
            k += 1
            if k == len(pat): return i-k+1
    return -1
def rabin_karp(text, pat, base=256, mod=(1<<61)-1):
    n, m = len(text), len(pat)
    if m > n: return -1
    hp = 0; ht = 0; power = pow(base, m-1, mod)
    for i in range(m):
        hp = (hp*base + ord(pat[i])) % mod
        ht = (ht*base + ord(text[i])) % mod
    for i in range(n-m+1):
        if hp == ht and text[i:i+m] == pat: return i          # verify: hashes can collide
        if i+m < n:
            ht = ((ht - ord(text[i])*power) * base + ord(text[i+m])) % mod
    return -1
def longest_palindrome_expand(s):
    if not s: return ""
    best = (0, 0)
    for c in range(len(s)):
        for l, r in ((c, c), (c, c+1)):                       # odd and even centers
            while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1
            if r-l-2 > best[1]-best[0]: best = (l+1, r-1)
    return s[best[0]:best[1]+1]
def group_anagrams(words):
    g = defaultdict(list)
    for w in words: g[''.join(sorted(w))].append(w)
    return list(g.values())
def is_anagram(a, b): return Counter(a) == Counter(b)
def encode_decode(strs):
    enc = ''.join(f"{len(s)}#{s}" for s in strs)              # length-prefixed: delimiter-safe
    res, i = [], 0
    while i < len(enc):
        j = enc.index('#', i); n = int(enc[i:j])
        res.append(enc[j+1:j+1+n]); i = j+1+n
    return res
assert kmp_search("ababcabcabababd","ababd")==10
assert kmp_search("aaaaa","bba")==-1
assert rabin_karp("ababcabcabababd","ababd")==10
assert longest_palindrome_expand("babad") in ("bab","aba")
assert longest_palindrome_expand("cbbd")=="bb"
assert len(group_anagrams(["eat","tea","tan","ate","nat","bat"]))==3
assert is_anagram("listen","silent")
assert encode_decode(["a#b","","x"])==["a#b","","x"]
ok("strings: KMP (with LPS), Rabin-Karp rolling hash, expand-around-center, anagram grouping, encode/decode")

# ---------- matrix ----------
def rotate90(m):
    m.reverse()                                              # transpose after reversing rows
    for i in range(len(m)):
        for j in range(i+1, len(m)):
            m[i][j], m[j][i] = m[j][i], m[i][j]
    return m
def spiral(m):
    res = []
    while m:
        res += m.pop(0)
        m = [list(r) for r in zip(*m)][::-1]                 # rotate counter-clockwise
    return res
def set_zeroes(m):
    R, C = len(m), len(m[0])
    first_col = any(m[r][0] == 0 for r in range(R))
    for r in range(R):
        for c in range(1, C):
            if m[r][c] == 0: m[r][0] = 0; m[0][c] = 0        # use row 0 / col 0 as markers
    for r in range(R-1, -1, -1):
        for c in range(C-1, 0, -1):
            if m[r][0] == 0 or m[0][c] == 0: m[r][c] = 0
        if first_col: m[r][0] = 0
    return m
assert rotate90([[1,2],[3,4]])==[[3,1],[4,2]]
assert spiral([[1,2,3],[4,5,6],[7,8,9]])==[1,2,3,6,9,8,7,4,5]
assert set_zeroes([[1,1,1],[1,0,1],[1,1,1]])==[[1,0,1],[0,0,0],[1,0,1]]
ok("matrix: rotate 90 in place, spiral order, set-zeroes with O(1) extra space")

print("\n".join(out)); print(f"\nALL PATTERN ASSERTIONS PASSED ({len(out)} families)")