DSA cheat sheet

includes, indexOf, find

O(n) hidden loop

shift, unshift, splice

O(n): items move

slice, spread, concat

O(n): copies

n ≤ 20

2ⁿ is fine (n ≤ 10: n!)

n ≤ 5,000

n² is fine (n ≤ 500: n³)

n ≤ 10⁶

n log n or n

n ≥ 10⁹

log n or O(1)

Tip: About 10⁸ simple steps per second. Sequential loops add, nested loops multiply. Quote the worst case.

• Digit loop (n % 10, Math.floor(n / 10)) is O(log n). Divisors come in pairs, so loop while i * i <= n: O(√n). 0 and 1 are not prime.
• Sieve: all primes up to n in O(n log log n). Euclid gcd and fast power: O(log n).
• Recursion needs a base case, a smaller call and progress. Space is O(depth).

Watch out: Plain fib(30) makes about 2.7 million calls. A memo makes 59.

• Merge: a[i] <= b[j] keeps it stable. Merging two sorted arrays is O(n + m).
• Quickselect finds the k-th item in O(n) average.

Watch out: sort() with no comparator sorts as text ("100" before "9"). Use (a, b) => a - b, never a boolean.

Range sum l..r

pre[r + 1] - pre[l], pre starts with 0

Subarray sums to k

Count earlier prefix sums equal sum - k

Kadane

cur = max(x, cur + x); answer is the best cur

In place (dedupe, zeros)

Read and write pointers, O(1) space

Rotate right by k

Reverse all, then each part; k % n

const seen = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const x of nums) {
  sum += x;
  count += seen.get(sum - k) ?? 0;
  seen.set(sum, (seen.get(sum) ?? 0) + 1);
}

Watch out: Start Kadane at nums[0], not 0, or all-negative input returns 0.

let l = 0, r = nums.length - 1;
while (l < r) {
  const s = nums[l] + nums[r];
  if (s === target) return [l, r];
  if (s < target) l++; else r--;
}

• 3Sum: sort, fix one value, two pointers on the rest. O(n²).
• Container: move the shorter line inwards.

let l = 0;
for (let r = 0; r < n; r++) {
  add(nums[r]);
  while (invalid())
    remove(nums[l++]);
  best = Math.max(best, r - l + 1);
}

• Fixed size k: drop nums[i - k] when i >= k, use the window when i >= k - 1.
• Exactly k = atMost(k) − atMost(k − 1). Count windows by adding r - l + 1.
• Strings are immutable: join once. Longest palindrome: expand around 2n − 1 centres, O(n²).

Watch out: Windows need non-negative values. With negatives use prefix sums and a Map.

const seen = new Map();
for (let i = 0; i < nums.length; i++) {
  const j = seen.get(target - nums[i]);
  if (j !== undefined) return [j, i];
  seen.set(nums[i], i); // then store
}

• Count: freq.set(x, (freq.get(x) ?? 0) + 1). Fixed range: counting array.
• Anagram key: sorted letters or counts.join(","), never join(""). A Map compares arrays by identity.
• Top k frequent: count, then buckets by count. Majority: Boyer–Moore vote.

let lo = 0, hi = nums.length; // [lo, hi)
while (lo < hi) {
  const mid = (lo + hi) >> 1;
  if (nums[mid] < target) lo = mid + 1;
  else hi = mid;
}
return lo; // first nums[i] >= target

• Pick one style. Closed [lo, hi]: lo <= hi, mid ± 1. Half-open: lo < hi, hi = mid.
• First / last of x: lowerBound(x), upperBound(x) - 1.
• Rotated array: one half is sorted. Compare nums[lo] with nums[mid].

1. On the answer: set the range lo..hi of answers.
2. Write works(x), one O(n) pass (Koko: sum of Math.ceil(pile / k) ≤ h).
3. Check false…false, true…true. Find the first true: O(n log range).

// n = nums.length
function walk(start, path) {
  out.push([...path]);  // copy
  for (let i = start; i < n; i++) {
    path.push(nums[i]); // choose
    walk(i + 1, path);  // explore
    path.pop();         // un-choose
  }
}

Duplicates

Sort, skip i > start && nums[i] === nums[i-1]

Permutations

Loop from 0 with a used array

Combination sum

Recurse with i to reuse; prune

Watch out: Pushing path without copying fills out with empty arrays. Forgetting to undo is the most common bug.

let prev = null, cur = head;
while (cur) {
  const next = cur.next; // save first
  cur.next = prev;
  prev = cur;
  cur = next;
}
return prev;

• Insert at head or after a held node is O(1); access index i is O(i). A dummy head removes the delete-head special case.
• Slow 1 step, fast 2: middle and cycle (Floyd). Cycle start: reset one pointer to head, step both by 1.
• n-th from end: send fast n ahead, then move both.

const ans = Array(n).fill(-1);
const st = [];
for (let i = 0; i < n; i++) {
  while (st.length &&
         nums[st.at(-1)] < nums[i])
    ans[st.pop()] = nums[i];
  st.push(i);
}

• Stack = array with push and pop. Brackets: closer must match the top; fail on mismatch, empty, leftovers.
• Queue: use a head index, not shift() (O(n)), or BFS turns O(n²).
• Min stack: store the minimum beside each item.
• Circular array: loop 2n with i % n.

function height(node) {
  if (node === null) return 0; // base case
  return 1 + Math.max(
    height(node.left), height(node.right));
}

BFS level order

Queue; take size first, one level a round

BST

Inorder is sorted. Search, insert, delete O(h)

LCA, any tree

Return null, the target, or the LCA

LCA, BST

Step toward both values until they split

Watch out: Validate a BST with min/max bounds: the rule covers the whole subtree. A skewed BST has h = n.

• Min-heap: children of i are 2i+1, 2i+2. Push, pop O(log n), peek O(1). Top k: heap of size k, O(n log k).
• Greedy needs a proof (exchange argument). Coins 1, 3, 4, amount 6: greedy 4+1+1, best 3+3. Use DP.

intervals.sort((a, b) => a[0] - b[0]);
const out = [intervals[0]];
for (const [s, e] of intervals.slice(1)) {
  const last = out[out.length - 1];
  if (s <= last[1])
    last[1] = Math.max(last[1], e);
  else out.push([s, e]);
}

Tip: Touching ranges merge (<=); back-to-back meetings do not clash (<). Fewest to remove: sort by end.

const q = [start];
const seen = new Set([start]);
for (let h = 0; h < q.length; h++) {
  for (const nb of adj[q[h]]) {
    if (seen.has(nb)) continue;
    seen.add(nb); // mark on enqueue
    q.push(nb);
  }
}

• Adjacency list O(V + E) is the default; matrix is O(V²). Undirected edges go both ways.
• Grid: DIRS plus a bounds check. Build rows with Array.from, not fill(row). Rotate 90°: transpose, reverse rows.

1. Say it: "dp[i] means …". No sentence, no solution.
2. Base cases. Transition: what was the last decision?
3. Order: inputs ready first. Memo is top-down, table bottom-up.

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 - c] + 1 < dp[a])
      dp[a] = dp[a - c] + 1;

1. Clarify. Examples and edge cases aloud.
2. Brute force first, then find the wasted work.
3. Code, then dry run a normal and an edge case.
4. Say time and space unprompted.