Algorithms
Sorting & Searching Algorithms
Sorting & Searching Algorithms Complexity Cheatsheet Algorithm Best Average Worst Space ───────────────────────────────────────────────────── Bubble Sort O(n) O…
Sorting & Searching Algorithms
Complexity Cheatsheet
Algorithm Best Average Worst Space
─────────────────────────────────────────────────────
Bubble Sort O(n) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)
Heap Sort O(n log n) O(n log n) O(n log n) O(1)
Counting Sort O(n+k) O(n+k) O(n+k) O(k)
Radix Sort O(nk) O(nk) O(nk) O(n+k)
─────────────────────────────────────────────────────
Binary Search O(1) O(log n) O(log n) O(1)
Linear Search O(1) O(n) O(n) O(1)
Pick:
- General sort → Quick Sort (in-place) or Merge Sort (stable)
- Nearly sorted → Insertion Sort
- External sort → Merge Sort
- Integer range → Counting Sort / Radix Sort
- Priority queue → Heap SortKey Implementations
// Binary Search — O(log n)
function binarySearch(arr: number[], target: number): number {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Merge Sort — O(n log n), stable
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(a: number[], b: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
result.push(a[i] <= b[j] ? a[i++] : b[j++]);
}
return [...result, ...a.slice(i), ...b.slice(j)];
}
// Quick Sort — O(n log n) avg, in-place
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): void {
if (lo >= hi) return;
const p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
function partition(arr: number[], lo: number, hi: number): number {
const pivot = arr[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
}
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
return i + 1;
}Dynamic Programming Patterns
// DP template: define state, recurrence, base case, order
// 1D DP — Fibonacci / Climbing Stairs
function climbStairs(n: number): number {
if (n <= 2) return n;
let prev = 1, curr = 2;
for (let i = 3; i <= n; i++) [prev, curr] = [curr, prev + curr];
return curr;
}
// Coin Change — min coins to make amount
function coinChange(coins: number[], amount: number): number {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const c of coins) {
if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Longest Common Subsequence (2D DP)
function lcs(s1: string, s2: string): number {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = s1[i-1] === s2[j-1]
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// 0/1 Knapsack
function knapsack(weights: number[], values: number[], cap: number): number {
const n = weights.length;
const dp = Array(cap + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let w = cap; w >= weights[i]; w--) { // iterate backwards
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[cap];
}