Algorithm patterns — if it says X, reach for Y

cue: sorted, pair/triplet, palindrome, in-place dedupe. Ends move inward; fast/slow finds a cycle or the middle.

var l = 0, r = a.count - 1
while l < r {
  let s = a[l] + a[r]
  if s == t { return (l, r) }
  if s < t { l += 1 } else { r -= 1 } }

cue: contiguous + constraint. Fixed k: sum += a[i] - a[i-k]. Variable: grow right, shrink left while invalid — each index enters and leaves once.

var l = 0
for r in 0..<n { add(a[r])
  while !valid { remove(a[l]); l += 1 }
  best = max(best, r - l + 1) }

cue: complement: look up before inserting (no self-pair) · frequency · canonical key (sorted chars) to group anagrams.

if let j = seen[t - x] { return [j, i] }
seen[x] = i
freq[c, default: 0] += 1

Prefix-sum map (sum = k, negatives ok), seed [0: 1]:

p += x
count += seen[p - k, default: 0]
seen[p, default: 0] += 1

cue: sorted, first/last position, insert point. One template (half-open lower bound), never mix:

var lo = 0, hi = a.count        // [lo, hi)
while lo < hi {
  let m = lo + (hi - lo) / 2    // no overflow
  if a[m] < t { lo = m + 1 } else { hi = m } }
// lo = first index with a[lo] >= t

On the answer (min speed / capacity, “minimise the max”): ok(x) flips once → lo = minAns, hi = maxAns, then if ok(m) { hi = m } else { lo = m + 1 }. O(n log range).

cue: top K, k-th largest, merge K lists, running median (two heaps). A min-heap of size k keeps the k largest. Swift has no heap — say so, then: sort O(n log n), a small binary heap, or quickselect (avg O(n)). Top-K frequent: bucket by count, O(n).

let top = freq.sorted { $0.value > $1.value }
              .prefix(k).map(\.key)

cue: next greater/smaller, stock span, daily temperatures, largest rectangle. Keep indices; pop while the new value beats the top.

for i in 0..<n {
  while let j = st.last, a[j] < a[i] {
    ans[j] = a[i]; st.removeLast() }
  st.append(i) }

cue: BFS = levels = shortest unweighted path; DFS = connectivity, flood fill, cycles. Mark visited on enqueue.

var q = [s], head = 0, seen: Set = [s]
while head < q.count {     // head: O(1) pop
  let u = q[head]; head += 1
  for v in adj[u] where seen.insert(v).inserted {
    q.append(v) } }

Grid: 4 neighbours, bounds-check before subscripting. Directed cycle: an onPath set, separate from visited.

cue: “must come before”. In-degree 0 → queue; pop, decrement neighbours. order.count < n ⇒ cycle. [a, b] = “a needs b” = edge b→a.

cue: “all” subsets / permutations / combos / N-Queens. Choose → explore → unchoose; prune invalid branches early.

func bt(_ start: Int) {
  res.append(path)               // subsets
  for i in start..<n {
    path.append(a[i])            // choose
    bt(i + 1)                    // explore
    path.removeLast() } }        // UNCHOOSE

Reuse allowed → bt(i); permutations → a used array, loop from 0.

cue: count ways / min / max / feasible, and the brute force re-solves the same sub-inputs. Recipe: state in one sentence → recurrence → base cases → iteration order → answer cell. Memo (top-down: recursion + cache, only reachable states, deep stack) vs tabulation (bottom-up loop, easy to shrink to one row / two scalars). Same big-O.

The 5 classic shapes

=2mm1D linear: dp[i] = max(dp[i-1], dp[i-2]+x) — stairs, robber

=2mmUnbounded choice: dp[a] = min(dp[a], dp[a-c]+1), a ascending — coin change

=2mm0/1 knapsack: one row, capacity descending ⇒ each item once

=2mmTwo sequences: dp[i][j], table (m+1)×(n+1), compare a[i-1] — LCS, edit distance

=2mmGrid paths: dp[r][c] = dp[r-1][c] + dp[r][c-1], first row/col = 1

var memo: [Int: Int] = [:]
func ways(_ i: Int) -> Int {
  if i <= 1 { return 1 }
  if let v = memo[i] { return v }
  let v = ways(i - 1) + ways(i - 2)
  memo[i] = v; return v }

cue: sort by start, sweep; extend with max(end, iv.end) — a contained interval must not shrink it. Touching ([1,4],[4,5]): decide and say it. Meeting rooms = min-heap of end times, or sorted starts vs sorted ends.

• String has no s[i] — let c = Array(s) once ([Character], O(1) index). s.count is O(n).
• Character ≠ String: "a" as Character; c.asciiValue! (UInt8); c.isLetter, c.isNumber.
• dict[k, default: 0] += 1; plain lookup returns an Optional.
• No heap, no deque: removeFirst() is O(n) → keep a head index.
• Tuples aren’t Hashable → struct P: Hashable { let r, c: Int }.
• Int overflow traps: midpoint lo + (hi-lo)/2; ∞ sentinel amount + 1, not Int.max.
• 2D: Array(repeating: Array(repeating: 0, count: n), count: m).
• a.max() is Optional; stride(from: n-1, through: 0, by: -1); swapAt; sorted(by:) returns a copy.
• Deep recursion crashes (iOS main-thread stack is 1 MB, secondary 512 KB) → explicit stack for degenerate trees / long paths.

Interview traps

• Window with negative numbers — shrinking no longer restores validity; use the prefix-sum map.
• BFS marking visited on dequeue → a node queued many times.
• Greedy that “looks right”: coins [1,3,4], 6 → greedy 4+1+1, DP 3+3.
• Backtracking without the unchoose → paths leak into each other; res.append(path) copies (value type) — good.
• Claiming O(n) and forgetting the O(n) space of the map or the recursion stack.

Remember: sorted → pointers / binary · contiguous → window · seen → hash · levels → BFS · “all” → backtrack · repeated sub-answers → DP · top K → heap.

Likely questions

1. Why is the window O(n) despite a nested while? — each index enters and leaves once.
2. Why seed the prefix map with [0: 1]? — subarrays that start at index 0.
3. Memo or table? — same big-O; memo mirrors the recurrence, table avoids deep recursion and shrinks space.
4. Two-sum sorted vs unsorted? — pointers O(1) space vs hash O(n) keeping original indices.