DSA CHEAT SHEET

before you code — the input size already told you the answer

contiguous memory — the substrate everything else is built on

// in-place, O(1) space: reverse / rotate / partition
function reverse(a, i = 0, j = a.length - 1) {
  while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
}   // don't inline i++/j-- into the swap — eval order will bite you

// rotate right by k, O(n) time O(1) space — reverse 3 times
function rotate(a, k) {
  k %= a.length;
  reverse(a, 0, a.length - 1);   // whole thing
  reverse(a, 0, k - 1);          // first k back into order
  reverse(a, k, a.length - 1);   // the rest back into order
}

// Kadane — max subarray sum, the "do I restart?" trick
let best = -Infinity, cur = 0;
for (const x of a) { cur = Math.max(x, cur + x); best = Math.max(best, cur); }

• Two Sum easy
• Best Time to Buy and Sell Stock easy
• Maximum Subarray medium
• Product of Array Except Self medium
• Rotate Array medium
• Set Matrix Zeroes medium
• First Missing Positive hard
• Plus One easy
• Longest Common Prefix easy
• Majority Element easy
• Remove Duplicates from Sorted Array easy
• Best Time to Buy and Sell Stock II medium
• Spiral Matrix medium
• Rotate Image medium

turn an O(n²) pair-hunt into one O(n) sweep

// A. opposite ends — sorted array, find a pair
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--;      // too small? grow left. too big? shrink right.
}

// B. same direction — in-place filter (remove all zeroes)
let w = 0;                                  // write pointer
for (let rd = 0; rd < a.length; rd++)      // read pointer
  if (a[rd] !== 0) a[w++] = a[rd];
while (w < a.length) a[w++] = 0;

// C. fast & slow — de-duplicate a sorted array
let k = 1;
for (let i = 1; i < a.length; i++)
  if (a[i] !== a[k - 1]) a[k++] = a[i];
return k;

• Valid Palindrome easy
• Move Zeroes easy
• Two Sum II — Input Array Is Sorted medium
• 3Sum medium
• Container With Most Water medium
• Sort Colors (Dutch flag) medium
• Trapping Rain Water hard
• Remove Element easy
• Squares of a Sorted Array easy
• Merge Strings Alternately easy
• 3Sum Closest medium
• 4Sum medium
• Boats to Save People medium
• Reverse Words in a String medium

contiguous + "longest/shortest/count" this, almost always

// THE template. Change only the two ??? lines.
let l = 0, best = 0;
const state = new Map();

for (let r = 0; r < s.length; r++) {
  add(s[r], state);                        // 1. grow right

  while (windowIsInvalid(state)) {         // 2. ??? shrink until valid again
    remove(s[l], state); l++;
  }

  best = Math.max(best, r - l + 1);        // 3. ??? record (max here, min if shrinking to valid)
}

// longest substring without repeating characters
const last = new Map(); let l = 0, best = 0;
for (let r = 0; r < s.length; r++) {
  const c = s[r];
  if (last.has(c) && last.get(c) >= l) l = last.get(c) + 1;  // jump, don't crawl
  last.set(c, r);
  best = Math.max(best, r - l + 1);
}

• Maximum Average Subarray I easy
• Longest Substring Without Repeating Characters medium
• Longest Repeating Character Replacement medium
• Permutation in String medium
• Minimum Size Subarray Sum medium
• Fruit Into Baskets medium
• Minimum Window Substring hard
• Sliding Window Maximum hard
• Contains Duplicate II easy
• Max Consecutive Ones III medium
• Longest Substring with At Most K Distinct Characters medium
• Count Number of Nice Subarrays medium
• Subarrays with K Different Integers hard
• Substring with Concatenation of All Words hard

pay O(n) once, answer every range query in O(1)

// prefix sums — O(1) range query after O(n) build
const p = [0];
for (const x of a) p.push(p[p.length - 1] + x);
const rangeSum = (i, j) => p[j + 1] - p[i];   // inclusive j

// difference array — O(1) range update, O(n) finalise
const d = new Array(n + 1).fill(0);
for (const [l, r, v] of updates) { d[l] += v; d[r + 1] -= v; }
for (let i = 1; i < n; i++) d[i] += d[i - 1];   // d is now the array

// prefix + hashmap: count subarrays summing to k (works with negatives!)
const seen = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const x of a) {
  sum += x;
  count += seen.get(sum - k) ?? 0;     // how many prefixes make the rest equal k
  seen.set(sum, (seen.get(sum) ?? 0) + 1);
}

• Running Sum of 1d Array easy
• Range Sum Query — Immutable easy
• Subarray Sum Equals K medium
• Contiguous Array medium
• Subarray Sums Divisible by K medium
• Range Sum Query 2D — Immutable medium
• Corporate Flight Bookings medium
• Find Pivot Index easy
• Continuous Subarray Sum medium
• Maximum Size Subarray Sum Equals k medium
• Path Sum III medium
• Number of Submatrices That Sum to Target hard

trade memory for time; the single most common optimisation in interviews

// frequency count — the workhorse
const freq = new Map();
for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);

// group anagrams: canonical key
const groups = new Map();
for (const w of words) {
  const key = [...w].sort().join('');       // or a 26-length count signature
  (groups.get(key) ?? groups.set(key, []).get(key)).push(w);
}

// seen-set: "have I been here before?"
const seen = new Set();
for (const x of a) { if (seen.has(target - x)) return true; seen.add(x); }

• Contains Duplicate easy
• Valid Anagram easy
• Group Anagrams medium
• Top K Frequent Elements medium
• Longest Consecutive Sequence medium
• LRU Cache (map + doubly linked list) medium
• Insert Delete GetRandom O(1) medium
• Ransom Note easy
• Intersection of Two Arrays easy
• Design HashMap easy
• Find All Anagrams in a String medium
• 4Sum II medium
• Time Based Key-Value Store medium
• Sudoku Validator medium

LIFO — "the most recent unresolved thing"

// classic: balanced brackets
const pairs = { ')': '(', ']': '[', '}': '{' }, st = [];
for (const c of s) {
  if (c in pairs) { if (st.pop() !== pairs[c]) return false; }
  else st.push(c);
}
return st.length === 0;

// monotonic decreasing stack: next greater element to the right
const res = new Array(n).fill(-1), st = [];   // st holds INDICES
for (let i = 0; i < n; i++) {
  while (st.length && a[st[st.length - 1]] < a[i])
    res[st.pop()] = a[i];      // a[i] is the first bigger thing to its right
  st.push(i);
}

• Valid Parentheses easy
• Min Stack medium
• Evaluate Reverse Polish Notation medium
• Daily Temperatures medium
• Next Greater Element II medium
• Asteroid Collision medium
• Largest Rectangle in Histogram hard
• Basic Calculator hard
• Baseball Game easy
• Remove All Adjacent Duplicates In String easy
• Simplify Path medium
• Decode String medium
• Car Fleet medium
• Remove K Digits medium
• Maximal Rectangle hard

FIFO — the shape of "level by level"

// !! JS: array.shift() is O(n). For big inputs use a head index.
let head = 0; const q = [start];
while (head < q.length) { const node = q[head++]; /* ... */ }

// monotonic deque: maximum of every window of size k, O(n)
const dq = [], out = [];    // dq holds indices, values DECREASING
for (let i = 0; i < a.length; i++) {
  if (dq.length && dq[0] <= i - k) dq.shift();            // left edge slid past
  while (dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop(); // smaller = useless forever
  dq.push(i);
  if (i >= k - 1) out.push(a[dq[0]]);                      // front is the max
}

• Implement Queue using Stacks easy
• Number of Recent Calls easy
• Design Circular Queue medium
• Shortest Subarray with Sum at Least K hard
• Sliding Window Maximum hard
• First Unique Character in a String easy
• Moving Average from Data Stream easy
• Design Front Middle Back Queue medium
• Jump Game VI medium
• Constrained Subsequence Sum hard

O(1) insert/delete if you already hold the node — that's the whole trade

// 1. reverse — the one you must be able to write blindfolded
let prev = null, cur = head;
while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
return prev;

// 2. dummy head — kills all "what if we delete the first node" bugs
const dummy = { next: head }; let p = dummy;
while (p.next) p.next.val === target ? (p.next = p.next.next) : (p = p.next);
return dummy.next;

// 3. fast & slow — middle, cycle, k-th from end
let slow = head, fast = head;
while (fast && fast.next) {
  slow = slow.next; fast = fast.next.next;
  if (slow === fast) break;      // cycle! (Floyd)
}
// cycle START: reset one pointer to head, advance both by 1, they meet at the entry

• Reverse Linked List easy
• Merge Two Sorted Lists easy
• Linked List Cycle easy
• Remove Nth Node From End of List medium
• Reorder List medium
• Copy List with Random Pointer medium
• Merge k Sorted Lists hard
• Reverse Nodes in k-Group hard
• Middle of the Linked List easy
• Palindrome Linked List easy
• Intersection of Two Linked Lists easy
• Add Two Numbers medium
• Odd Even Linked List medium
• Rotate List medium
• LFU Cache hard

not "find a number" — "find the boundary of a yes/no predicate"

// lower bound — first index where a[i] >= target. Half-open [lo, hi).
let lo = 0, hi = a.length;
while (lo < hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (a[mid] < target) lo = mid + 1;   // mid is too small, discard it
  else hi = mid;                       // mid might be the answer, keep it
}
return lo;   // == a.length means "not found, insert at end"

// binary search on the ANSWER — the real interview version
const feasible = (x) => { /* can we do it with capacity/time/size x? */ };
let lo = minPossible, hi = maxPossible;
while (lo < hi) {
  const mid = lo + ((hi - lo) >> 1);
  feasible(mid) ? (hi = mid) : (lo = mid + 1);
}
return lo;   // smallest feasible x

• Binary Search easy
• First Bad Version easy
• Search in Rotated Sorted Array medium
• Find Minimum in Rotated Sorted Array medium
• Find First and Last Position of Element medium
• Koko Eating Bananas medium
• Capacity To Ship Packages Within D Days medium
• Median of Two Sorted Arrays hard
• Search Insert Position easy
• Sqrt(x) easy
• Valid Perfect Square easy
• Find Peak Element medium
• Kth Smallest Element in a Sorted Matrix medium
• Minimum Speed to Arrive on Time medium
• Split Array Largest Sum hard

you'll rarely implement it — you'll constantly decide whether to call it

// JS default sort is LEXICOGRAPHIC. This bites everyone once.
[10, 9, 1].sort();              // [1, 10, 9]  <- wrong
[10, 9, 1].sort((x, y) => x - y);  // [1, 9, 10] <- correct

// multi-key: by age asc, then name desc
people.sort((a, b) => a.age - b.age || b.name.localeCompare(a.name));

// cyclic sort — numbers 1..n, O(n) time O(1) space, no hashmap
for (let i = 0; i < n; ) {
  const j = a[i] - 1;                       // where a[i] belongs
  if (a[i] !== a[j]) [a[i], a[j]] = [a[j], a[i]];
  else i++;
}
// now any index where a[i] !== i+1 is the missing/duplicate

// quickselect — k-th smallest in O(n) average, no full sort
function select(a, lo, hi, k) {
  const p = partition(a, lo, hi);
  if (p === k) return a[p];
  return p < k ? select(a, p + 1, hi, k) : select(a, lo, p - 1, k);
}

• Merge Sorted Array easy
• Missing Number easy
• Sort an Array (implement merge/quick) medium
• Kth Largest Element in an Array medium
• Find All Duplicates in an Array medium
• Largest Number medium
• Count of Smaller Numbers After Self hard
• Meeting Rooms easy
• Sort Array By Parity easy
• H-Index medium
• Sort Characters By Frequency medium
• Custom Sort String medium
• Wiggle Sort II medium
• Maximum Gap hard

trust the recursive call. it works. stop tracing it in your head.

// shape of every divide & conquer
function solve(problem) {
  if (isBase(problem)) return baseAnswer;      // 1
  const [left, right] = split(problem);         // 2
  return combine(solve(left), solve(right));    // 3
}

// merge sort, the canonical example — T(n) = 2T(n/2) + O(n) = O(n log n)
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

• Fibonacci Number easy
• Pow(x, n) medium
• Sort List (merge sort on a linked list) medium
• Search a 2D Matrix II medium
• Different Ways to Add Parentheses medium
• Reverse Pairs hard
• Kth Symbol in Grammar medium
• Count Good Numbers medium
• Beautiful Array medium
• The Skyline Problem hard

DFS over a decision tree, with an undo button

const res = [], path = [];

function backtrack(start) {
  if (isSolution(path)) { res.push([...path]); return; }   // COPY, don't push the ref

  for (let i = start; i < choices.length; i++) {
    if (!valid(choices[i])) continue;      // <- prune here. this line is the whole game.

    path.push(choices[i]);                 // choose
    backtrack(i + 1);                      // explore  (i+1 = no reuse, i = reuse allowed)
    path.pop();                            // un-choose
  }
}

• Subsets medium
• Combination Sum medium
• Permutations II medium
• Letter Combinations of a Phone Number medium
• Word Search medium
• Palindrome Partitioning medium
• N-Queens hard
• Sudoku Solver hard
• Combinations medium
• Subsets II medium
• Combination Sum II medium
• Generate Parentheses medium
• Restore IP Addresses medium
• Word Break II hard
• Expression Add Operators hard

recursion with a shape

// the four traversals, in one picture
//   preorder  : node, left, right   -> copy / serialise a tree
//   inorder   : left, node, right   -> sorted output on a BST
//   postorder : left, right, node   -> delete / compute from children up
//   level     : BFS with a queue    -> shortest depth, right-side view

// iterative inorder (interviewers ask for this)
const st = []; let cur = root;
while (cur || st.length) {
  while (cur) { st.push(cur); cur = cur.left; }
  cur = st.pop(); visit(cur); cur = cur.right;
}

// level order — the size trick captures each level exactly
const q = root ? [root] : [];
while (q.length) {
  const size = q.length, level = [];
  for (let i = 0; i < size; i++) {
    const n = q.shift();
    level.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  out.push(level);
}

// "return to parent, track globally" — diameter, max path sum, etc.
let best = 0;
function depth(n) {
  if (!n) return 0;
  const L = Math.max(0, depth(n.left)), R = Math.max(0, depth(n.right));
  best = Math.max(best, L + R + n.val);   // path THROUGH n — can't go to parent
  return n.val + Math.max(L, R);          // what the parent can actually use
}

• Maximum Depth of Binary Tree easy
• Invert Binary Tree easy
• Diameter of Binary Tree easy
• Binary Tree Level Order Traversal medium
• Validate Binary Search Tree medium
• Lowest Common Ancestor of a Binary Tree medium
• Construct Tree from Preorder and Inorder medium
• Kth Smallest Element in a BST medium
• Binary Tree Maximum Path Sum hard
• Serialize and Deserialize Binary Tree hard
• Same Tree easy
• Symmetric Tree easy
• Path Sum easy
• Balanced Binary Tree easy
• Subtree of Another Tree easy
• Binary Tree Right Side View medium
• Count Good Nodes in Binary Tree medium
• Flatten Binary Tree to Linked List medium
• House Robber III medium
• Delete Node in a BST medium
• Vertical Order Traversal of a Binary Tree hard

"give me the best one, repeatedly"

// array layout: parent = (i-1)>>1, children = 2i+1, 2i+2
class MinHeap {
  a = [];
  push(v) { this.a.push(v); this.up(this.a.length - 1); }
  pop() {
    const top = this.a[0], last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this.down(0); }
    return top;
  }
  up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p] <= this.a[i]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  down(i) {
    const n = this.a.length;
    for (;;) {
      let m = i, l = 2*i + 1, r = l + 1;
      if (l < n && this.a[l] < this.a[m]) m = l;
      if (r < n && this.a[r] < this.a[m]) m = r;
      if (m === i) break;
      [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
      i = m;
    }
  }
}

• Last Stone Weight easy
• Kth Largest Element in a Stream easy
• K Closest Points to Origin medium
• Task Scheduler medium
• Meeting Rooms II medium
• Find Median from Data Stream hard
• Merge k Sorted Lists hard
• Reorganize String medium
• Minimum Cost to Connect Sticks medium
• Ugly Number II medium
• Top K Frequent Words medium
• IPO hard
• Sliding Window Median hard

a hashmap of hashmaps that knows about prefixes

class Trie {
  root = {};

  insert(word) {
    let n = this.root;
    for (const c of word) n = (n[c] ??= {});
    n.$ = true;                              // '$' marks end-of-word
  }

  // exact = require the '$' marker; prefix = just reach the node
  find(word, exact = true) {
    let n = this.root;
    for (const c of word) { n = n[c]; if (!n) return false; }
    return exact ? !!n.$ : true;
  }
}

• Implement Trie (Prefix Tree) medium
• Design Add and Search Words Data Structure medium
• Replace Words medium
• Maximum XOR of Two Numbers in an Array medium
• Word Search II hard
• Longest Word in Dictionary medium
• Search Suggestions System medium
• Map Sum Pairs medium
• Concatenated Words hard
• Design Search Autocomplete System hard

grids are graphs. trees are graphs. states are graphs.

// adjacency list — the only representation you need (V + E space)
const g = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { g[u].push(v); g[v].push(u); }  // drop the 2nd for directed

// BFS — shortest hops from src
const dist = new Array(n).fill(-1);
const q = [src]; dist[src] = 0;
for (let h = 0; h < q.length; h++) {          // head index, not .shift()
  for (const v of g[q[h]]) if (dist[v] === -1) {
    dist[v] = dist[q[h]] + 1;
    q.push(v);
  }
}

// DFS — recursive, with a visited set (mark on ENTRY, not on pop)
const seen = new Set();
const dfs = (u) => { seen.add(u); for (const v of g[u]) if (!seen.has(v)) dfs(v); };

// grid as a graph — the 4-direction idiom
const DIRS = [[0,1],[1,0],[0,-1],[-1,0]];
for (const [dr, dc] of DIRS) {
  const nr = r + dr, nc = c + dc;
  if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
  /* ... */
}

• Number of Islands medium
• Clone Graph medium
• Rotting Oranges medium
• Pacific Atlantic Water Flow medium
• Surrounded Regions medium
• Word Ladder hard
• Shortest Path in a Grid with Obstacles Elimination hard
• Flood Fill easy
• Find if Path Exists in Graph easy
• Max Area of Island medium
• 01 Matrix medium
• Walls and Gates medium
• Number of Enclaves medium
• Open the Lock medium
• Bus Routes hard

the three named algorithms that actually show up

// -- TOPOLOGICAL SORT (Kahn) — ordering with prerequisites
const indeg = new Array(n).fill(0);
for (const [u, v] of edges) { g[u].push(v); indeg[v]++; }   // u must come before v

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++) {
  order.push(q[h]);
  for (const v of g[q[h]]) if (--indeg[v] === 0) q.push(v);
}
if (order.length < n) return [];   // <- a cycle exists. this check IS "can I finish courses?"

// -- DIJKSTRA — shortest path, non-negative weights
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const pq = new MinHeap();  pq.push([0, src]);   // compare by [0]

while (pq.size) {
  const [d, u] = pq.pop();
  if (d > dist[u]) continue;                    // stale entry — lazy deletion
  for (const [v, w] of g[u]) {
    if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); }
  }
}
// O((V + E) log V).  Negative weights? Bellman-Ford, O(V*E).
// All pairs, small n? Floyd-Warshall, three nested loops, k on the OUTSIDE.

// -- UNION-FIND (DSU) — "are these two in the same group?"
const p = [...Array(n).keys()], rank = new Array(n).fill(0);

const find = (x) => p[x] === x ? x : (p[x] = find(p[x]));   // path compression

const union = (a, b) => {
  a = find(a); b = find(b);
  if (a === b) return false;                    // already joined -> this edge makes a cycle
  if (rank[a] < rank[b]) [a, b] = [b, a];        // union by rank
  p[b] = a;
  if (rank[a] === rank[b]) rank[a]++;
  return true;
};
// near-O(1) amortised (inverse Ackermann). Counts components, detects cycles, builds Kruskal's MST.

• Course Schedule medium
• Course Schedule II medium
• Number of Provinces medium
• Redundant Connection medium
• Network Delay Time medium
• Cheapest Flights Within K Stops medium
• Min Cost to Connect All Points medium
• Alien Dictionary hard
• Swim in Rising Water hard
• Find the Town Judge easy
• Evaluate Division medium
• Accounts Merge medium
• Path with Minimum Effort medium
• Number of Operations to Make Network Connected medium
• Reconstruct Itinerary hard
• Longest Increasing Path in a Matrix hard
• Critical Connections in a Network hard

take the locally best move and never look back — when that's actually allowed

// intervals: the sort key IS the algorithm
intervals.sort((a, b) => a[0] - b[0]);   // by START  -> merging overlaps
intervals.sort((a, b) => a[1] - b[1]);   // by END    -> max non-overlapping / min removals

// merge overlapping intervals
const out = [];
for (const [s, e] of intervals) {
  const last = out[out.length - 1];
  if (last && s <= last[1]) last[1] = Math.max(last[1], e);   // overlap -> extend
  else out.push([s, e]);
}

// jump game — how far can I possibly reach?
let reach = 0;
for (let i = 0; i < a.length; i++) {
  if (i > reach) return false;
  reach = Math.max(reach, i + a[i]);
}

• Merge Intervals medium
• Insert Interval medium
• Non-overlapping Intervals medium
• Jump Game II medium
• Gas Station medium
• Partition Labels medium
• Candy hard
• Assign Cookies easy
• Lemonade Change easy
• Two City Scheduling medium
• Minimum Number of Arrows to Burst Balloons medium
• Queue Reconstruction by Height medium
• Employee Free Time hard
• Meeting Rooms III hard

recursion + memory. that is the entire definition.

// top-down: write the recursion, then add one line of cache
const memo = new Map();
function f(i) {
  if (i <= 1) return base;
  if (memo.has(i)) return memo.get(i);      // <- the entire "DP" part
  const ans = combine(f(i - 1), f(i - 2));
  memo.set(i, ans);
  return ans;
}

// bottom-up + space compression: only the last 2 rows ever mattered
let a = 1, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];

const dp = new Array(W + 1).fill(0);   // dp[c] = best value with capacity c
for (const { w, v } of items)
  for (let c = W; c >= w; c--)         // <- BACKWARD: dp[c-w] is still the PREVIOUS item's row
    dp[c] = Math.max(dp[c], dp[c - w] + v);

// unbounded knapsack (reuse allowed): loop FORWARD instead. one character.

// LCS — the two-sequence skeleton. Edit Distance is the same grid, different transition.
for (let i = 1; i <= n; i++)
  for (let j = 1; j <= m; j++)
    dp[i][j] = s1[i-1] === s2[j-1]
      ? dp[i-1][j-1] + 1                              // match: consume both
      : Math.max(dp[i-1][j], dp[i][j-1]);             // skip one or the other

// LIS in O(n log n) — tails[k] = smallest tail of an increasing subseq of length k+1
const tails = [];
for (const x of a) {
  const i = lowerBound(tails, x);
  i === tails.length ? tails.push(x) : (tails[i] = x);
}
return tails.length;   // tails is NOT the actual subsequence — only its length is real

• Climbing Stairs easy
• House Robber medium
• Coin Change medium
• Longest Increasing Subsequence medium
• Unique Paths medium
• Partition Equal Subset Sum medium
• Longest Common Subsequence medium
• Word Break medium
• Edit Distance medium
• Best Time to Buy and Sell Stock with Cooldown medium
• Burst Balloons hard
• Regular Expression Matching hard
• Min Cost Climbing Stairs easy
• Decode Ways medium
• Maximum Product Subarray medium
• Longest Palindromic Substring medium
• Palindromic Substrings medium
• Unique Paths II medium
• Triangle medium
• Perfect Squares medium
• Target Sum medium
• Interleaving String medium
• Stone Game medium
• Distinct Subsequences hard
• Cherry Pickup hard

a handful of identities. learn them once, recognise them forever.

x & 1               // odd?
x >> 1              // divide by 2 (floor, for non-negatives)
(x >> i) & 1        // read bit i
x | (1 << i)        // set bit i
x & ~(1 << i)       // clear bit i
x ^ (1 << i)        // flip bit i

x & (x - 1)         // * clear the LOWEST set bit  -> popcount loop, power-of-two check
x & (-x)            // * isolate the lowest set bit -> Fenwick trees
x & (x - 1) === 0   // is x a power of two? (x > 0)

// count set bits — runs once per set bit, not 32 times
let c = 0; while (x) { x &= x - 1; c++; }

// iterate every subset of an n-element set
for (let mask = 0; mask < (1 << n); mask++)
  for (let i = 0; i < n; i++) if (mask >> i & 1) use(a[i]);

// iterate every SUBMASK of a mask (bitmask DP)
for (let s = mask; s; s = (s - 1) & mask) { /* s is a submask */ }

• Single Number easy
• Number of 1 Bits easy
• Counting Bits easy
• Reverse Bits easy
• Single Number II medium
• Sum of Two Integers medium
• Subsets (bitmask version) medium
• Power of Two easy
• Hamming Distance easy
• Complement of Base 10 Integer easy
• Bitwise AND of Numbers Range medium
• Maximum Product of Word Lengths medium
• Gray Code medium

small toolkit, occasionally decisive

// gcd / lcm (Euclid)
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const lcm = (a, b) => a / gcd(a, b) * b;      // divide first: avoids overflow

// sieve of Eratosthenes — all primes below n in O(n log log n)
const isP = new Array(n + 1).fill(true); isP[0] = isP[1] = false;
for (let i = 2; i * i <= n; i++)
  if (isP[i]) for (let j = i * i; j <= n; j += i) isP[j] = false;   // start at i2, not 2i

// fast modular exponentiation — a^b mod m in O(log b)
function power(a, b, m) {
  let r = 1n; a = BigInt(a) % BigInt(m);
  while (b > 0) {
    if (b & 1) r = r * a % BigInt(m);
    a = a * a % BigInt(m);
    b >>= 1;
  }
  return r;
}

// primality by trial division — only up to sqrtn, and only 6k±1
if (n < 4) return n > 1;
if (n % 2 === 0 || n % 3 === 0) return false;
for (let i = 5; i * i <= n; i += 6)
  if (n % i === 0 || n % (i + 2) === 0) return false;

• Palindrome Number easy
• Happy Number easy
• Count Primes medium
• Pow(x, n) medium
• Excel Sheet Column Title easy
• Random Pick with Weight medium
• Add Digits easy
• Ugly Number easy
• Multiply Strings medium
• Basic Calculator II medium
• Fraction to Recurring Decimal medium
• Rotate Function medium

rare in interviews, decisive in contests

const t = new Array(n + 1).fill(0);
const add = (i, v) => { for (i++; i <= n; i += i & -i) t[i] += v; };
const sum = (i) => { let s = 0; for (i++; i > 0; i -= i & -i) s += t[i]; return s; };

• Range Sum Query — Mutable medium
• Implement strStr() / KMP easy
• Repeated DNA Sequences medium
• Sum of Subarray Minimums medium
• Count of Range Sum hard
• Find the Shortest Superstring (bitmask DP) hard
• My Calendar I medium
• Number of Longest Increasing Subsequence medium
• Shortest Palindrome hard
• Longest Duplicate Substring hard
• Range Module hard

an order that builds on itself, and what to say out loud in the room