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.
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.
Searching
Finding a value, or the place where it belongs.
Linear search
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.
Binary search
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- Sorted input only.
O(log n)time. >> 1halves and rounds down.- See the binary search pattern.
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); // → 3Also the index at which to insert x and keep the order.
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. kis 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.
sortchanges the array;toSortedcopies 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.
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); // → trueO(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); // → 9Add 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]; // → 5Build 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]); // → 7Trades 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]); // → 6At each item: extend the run, or start again here.
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.
ncalls deep usesO(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); // → 12586269025Each 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.
Graphs and trees
Visiting things that are joined to each other.
Breadth-first search
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.
Depth-first search
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.
Dynamic programming
Solve the small versions first and reuse their answers.
The four steps
- Say what one answer means: "
dp[i]is …". - Write it using smaller answers.
- Fill in the smallest answers by hand.
- 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); // → 8Each 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); // → 5O(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"); // → 3dp[i][j] is the answer for the first i and j letters.
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 |