Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

DSA Algorithms Cheat Sheet

8 groups · 30 topics · Updated

The code is JavaScript, and // → shows the result of that line. n is the size of the input.

1

Complexity

How the work grows as the input grows.

Big O at a glance

Big O Name Example
O(1) constant read list[i]
O(log n) logarithmic binary search
O(n) linear one loop
O(n log n) linearithmic merge sort
O(n²) quadratic a loop in a loop
O(2ⁿ) exponential every subset
O(n!) factorial every ordering

Fastest at the top. More in Big O notation explained.

Spot it in code

Shape of the code Cost
One loop over the input O(n)
Two nested loops O(n²)
Halve the range each step O(log n)
A loop with a halving inside O(n log n)
Sort, then one loop O(n log n)
Two calls per call, n deep O(2ⁿ)
Map or Set lookup O(1) on average

What fits the input size

n up to Aim for
20 O(2ⁿ)
500 O(n³)
5,000 O(n²)
1,000,000 O(n log n)
100,000,000 O(n)
larger O(log n) or O(1)

A rough guide for about one second of work.

2

Searching

Finding a value, or the place where it belongs.

function indexOfValue(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;
  }
  return -1;
}
indexOfValue([4, 9, 2], 2); // → 2
  • Works on any order.
  • O(n) time, O(1) space.
function findSorted(list, target) {
  let low = 0;
  let high = list.length - 1;
  while (low <= high) {
    const mid = (low + high) >> 1;
    if (list[mid] === target) return mid;
    if (list[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
findSorted([1, 3, 5, 8], 5); // → 2

First position at least x

function firstAtLeast(list, x) {
  let low = 0;
  let high = list.length;
  while (low < high) {
    const mid = (low + high) >> 1;
    if (list[mid] < x) low = mid + 1;
    else high = mid;
  }
  return low;
}
firstAtLeast([1, 3, 3, 7], 3); // → 1
firstAtLeast([1, 3, 3, 7], 4); // → 3

Also the index at which to insert x and keep the order.

3

Sorting

Putting items in order, and what each way costs.

Compare the sorts

Sort Time Space Stable
Insertion O(n²) O(1) yes
Merge O(n log n) O(n) yes
Quick O(n log n) O(log n) no
Heap O(n log n) O(1) no
Counting O(n + k) O(k) yes
  • Stable: equal items keep their order.
  • Quick sort is O(n²) at worst.
  • k is the largest value.

Built-in sort

const up = (a, b) => a - b;
const down = (a, b) => b - a;
[10, 9, 1].sort();     // → [1, 10, 9]
[10, 9, 1].sort(up);   // → [1, 9, 10]
[10, 9, 1].sort(down); // → [10, 9, 1]
["b", "a"].sort();     // → ["a", "b"]
[3, 1].toSorted(up);   // → [1, 3]
  • With no function, items are compared as text.
  • sort changes the array; toSorted copies it.

Insertion sort

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const value = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
  return a;
}
insertionSort([3, 1, 2]); // → [1, 2, 3]

Good for small or nearly sorted input.

Merge sort

function mergeSort(a) {
  if (a.length < 2) return a;
  const mid = a.length >> 1;
  const l = mergeSort(a.slice(0, mid));
  const r = mergeSort(a.slice(mid));
  const out = [];
  let i = 0;
  let j = 0;
  while (i < l.length && j < r.length) {
    out.push(l[i] <= r[j] ? l[i++] : r[j++]);
  }
  out.push(...l.slice(i), ...r.slice(j));
  return out;
}
mergeSort([5, 2, 9, 1]); // → [1, 2, 5, 9]

Split in half, sort each half, merge the two.

Quick sort

function quickSort(
  a, lo = 0, hi = a.length - 1,
) {
  if (lo >= hi) return a;
  const pivot = a[hi];
  let p = lo;
  for (let i = lo; i < hi; i++) {
    if (a[i] < pivot) {
      [a[i], a[p]] = [a[p], a[i]];
      p++;
    }
  }
  [a[p], a[hi]] = [a[hi], a[p]];
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
  return a;
}
quickSort([5, 2, 9, 1]); // → [1, 2, 5, 9]

Smaller items go left of the pivot, then each side is sorted.

Counting sort

function countingSort(a, max) {
  const count = new Array(max + 1).fill(0);
  for (const value of a) count[value]++;
  const out = [];
  count.forEach((times, value) => {
    out.push(...Array(times).fill(value));
  });
  return out;
}
countingSort([3, 0, 1], 3); // → [0, 1, 3]

Only for whole numbers from 0 to max.

4

Array techniques

Ways to finish in one pass instead of a loop inside a loop.

Two pointers

// sorted input: any pair with this sum?
function hasPairSum(list, target) {
  let left = 0;
  let right = list.length - 1;
  while (left < right) {
    const sum = list[left] + list[right];
    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }
  return false;
}
hasPairSum([1, 3, 4, 8], 7); // → true

O(n) time. See two pointers.

Sliding window

// largest sum of k items in a row
function bestWindowSum(list, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += list[i];
  let best = sum;
  for (let i = k; i < list.length; i++) {
    sum += list[i] - list[i - k];
    best = Math.max(best, sum);
  }
  return best;
}
bestWindowSum([2, 1, 5, 1, 3], 3); // → 9

Add the item that enters, take away the one that leaves. See sliding window.

Prefix sums

function buildPrefix(list) {
  const prefix = [0];
  for (const value of list) {
    prefix.push(prefix.at(-1) + value);
  }
  return prefix;
}
const prefix = buildPrefix([3, 1, 4, 1]);
prefix;                // → [0, 3, 4, 8, 9]
// sum of items 1 to 2
prefix[3] - prefix[1]; // → 5

Build once in O(n); every range sum is then O(1). See prefix sums.

Hash lookup

// first value seen twice
function firstDuplicate(list) {
  const seen = new Set();
  for (const value of list) {
    if (seen.has(value)) return value;
    seen.add(value);
  }
  return null;
}
firstDuplicate([4, 7, 1, 7, 4]); // → 7

Trades O(n) space for O(1) checks. See hashing.

Kadane's algorithm

// largest sum of any run of items
function maxSubarraySum(list) {
  let current = list[0];
  let best = list[0];
  for (let i = 1; i < list.length; i++) {
    const x = list[i];
    current = Math.max(x, current + x);
    best = Math.max(best, current);
  }
  return best;
}
maxSubarraySum([-2, 1, 4, -1, 2]); // → 6

At each item: extend the run, or start again here.

5

Recursion and backtracking

A function that solves a problem by calling itself on a smaller one.

Recursion

function factorial(n) {
  if (n <= 1) return 1;        // base case
  return n * factorial(n - 1); // smaller
}
factorial(5); // → 120
  • Always have a base case.
  • Each call must move towards it.
  • n calls deep uses O(n) memory.

Memoisation

function fib(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value =
    fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}
fib(50); // → 12586269025

Each answer is worked out once: O(2ⁿ) becomes O(n).

Backtracking

// every subset of the list
function subsets(list) {
  const n = list.length;
  const out = [];
  const pick = [];
  function walk(start) {
    out.push([...pick]);
    for (let i = start; i < n; i++) {
      pick.push(list[i]); // choose
      walk(i + 1);        // explore
      pick.pop();         // undo
    }
  }
  walk(0);
  return out;
}
subsets([1, 2]); // → [[], [1], [1, 2], [2]]

Choose, explore, undo. O(2ⁿ) subsets.

6

Graphs and trees

Visiting things that are joined to each other.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      if (seen.has(next)) continue;
      seen.add(next);
      queue.push(next);
    }
  }
  return order;
}
const graph = {
  a: ["b", "c"], b: ["d"], c: ["d"], d: [],
};
bfs(graph, "a"); // → ["a", "b", "c", "d"]
  • Nearest first, so it finds the fewest steps.
  • Uses a queue. O(V + E) time.
  • shift() is slow on a huge queue; keep an index.
function dfs(graph, node, seen = new Set()) {
  seen.add(node);
  for (const next of graph[node]) {
    if (seen.has(next)) continue;
    dfs(graph, next, seen);
  }
  return [...seen];
}
const graph = {
  a: ["b", "c"], b: ["d"], c: ["d"], d: [],
};
dfs(graph, "a"); // → ["a", "b", "d", "c"]
  • Goes as deep as it can, then steps back.
  • Uses recursion or a stack. O(V + E) time.

Tree traversals

function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.value);
  inorder(node.right, out);
  return out;
}
const tree = {
  value: 2,
  left: { value: 1 },
  right: { value: 3 },
};
inorder(tree); // → [1, 2, 3]
Order Visits Used for
Preorder node, left, right copying a tree
Inorder left, node, right sorted order
Postorder left, right, node deleting, sizes
Level order row by row nearest first

Which graph algorithm

Need Use
Fewest steps, no weights BFS
Reach everything, find a cycle DFS
Cheapest path, no negative weights Dijkstra
Cheapest path, negative weights Bellman-Ford
Tasks in dependency order Topological sort
Cheapest way to join every node Kruskal or Prim

V is the number of nodes, E the number of links.

7

Dynamic programming

Solve the small versions first and reuse their answers.

The four steps

  1. Say what one answer means: "dp[i] is …".
  2. Write it using smaller answers.
  3. Fill in the smallest answers by hand.
  4. Work upwards so each answer is ready when needed.

One row of answers

// ways to climb n stairs, 1 or 2 at a time
function climbStairs(n) {
  let previous = 1;
  let current = 1;
  for (let i = 2; i <= n; i++) {
    [previous, current] =
      [current, previous + current];
  }
  return current;
}
climbStairs(5); // → 8

Each answer needs only the two before it, so no array.

Fewest coins

// dp[t]: fewest coins that add up to t
function coinChange(coins, amount) {
  const size = amount + 1;
  const dp = Array(size).fill(Infinity);
  dp[0] = 0;
  for (let t = 1; t <= amount; t++) {
    for (const coin of coins) {
      if (coin > t) continue;
      const count = dp[t - coin] + 1;
      if (count < dp[t]) dp[t] = count;
    }
  }
  const best = dp[amount];
  return best === Infinity ? -1 : best;
}
coinChange([1, 5, 10], 18); // → 5

O(amount × coins) time. Returns -1 when no mix works.

A grid of answers

// longest common subsequence
function lcsLength(a, b) {
  const dp = Array.from(
    { length: a.length + 1 },
    () => Array(b.length + 1).fill(0),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(
          dp[i - 1][j], dp[i][j - 1],
        );
      }
    }
  }
  return dp[a.length][b.length];
}
lcsLength("abcde", "ace"); // → 3

dp[i][j] is the answer for the first i and j letters.

8

Choosing an algorithm

Clues in a problem that point to a technique.

From clue to technique

Clue Try
Sorted input Binary search
Smallest value that works Search the answer
Rises to a peak, then falls Peak finding
Grid with sorted rows Matrix search
Sorted, then rotated Rotated arrays
A pair or triple with a sum Two pointers
"Subarray" or "substring" Sliding window
Many range sums Prefix sums
Seen before, count, group Hashing
Brackets, next greater Stack
Linked list, cycle, middle List pointers
Fewest steps BFS
Every combination or order Backtracking
Count the ways, best total Dynamic programming
Best choice now, never undone Greedy
Top k, smallest so far Heap

Common mistakes

Mistake Fix
Binary search on unsorted input Sort first, or use a Set
Mixing low < high and low <= high Learn one template and keep to it
Recursion with no base case Return early for the smallest input
Graph search with no seen set Mark a node when you queue it
.sort() on numbers Pass (a, b) => a - b
A loop in a loop for lookups Remember values in a Map