← DSA

DSA Patterns

Last reviewed 21 Sept 2026

Interview coding is pattern recognition under time pressure. For each pattern below: the trigger that should make you reach for it, the approach, the complexity, and reference code. Write your own version before reading the code.

The problem-solving script

Say this out loud in the room — communication is scored:

1. Restate the problem and confirm constraints, input ranges, duplicates, empty input, sortedness.
2. Walk one small example by hand.
3. State the brute force and its Big-O — always, even if trivial.
4. Name the pattern and why it applies.
5. Sketch the approach in two or three sentences and get a nod before coding.
6. Code in small pieces, narrating intent.
7. Dry-run on your example, then edge cases: empty, single element, all duplicates, negatives, already sorted, overflow.
8. State the final time and space complexity unprompted.

Hashing

Trigger: “have I seen this before?”, counting frequencies, grouping, complement lookups. Turns an O(n²) scan into O(n).

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

O(n) time, O(n) space. Related: group anagrams (key by sorted string), subarray sum equals k (prefix-sum counts in a map).

Prefix sum

Trigger: “sum of a subarray / range”, “subarray with sum k”, counts over ranges, or a sliding window that breaks because values can be negative. prefix[j] - prefix[i] is the sum of (i, j].

function subarraySumK(nums, k) {
  const count = new Map([[0, 1]]); // prefix sum -> times seen
  let sum = 0, res = 0;
  for (const x of nums) {
    sum += x;
    res += count.get(sum - k) ?? 0; // earlier prefix that leaves exactly k
    count.set(sum, (count.get(sum) ?? 0) + 1);
  }
  return res;
}

O(n) time, O(n) space. Seed the map with 0 → 1 so subarrays starting at index 0 count. Also: zero-sum subarray, product of array except self (prefix and suffix products), range sum query, 2-D prefix sums for submatrix sums.

Two pointers

Trigger: a sorted array, or comparing from both ends; find a pair or triplet, reverse in place, partition, dedupe.

function pairSumSorted(a, target) {
  let l = 0, r = a.length - 1;
  while (l < r) {
    const s = a[l] + a[r];
    if (s === target) return [l, r];
    s < target ? l++ : r--;
  }
  return [];
}

O(n) after an O(n log n) sort. Three-sum: fix one element, two-pointer the rest, skip duplicates.

Cyclic sort / index marking

Trigger: an array of n numbers in the range 1..n (or 0..n) — find the missing, duplicate, or first missing positive in O(1) extra space. Each value has a “home” index.

function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    // keep swapping nums[i] to its home (value v lives at index v - 1)
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

O(n) — every swap places one value permanently. Alternative when you may mutate: flip nums[v - 1] negative to mark v as seen. Also: find all duplicates, set mismatch (repeating and missing), missing number (or XOR / sum formula).

Sliding window

Trigger: longest, shortest, or count of a contiguous subarray or substring meeting a constraint. Expand the right edge; shrink the left while the window is invalid.

function longestUniqueSubstring(s) {
  const last = new Map();
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (last.has(c) && last.get(c) >= start) start = last.get(c) + 1;
    last.set(c, i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}

O(n) time. Also: minimum window substring, max sum subarray of size k, longest with at most k distinct.

Binary search

Trigger: sorted-array lookup, or a monotonic predicate over a numeric range (“smallest capacity such that we finish in D days”).

// leftmost index where pred(x) is true; pred must be false...false, true...true
function lowerBound(lo, hi, pred) {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (pred(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

O(log n), times an O(n) check when searching the answer space. Keep one template; define the predicate carefully; use the shift or Math.floor to avoid mid overflow.

Binary search on the answer

When the question asks for the minimum maximum or maximum minimum of something (capacity, speed, pages, distance) and “can we do it with X?” is monotonic in X, binary-search X and write a greedy O(n) feasibility check.

function minEatingSpeed(piles, h) {
  const canFinish = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h;
  return lowerBound(1, Math.max(...piles), canFinish);
}

O(n log range). Same shape: ship packages within D days, split array largest sum, book allocation, painter’s partition, aggressive cows (maximise the minimum gap — flip the predicate), median of two sorted arrays (search the partition).

Stack

Trigger: matching pairs, “most recent unresolved thing”, or “next greater / smaller element” (a monotonic stack).

function nextGreater(nums) {
  const res = Array(nums.length).fill(-1);
  const st = []; // indices, values decreasing
  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[i] > nums[st[st.length - 1]]) {
      res[st.pop()] = nums[i];
    }
    st.push(i);
  }
  return res;
}

O(n) — each index is pushed and popped once.

Monotonic deque

Trigger: max or min of every window of size k, or DP where you need the best value over a sliding range. A deque of indices whose values stay monotonic; the front is always the answer for the current window.

function maxSlidingWindow(nums, k) {
  const dq = [], res = []; // indices, values decreasing
  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] <= i - k) dq.shift();            // out of window
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // dominated
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}

O(n) amortised (use a real deque or a head index in production; shift is O(n) in JS). The monotonic stack above covers next greater / smaller, largest rectangle in a histogram, daily temperatures, stock span, and trapping rain water.

Fast and slow pointers

Trigger: linked-list cycle detection, finding the middle, reordering.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

O(n) time, O(1) space. The middle is slow when fast reaches the end. Use a dummy head node for insert- or delete-heavy problems.

Linked list in-place reversal

Trigger: reverse the whole list, a sub-range, or every group of k; palindrome check; reorder list. Three pointers — prev, curr, next — and a dummy head when the head can change.

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

O(n) time, O(1) space. Reverse in groups of k: check k nodes exist, reverse them, reconnect the previous group’s tail. Palindrome: find the middle (fast/slow), reverse the second half, compare. Reorder list: middle + reverse + merge alternately.

Trees — BFS and DFS

Trigger: anything hierarchical. Level-order needs a queue; depth, diameter, path sum, and validation are recursive.

function levelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const level = [];
    for (let n = q.length; n > 0; n--) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
}

O(n) time. A binary-search-tree in-order traversal yields sorted order. Know: validate a BST by passing down min and max bounds; lowest common ancestor.

Graphs

Trigger: nodes and edges, or a grid treated as a graph. BFS for shortest path in an unweighted graph; DFS for connectivity and cycles; Kahn’s algorithm or DFS colours for topological sort.

function numIslands(grid) {
  const R = grid.length, C = grid[0].length;
  let count = 0;
  const sink = (r, c) => {
    if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  };
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (grid[r][c] === '1') { count++; sink(r, c); }
  return count;
}

O(V + E).

Topological sort

Trigger: dependencies, prerequisites, build order, “can all tasks finish?”, ordering derived from comparisons (alien dictionary). Only exists for a DAG — if you cannot order every node, there is a cycle.

function courseOrder(n, prereqs) {           // prereqs: [course, needs]
  const adj = Array.from({ length: n }, () => []);
  const indeg = Array(n).fill(0);
  for (const [c, p] of prereqs) { adj[p].push(c); indeg[c]++; }
  const q = [], order = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  for (let h = 0; h < q.length; h++) {
    const u = q[h];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === n ? order : []; // [] means a cycle
}

O(V + E) (Kahn’s algorithm). DFS alternative: post-order, then reverse; three colours detect a cycle. Also: minimum time per job in a DAG (process in topological order), longest path in a DAG.

Union-Find (disjoint set)

Trigger: “are these connected?”, number of components as edges arrive, redundant connection, grouping equivalent items (accounts merge, similar strings), Kruskal’s MST.

class DSU {
  constructor(n) { this.parent = [...Array(n).keys()]; this.size = Array(n).fill(1); }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;                    // already connected → cycle
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    return true;
  }
}

Near O(1) per operation with path compression and union by size. Prefer it over DFS when edges arrive over time or you only need connectivity, not paths.

Trie

Trigger: many prefix queries, autocomplete, “word starts with”, searching many words in a grid at once (word search II), shortest unique prefix, maximum XOR of two numbers (a bit trie).

class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const ch of word) node = node[ch] ??= {};
    node.end = true;
  }
  #walk(s) {
    let node = this.root;
    for (const ch of s) if (!(node = node[ch])) return null;
    return node;
  }
  search(word) { return !!this.#walk(word)?.end; }
  startsWith(prefix) { return this.#walk(prefix) !== null; }
}

O(L) per operation for a word of length L; space is total characters stored. For word search II, build a trie of the words and DFS the grid once, pruning when no child matches.

Heap / priority queue

Trigger: “k largest or smallest”, “kth”, streaming order statistics. JavaScript has no built-in heap — carry a small class or keep a sorted array for tiny k.

// k largest: keep a min-heap of size k; the root is the kth largest.
// Running median: a max-heap for the low half, a min-heap for the high half.

Top-k is O(n log k).

Top-K, K-way merge and two heaps

Three recurring heap shapes — recognise which one before coding:

• Top-K — “k largest / most frequent / closest”: a min-heap of size k (pop when size exceeds k). O(n log k). For a one-off query, quickselect is O(n) average; for frequencies, bucket sort by count is O(n).
• K-way merge — “merge k sorted lists / arrays”, “kth smallest in a sorted matrix”, “smallest range covering k lists”: push the head of each list, pop the smallest, push its successor. O(N log k).
• Two heaps — “running median”, “sliding window median”: a max-heap for the lower half, a min-heap for the upper half; rebalance so sizes differ by at most one. O(log n) per insert.

class MinHeap {
  constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a; a.push(x);
    for (let i = a.length - 1, p; i > 0 && this.cmp(a[i], a[p = (i - 1) >> 1]) < 0; i = p)
      [a[i], a[p]] = [a[p], a[i]];
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ;) {
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
        if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

Carry this class into JavaScript interviews — pass a comparator to get a max-heap or to order [value, listIndex] pairs.

Backtracking

Trigger: generate all subsets, permutations, or combinations; constraint satisfaction.

function subsets(nums) {
  const res = [], path = [];
  const bt = (start) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      bt(i + 1);
      path.pop(); // undo
    }
  };
  bt(0);
  return res;
}

Shape: choose, recurse, un-choose. Permutations track a used array; combination sum allows reuse by recursing on i rather than i + 1. Exponential by nature — that is expected.

Dynamic programming

Trigger: “number of ways”, “min or max cost”, “can we reach”, with overlapping subproblems and choices at each step.

Steps: define the state (what dp[i] means), the recurrence, the base case, the fill order, the answer cell. Then reduce space if only the last few states are needed.

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

O(amount × coins). House robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]), reducible to two variables.

Greedy

Trigger: a locally best choice that never needs undoing — scheduling the most non-overlapping activities, jump game, gas station, minimum platforms, assign cookies, task scheduler. Usually “sort by something, then sweep”.

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;   // stuck before i
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

O(n), or O(n log n) with a sort. Justify it — interviewers ask “why is greedy correct?”. Use an exchange argument: swapping any optimal solution’s choice for the greedy one never makes it worse. If you cannot argue that, it is probably DP (coin change with arbitrary coins is the classic trap).

Intervals

Trigger: overlapping ranges, scheduling, “can attend all”, “rooms needed”. Almost always: sort by start first.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
    else res.push(intervals[i]);
  }
  return res;
}

O(n log n). Minimum meeting rooms: sort starts and ends separately and sweep, or use a min-heap of end times.

Bit manipulation

Trigger: “every element appears twice except one”, O(1)-space tricks, power of two, subsets of a small set (n ≤ 20), toggling flags.

const singleNumber = (nums) => nums.reduce((x, n) => x ^ n, 0); // a ^ a = 0, a ^ 0 = a
const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;
function countBits(n) { let c = 0; while (n) { n &= n - 1; c++; } return c; } // Kernighan

Know: x & (x - 1) clears the lowest set bit, x & -x isolates it, 1 << i builds a mask, and enumerating mask from 0 to (1 << n) - 1 walks every subset. JavaScript bitwise operators work on 32-bit signed integers — use >>> 0 for unsigned, and BigInt beyond 32 bits.

Matrix traversal

Trigger: 2-D grids — spiral order, rotate by 90°, set matrix zeroes, search a sorted matrix, and grid-as-graph problems (islands, rotting oranges, shortest path in a maze).

function spiralOrder(m) {
  const res = [];
  let top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) res.push(m[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) res.push(m[r][right]);
    right--;
    if (top <= bottom) { for (let c = right; c >= left; c--) res.push(m[bottom][c]); bottom--; }
    if (left <= right) { for (let r = bottom; r >= top; r--) res.push(m[r][left]); left++; }
  }
  return res;
}

O(R × C). Rotate 90° clockwise in place: transpose, then reverse each row. Sorted rows and columns: start at the top-right corner and step left or down (O(R + C)). For grid BFS/DFS, keep a dirs = [[1,0],[-1,0],[0,1],[0,-1]] array; multi-source BFS (all rotten oranges in the queue at once) gives distances from the nearest source.

When you do not recognise the problem

Look for structure: sorted implies binary search or two pointers; contiguous implies sliding window; “seen before” implies a hash; a tree or graph implies BFS or DFS; optimal over choices with overlap implies DP; “k of something” implies a heap; dependencies imply topological sort; “connected as edges arrive” implies union-find; many prefixes imply a trie; values in 1..n imply cyclic sort; “minimise the maximum” implies binary search on the answer; range sums with negatives imply prefix sums. Pick the most promising, sketch it in words, get a nod, then code.