TS THE INTERVIEW FIELD GUIDE 01 / ALGORITHMS

Recognize the pattern.
Know the next move.

The minimum to recognize, explain, and implement the common interview patterns. All templates are TypeScript. Open a pattern when you need the details.

22 patterns15 core firstRunnable templatesLinked visualizations

Before you reach for a template

01
Clarify
Input size, duplicates, ordering, mutation, and the exact output.
02
Explain
State a brute-force solution, then what repeated work you can remove.
03
Check
Trace one example. Test empty, singleton, ties, and boundary cases.

START WITH THE CLUE

What is the problem asking?

Clues, not guarantees.

Find a pair or remember a count

Hash maps & sets Two pointers

Work with a contiguous range

Sliding window Prefix sums

Search sorted data or a yes/no boundary

Binary search

Explore connections or dependencies

Breadth-first search Graphs & flood fill Topological sort

Choose the best next item

Heaps & priority queues Greedy algorithms

Explore choices or reuse subproblems

Backtracking Dynamic programming

THE REFERENCE

Patterns to keep in reach

Costs describe the shown template.

22 of 22 patterns · V = vertices, E = edges, h = tree height

Remember earlier work so each lookup replaces another scan.

Know this: Use Set for membership and Map for counts or indices. Decide exactly what each key represents.
Keep true: Before processing index i, the map contains only earlier indices.
Watch for: Look up the complement before inserting the current value, or you can reuse the same index. Check undefined, not truthiness: index 0 is valid.

Time O(n) expectedSpace O(n)

TypeScript

function twoSum(a: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < a.length; i++) {
    const j = seen.get(target - a[i]!);
    if (j !== undefined) return [j, i];
    seen.set(a[i]!, i);
  }
  return [];
}

TRACE ITtwoSum([2, 7, 11, 15], 9) → [0, 1]

SEE IT MOVETwo Sum Group Anagrams

Move the pointer whose current position you can safely rule out.

Know this: For a sorted pair sum: too small → move left forward; too large → move right backward. Be able to explain why the discarded candidates cannot work.
Keep true: If a valid pair remains, both of its indices are inside [left, right].
Watch for: The movement rule depends on the problem. Sorting costs O(n log n) and loses original indices unless you preserve them.

Time O(n) on sorted inputSpace O(1)

TypeScript

// Input is sorted ascending; returns indices in this array.
function sortedPair(a: number[], target: number): number[] {
  let left = 0, right = a.length - 1;
  while (left < right) {
    const sum = a[left]! + a[right]!;
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

TRACE ITsortedPair([1, 3, 4, 6], 7) → [0, 3]

SEE IT MOVEContainer With Most Water Trapping Rain Water

Extend the right edge; shrink the left edge until the window is valid.

Know this: Track just enough to add and remove an item. For longest valid windows, record after repair; for shortest covering windows, record while shrinking a valid window.
Keep true: After the while loop, this example’s window contains no repeated character.
Watch for: Contiguous is not a subsequence. Negative values break the usual sum-based shrinking rule; exact sums with negatives often need prefix sums + a map.

Time O(n) expectedSpace O(n)

TypeScript

function longestUnique(s: string): number {
  const chars = [...s];
  const window = new Set<string>();
  let left = 0, best = 0;
  for (let right = 0; right < chars.length; right++) {
    while (window.has(chars[right]!)) {
      window.delete(chars[left++]!);
    }
    window.add(chars[right]!);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

TRACE ITlongestUnique("abcabcbb") → 3

SEE IT MOVELongest Unique Substring Minimum Window Substring

A range sum is the difference between two prefix sums.

Know this: Build prefix[0] = 0 and prefix[i + 1] = prefix[i] + a[i]. Then sum of [l, r) is prefix[r] − prefix[l]. For target k, count previous prefixes equal to sum − k.
Keep true: The frequency map counts prefixes ending before the current prefix.
Watch for: Seed frequency 0 with 1 to count ranges starting at index 0. Look up before incrementing, especially when k = 0.

Time O(n) expectedSpace O(n)

TypeScript

function countSum(a: number[], k: number): number {
  const freq = new Map<number, number>([[0, 1]]);
  let sum = 0, count = 0;
  for (const x of a) {
    sum += x;
    count += freq.get(sum - k) ?? 0;
    freq.set(sum, (freq.get(sum) ?? 0) + 1);
  }
  return count;
}

TRACE ITcountSum([1, -1, 0], 0) → 3

SEE IT MOVERange Sum Query Subarray Sum Equals K

Keep the answer boundary and discard half the search space each time.

Know this: Learn one boundary template: first index with a[i] ≥ target. For “minimum capacity/time that works,” replace the comparison with a monotone feasibility test.
Keep true: Indices before lo are too small; indices at or after hi meet the target. The boundary stays in [lo, hi].
Watch for: The result can be a.length. Exact search needs an equality check afterward. Prove monotonicity before searching an answer space.

Time O(log n)Space O(1)

TypeScript

function lowerBound(a: number[], target: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

TRACE ITlowerBound([1, 3, 3, 7], 3) → 1

SEE IT MOVESearch Rotated Array Time Based Key-Value Store

Sort endpoints so only the current merged interval needs attention.

Know this: Merge by start time. Select the most non-overlapping intervals by end time. Count simultaneous events with a sweep or a min-heap of end times.
Keep true: The output stays sorted and disjoint; only its last interval can overlap the next input.
Watch for: Agree on closed [a, b] versus half-open [a, b) endpoints. Touching closed intervals merge; half-open meetings can reuse a room at the same time.

Time O(n log n)Space O(n)

TypeScript

type Interval = [number, number];
function mergeIntervals(input: Interval[]): Interval[] {
  const sorted = [...input].sort((a, b) => a[0] - b[0]);
  const out: Interval[] = [];
  for (const [start, end] of sorted) {
    const last = out.at(-1);
    if (!last || start > last[1]) out.push([start, end]);
    else last[1] = Math.max(last[1], end);
  }
  return out;
}

TRACE ITmergeIntervals([[1, 3], [2, 6], [8, 10]]) → [[1, 6], [8, 10]]

SEE IT MOVEMerge Intervals Meeting Rooms II Skyline Sweep

The last unfinished item is the first one you resolve.

Know this: Use an array with push/pop. For matching brackets, push openings and compare each closing bracket with the top.
Keep true: The stack contains exactly the openings that still need a matching close.
Watch for: A closing bracket can arrive with an empty stack. A nonempty stack at the end is also invalid.

Time O(n)Space O(n)

TypeScript

// Input contains only ()[]{} characters.
function validBrackets(s: string): boolean {
  const close = new Map([
    [")", "("], ["]", "["], ["}", "{"],
  ]);
  const stack: string[] = [];
  for (const ch of s) {
    if (!close.has(ch)) stack.push(ch);
    else if (stack.pop() !== close.get(ch)) return false;
  }
  return stack.length === 0;
}

TRACE ITvalidBrackets("([])") → true

SEE IT MOVEValid Parentheses Exclusive Time of Functions

Keep unresolved candidates in order; remove candidates the new item beats.

Know this: Store indices. A stack resolves next-greater queries; a deque keeps window candidates, discarding expired indices from its front and dominated values from its back.
Keep true: This stack holds unresolved indices in non-increasing value order.
Watch for: Choose < versus ≤ based on whether equal values count. Each index enters and leaves once, so the nested while loop is still linear.

Time O(n)Space O(n)

TypeScript

function nextGreater(a: number[]): number[] {
  const answer = Array<number>(a.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < a.length; i++) {
    while (stack.length && a[stack.at(-1)!]! < a[i]!) {
      answer[stack.pop()!] = a[i]!;
    }
    stack.push(i);
  }
  return answer;
}

TRACE ITnextGreater([2, 1, 2, 4, 3]) → [4, 2, 4, -1, -1]

SEE IT MOVESliding Window Maximum

Keep references to the nodes you will need before changing any link.

Know this: Reversal needs prev/current/next. Fast/slow pointers find a middle or cycle in O(n) time and O(1) space. A dummy node simplifies deleting or inserting at the head.
Keep true: prev heads the reversed prefix; current heads the untouched suffix.
Watch for: Save current.next before overwriting it. Compare node identity for cycles, not node values. This reversal assumes an acyclic list.

Time O(n)Space O(1)

TypeScript

type ListNode = { val: number; next: ListNode | null };
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

TRACE IT1 → 2 → 3 becomes 3 → 2 → 1

SEE IT MOVEReverse Linked List Linked List Cycle

Define what one subtree returns, then combine its children’s answers.

Know this: Write the null case first. Preorder acts before children; inorder visits left/node/right; postorder combines child results. BST validation passes ancestor bounds down.
Keep true: Each call returns the correct result for the entire subtree rooted at its argument.
Watch for: Tree height can be n, so recursion can overflow the JS call stack. A graph needs a visited set; a proper tree does not.

Time O(n)Space O(h) call stack

TypeScript

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function maxDepth(node: TreeNode | null): number {
  if (!node) return 0;
  const left = maxDepth(node.left);
  const right = maxDepth(node.right);
  return 1 + Math.max(left, right);
}

TRACE ITmaxDepth(null) → 0; a three-node chain → 3

SEE IT MOVEValidate BST Lowest Common Ancestor

Visit everything one step away before anything two steps away.

Know this: Use a FIFO queue and mark visited when enqueuing. For level-by-level work, freeze the queue’s end index before processing a level.
Keep true: Vertices leave the queue in nondecreasing distance; first discovery gives the shortest unweighted distance.
Watch for: BFS does not solve general weighted shortest paths. Avoid repeated Array.shift(); use a head index.

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

TypeScript

// Vertices are 0..graph.length-1; start is a valid vertex.
function distances(graph: number[][], start: number): number[] {
  const distance = Array<number>(graph.length).fill(-1);
  const queue = [start];
  distance[start] = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head]!;
    for (const v of graph[u]!) {
      if (distance[v] !== -1) continue;
      distance[v] = distance[u]! + 1;
      queue.push(v);
    }
  }
  return distance;
}

TRACE ITdistances([[1, 2], [3], [3], []], 0) → [0, 1, 1, 2]

SEE IT MOVELevel Order Traversal Number of Islands

Explore one connected region, marking nodes so cycles cannot repeat work.

Know this: Represent edges with adjacency lists. For a grid, neighbors are adjacent cells. To count components, launch a traversal from every still-unvisited node.
Keep true: Each discovered vertex is marked before it can be added to the stack again.
Watch for: A single start misses disconnected components. Directed-cycle detection needs active/finished states, not just a single visited flag.

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

TypeScript

// Undirected graph: each edge appears in both directions.
function components(graph: number[][]): number {
  const seen = new Set<number>();
  let count = 0;
  for (let start = 0; start < graph.length; start++) {
    if (seen.has(start)) continue;
    count++;
    seen.add(start);
    const stack = [start];
    while (stack.length) {
      const u = stack.pop()!;
      for (const v of graph[u]!) {
        if (seen.has(v)) continue;
        seen.add(v);
        stack.push(v);
      }
    }
  }
  return count;
}

TRACE ITcomponents([[1], [0], []]) → 2

SEE IT MOVENumber of Islands Clone Graph

Repeatedly take a node with no remaining prerequisites.

Know this: For edge u → v, increment indegree[v]. Queue all zero-indegree nodes, emit each one, and decrement its outgoing neighbors. Fewer than V emitted means a cycle.
Keep true: A queued vertex has no incoming edges from any unprocessed vertex.
Watch for: Use the correct edge direction. Include isolated nodes. If you deduplicate adjacency edges, deduplicate their indegree increments too.

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

TypeScript

function topo(graph: number[][]): number[] | null {
  const degree = Array<number>(graph.length).fill(0);
  for (const edges of graph) {
    for (const v of edges) degree[v] = degree[v]! + 1;
  }
  const queue: number[] = [];
  degree.forEach((d, u) => { if (d === 0) queue.push(u); });
  for (let head = 0; head < queue.length; head++) {
    for (const v of graph[queue[head]!]!) {
      degree[v] = degree[v]! - 1;
      if (degree[v] === 0) queue.push(v);
    }
  }
  return queue.length === graph.length ? queue : null;
}

TRACE ITtopo([[1], [2], []]) → [0, 1, 2]

SEE IT MOVECourse Schedule Alien Dictionary

Give each component a representative and merge representatives.

Know this: find follows parent links; union connects roots. Path compression plus union by size makes operations almost constant amortized time.
Keep true: Two items are connected exactly when find returns the same root.
Watch for: Merge roots, not arbitrary nodes. Union-find does not give paths and does not efficiently handle arbitrary edge deletions.

Time O(α(n)) amortized per operationSpace O(n)

TypeScript

class UnionFind {
  private parent: number[];
  private size: number[];
  constructor(n: number) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.size = Array<number>(n).fill(1);
  }
  find(x: number): number {
    while (x !== this.parent[x]) {
      this.parent[x] = this.parent[this.parent[x]!]!;
      x = this.parent[x]!;
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let x = this.find(a), y = this.find(b);
    if (x === y) return false;
    if (this.size[x]! < this.size[y]!) [x, y] = [y, x];
    this.parent[y] = x;
    this.size[x] = this.size[x]! + this.size[y]!;
    return true;
  }
}

TRACE ITunion(0, 1); union(1, 2); find(0) === find(2)

SEE IT MOVEAccounts Merge

Share the common prefixes of words in a tree of characters.

Know this: Each node maps a character to a child. A terminal flag distinguishes a complete word from a prefix. Traversing L characters takes O(L) expected time.
Keep true: The path from the root spells the prefix represented by the current node.
Watch for: A found path is not necessarily a full word. Autocomplete also costs time proportional to the results you traverse and return.

Time O(L) expected per insert/lookupSpace O(total inserted characters)

TypeScript

class Trie {
  private children = new Map<string, Trie>();
  private terminal = false;
  insert(word: string): void {
    let node: Trie = this;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new Trie());
      node = node.children.get(ch)!;
    }
    node.terminal = true;
  }
  has(word: string): boolean {
    let node: Trie = this;
    for (const ch of word) {
      const next = node.children.get(ch);
      if (!next) return false;
      node = next;
    }
    return node.terminal;
  }
}

TRACE ITinsert("cat"); has("cat") → true; has("ca") → false

SEE IT MOVETrie Autocomplete

Keep the next highest-priority item at the root without sorting everything.

Know this: A binary heap has O(1) peek and O(log n) push/pop. For kth largest, keep a min-heap of size k: its root is the smallest retained winner.
Keep true: After each item, the heap holds the largest min(k, items seen) values.
Watch for: A heap’s array is not fully sorted. Define the comparator direction and tie-breaks. Confirm whether the interview environment supplies a priority queue.

Time O(n log(k + 1))Space O(k)

TypeScript

Uses the Heap helper ↓. Copy includes it.

function kthLargest(a: number[], k: number): number {
  if (!Number.isInteger(k) || k < 1 || k > a.length) {
    throw new RangeError("k must be between 1 and a.length");
  }
  const heap = new Heap<number>((a, b) => a < b);
  for (const x of a) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  return heap.peek()!;
}

TRACE ITkthLargest([3, 2, 1, 5, 6, 4], 2) → 5

SEE IT MOVEKth Largest Merge k Sorted Lists Median from Data Stream

Choose, explore, undo; abandon a branch as soon as it cannot work.

Know this: Define the partial answer, available choices, and stopping rule. Use a start index for combinations and a used set/array for permutations. Copy each completed answer.
Keep true: On returning from a recursive call, the shared path is restored to its previous contents.
Watch for: Pushing path itself aliases every answer. Duplicate inputs need a deliberate skip rule. Exponential output means exponential work is unavoidable.

Time O(n · 2ⁿ) for all subsetsSpace O(n) auxiliary; O(n · 2ⁿ) output

TypeScript

// Input values are distinct.
function subsets(a: number[]): number[][] {
  const out: number[][] = [], path: number[] = [];
  function visit(start: number): void {
    out.push([...path]);
    for (let i = start; i < a.length; i++) {
      path.push(a[i]!);
      visit(i + 1);
      path.pop();
    }
  }
  visit(0);
  return out;
}

TRACE ITsubsets([1, 2]) → [[], [1], [1, 2], [2]]

SEE IT MOVEGenerate Parentheses

Name each subproblem precisely and compute its answer once.

Know this: Write state → transition → base cases → evaluation order → final answer. Memoize all state dimensions, or fill a table in dependency order. Time = states × work per state.
Keep true: When dp[sum] is computed, every smaller amount it depends on already has its best answer.
Watch for: Greedy coin choice can fail: [1, 3, 4], amount 6 needs 3 + 3. Zero often means a valid answer, so use Infinity for unreachable minimum-cost states.

Time O(amount · coins.length)Space O(amount)

TypeScript

// Positive integer coins; nonnegative integer amount.
function coinChange(coins: number[], amount: number): number {
  const dp = Array<number>(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let sum = 1; sum <= amount; sum++) {
    for (const coin of coins) {
      if (coin <= sum) {
        dp[sum] = Math.min(dp[sum]!, dp[sum - coin]! + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]!;
}

TRACE ITcoinChange([1, 3, 4], 6) → 2

SEE IT MOVEClimbing Stairs Coin Change Edit Distance

Make a choice you can show never makes the remaining solution worse.

Know this: Explain an exchange argument: an optimal solution can replace its first choice with yours without losing quality. For non-overlapping meetings, choose the earliest finish.
Keep true: After choosing each meeting, the selected set leaves as much remaining time as possible among equally large feasible selections.
Watch for: “Seems best now” is not a proof. Earliest start and shortest duration are not valid substitutes for earliest finish in interval scheduling.

Time O(n log n)Space O(n) for the sorted copy

TypeScript

// Half-open intervals [start, end), with start < end.
function maxMeetings(input: [number, number][]): number {
  const sorted = [...input].sort((a, b) => a[1] - b[1]);
  let end = -Infinity, count = 0;
  for (const [start, finish] of sorted) {
    if (start < end) continue;
    count++;
    end = finish;
  }
  return count;
}

TRACE ITmaxMeetings([[1, 3], [2, 4], [3, 5]]) → 2

SEE IT MOVENon-overlapping Intervals Task Scheduler

Dijkstra expands the unsettled vertex with the smallest known distance.

Know this: Relax each edge: if distance[u] + weight improves distance[v], save it and enqueue it. Use BFS for equal weights; Dijkstra requires nonnegative weights.
Keep true: A non-stale minimum-distance entry popped from the heap has its final shortest distance.
Watch for: Skip stale heap entries after an improvement. Negative edges require another algorithm, such as Bellman–Ford; unreachable vertices stay Infinity.

Time O(V + E log(E + 1)) with lazy heap entriesSpace O(V + E) auxiliary

TypeScript

Uses the Heap helper ↓. Copy includes it.

// Edge = [destination, nonnegative weight]; start is valid.
function dijkstra(graph: [number, number][][], start: number): number[] {
  const dist = Array<number>(graph.length).fill(Infinity);
  const heap = new Heap<[number, number]>((a, b) => a[0] < b[0]);
  dist[start] = 0;
  heap.push([0, start]);
  while (heap.size) {
    const [cost, u] = heap.pop()!;
    if (cost !== dist[u]) continue;
    for (const [v, weight] of graph[u]!) {
      const next = cost + weight;
      if (next >= dist[v]!) continue;
      dist[v] = next;
      heap.push([next, v]);
    }
  }
  return dist;
}

TRACE ITdijkstra([[[1, 4], [2, 1]], [], [[1, 2]]], 0) → [0, 3, 1]

Solve smaller versions, then combine their answers.

Know this: Merge sort splits in half and merges sorted halves. Its log n levels each do O(n) work. Know quicksort’s expected O(n log n), worst O(n²), and quickselect’s expected O(n).
Keep true: Before merging, both halves are sorted; the output prefix contains the smallest items consumed so far.
Watch for: Account for the combine work and allocation. This allocating merge sort uses O(n) peak auxiliary space; it is not in-place.

Time O(n log n)Space O(n) peak auxiliary

TypeScript

function mergeSort(a: number[]): number[] {
  if (a.length <= 1) return [...a];
  const mid = Math.floor(a.length / 2);
  const left = mergeSort(a.slice(0, mid));
  const right = mergeSort(a.slice(mid));
  const out: number[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i]! <= right[j]!) out.push(left[i++]!);
    else out.push(right[j++]!);
  }
  while (i < left.length) out.push(left[i++]!);
  while (j < right.length) out.push(right[j++]!);
  return out;
}

TRACE ITmergeSort([4, 1, 3, 2]) → [1, 2, 3, 4]

Use an algebraic property that removes unnecessary enumeration.

Know this: x ^ x = 0 and x ^ 0 = x; n & (n − 1) clears the lowest set bit. For greatest common divisor, repeatedly replace (a, b) with (b, a % b).
Keep true: The XOR accumulator equals the XOR of all values processed; equal pairs cancel.
Watch for: Number bitwise operators coerce to 32-bit integers. Use BigInt for wider integer bit operations, and never mix bigint and number operands.

Time O(n) for singleNumberSpace O(1)

TypeScript

// Signed 32-bit integers; every value appears twice except one.
function singleNumber(a: number[]): number {
  let result = 0;
  for (const x of a) result ^= x;
  return result;
}

// Nonnegative safe integers.
function gcd(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

TRACE ITsingleNumber([4, 1, 2, 1, 2]) → 4

LANGUAGE CHECK

TypeScript details worth remembering

Numbers need a comparator

[...a].sort((x, y) => x - y)

Default sort compares strings; sort mutates its array. Copy if the input must stay unchanged.

Use a queue head

const item = queue[head++];

Keep push for enqueue. Repeated shift can move every remaining element. A head index retains consumed slots, so this queue uses O(total enqueued) storage.

Zero is a value

count.set(x, (count.get(x) ?? 0) + 1);

Check map.has(key) or value !== undefined. A stored index or count of 0 is not missing. Map and Set compare objects by identity.

Each matrix row needs its own array

Array.from({length: rows}, () => Array<number>(cols).fill(0))

Using fill with a single inner array makes every row share the same object.

Know your integer range

Number.MAX_SAFE_INTEGER // 2 ** 53 - 1

Use bigint if exact integer results can exceed this range. Number bitwise operations use 32-bit values. BigInt arithmetic has a cost that grows with its bit length.

Be precise about strings and !

const characters = [...text];

This iterates Unicode code points; text[i] uses UTF-16 code units. Neither handles every visible grapheme. In templates, ! asserts an index already proved valid; it adds no runtime check.

Complexity shorthand assumes constant-cost numeric operations and expected O(1) hash lookups. Include sorting, copied arrays, the recursion stack, and returned output when explaining your costs.

Pass (a, b) => a < b for a min-heap or (a, b) => a > b for a max-heap. Array indices: parent ⌊(i − 1) / 2⌋, children 2i + 1 and 2i + 2.

TypeScript · generic helper

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (a: T, b: T) => boolean) {}
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }

  push(value: T): void {
    const a = this.a;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (!this.before(a[i]!, a[p]!)) break;
      [a[i], a[p]] = [a[p]!, a[i]!];
      i = p;
    }
  }

  pop(): T | undefined {
    const a = this.a;
    if (!a.length) return undefined;
    const root = a[0]!;
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (2 * i + 1 < a.length) {
        let child = 2 * i + 1;
        const right = child + 1;
        if (right < a.length && this.before(a[right]!, a[child]!)) {
          child = right;
        }
        if (!this.before(a[child]!, a[i]!)) break;
        [a[i], a[child]] = [a[child]!, a[i]!];
        i = child;
      }
    }
    return root;
  }
}

Recognize the pattern.Know the next move.

Before you reach for a template

What is the problem asking?

Patterns to keep in reach

01 Hash maps & setsCoreDuplicates, counts, grouping, or “have I seen the complement?” −

02 Two pointersCoreA sorted pair, a palindrome, or an in-place read/write pass. +

03 Sliding windowCoreA longest/shortest contiguous range with a repairable constraint. +

04 Prefix sumsCoreRepeated range totals, or counting contiguous ranges with a target sum. +

05 Binary searchCoreSorted data, or a feasibility test that changes from false to true once. +

06 Sorting & intervalsCoreOverlapping ranges, schedules, merging, or conflicting bookings. +

07 StacksCoreNesting, matching delimiters, undo, or “finish the most recent thing.” +

08 Monotonic stacks & dequesNextNext greater/smaller item, warmer day, or maximum in every window. +

09 Linked listsCoreReverse links, detect a cycle, find the middle, or splice nodes. +

10 Trees & recursive DFSCoreSubtree height, path information, ancestry, or validating a tree. +

11 Breadth-first searchCoreFewest unweighted steps, nearest target, or tree levels. +

12 Graphs & flood fillCoreReachability, connected components, islands, or copying a network. +

13 Topological sortNextPrerequisites, dependency order, or detecting a directed cycle. +

14 Union-findNextRepeatedly joining groups, undirected connectivity, or redundant edges. +

15 TriesNextMany prefix queries, autocomplete, or dictionary-guided search. +

16 Heaps & priority queuesCoreRepeated best item, top-k, merging sorted streams, or scheduling. +

17 BacktrackingCoreGenerate all subsets, combinations, permutations, or valid arrangements. +

18 Dynamic programmingCoreCount ways or optimize choices that repeatedly reach the same subproblem. +

19 Greedy algorithmsCoreAn optimization where one local choice can be proved safe. +

20 Weighted shortest pathsNextCheapest route through a graph whose edges have different costs. +

21 Divide & conquerNextA problem splits into independent smaller pieces with a useful combine step. +

22 Bits & basic mathNextPair cancellation, compact subsets, parity, divisibility, or cycles. +

TypeScript details worth remembering

Numbers need a comparator

Use a queue head

Zero is a value

Each matrix row needs its own array

Know your integer range

Be precise about strings and !

KEEP ONE IMPLEMENTATION HANDYReusable binary heap+

Recognize the pattern.
Know the next move.