Algorithm Cheat Sheet

Essential algorithms and data structures

Master the Most Important Algorithms

Comprehensive collection of must-know algorithms and data structures with clear explanations, complexity analysis, and production-ready code examples.

106

Total Algorithms

Arrays

Essential array algorithms and techniques

Binary Search

Efficiently search for an element in a sorted array using divide and conquer.

Easy

Divide and Conquer

Must-Know

Time: O(log n)

Space: O(1)

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1; // Element not found
}

// Example usage:
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // Output: 3
console.log(binarySearch(sortedArray, 6)); // Output: -1

How it works:

Binary search works by repeatedly dividing the search interval in half. If the target value is less than the middle element, search the left half; otherwise, search the right half.

Two Sum

Find two numbers in an array that add up to a target sum.

Easy

Hash Table

Array

Must-Know

Time: O(n)

Space: O(n)

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    
    map.set(nums[i], i);
  }
  
  return []; // No solution found
}

// Example usage:
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // Output: [0, 1]

How it works:

Use a hash map to store each number and its index. For each number, check if its complement (target - current number) exists in the map.

Maximum Subarray Sum (Kadane's Algorithm)

Find the contiguous subarray with the largest sum.

Medium

Dynamic Programming

Array

Must-Know

Time: O(n)

Space: O(1)

function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    // Either extend the existing subarray or start a new one
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

// Example usage:
const array = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(array)); // Output: 6 ([4, -1, 2, 1])

How it works:

At each position, decide whether to extend the current subarray or start a new one. Keep track of the maximum sum seen so far.

Two Pointers Technique

Use two pointers to solve array problems efficiently.

Easy

Array

Two Pointers

Technique

Time: O(n)

Space: O(1)

function twoPointersPairSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

// Example:
console.log(twoPointersPairSum([1,2,3,4,6], 6)); // Output: [1,3]

How it works:

Move two pointers inward (or forward together) to find pairs efficiently. Useful for sorted arrays.

Prefix Sum

Precompute prefix sums to answer range sum queries quickly.

Easy

Array

Prefix Sum

Range Query

Time: O(n) preprocessing, O(1) per query

Space: O(n)

function prefixSum(arr: number[]): number[] {
  const prefix: number[] = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[prefix.length - 1] + arr[i]);
  }
  return prefix;
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const prefix = prefixSum(arr);
console.log(prefix[5] - prefix[2]); // Range sum [2..4] = 12

How it works:

Store cumulative sums. Range sum [l, r] = prefix[r+1] - prefix[l].

Dutch National Flag Algorithm

Sort an array of 0s, 1s, and 2s in linear time.

Medium

Array

Sorting

Partitioning

Time: O(n)

Space: O(1)

function dutchNationalFlag(nums: number[]): number[] {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

// Example:
console.log(dutchNationalFlag([2,0,2,1,1,0])); // Output: [0,0,1,1,2,2]

How it works:

Partition array into three regions (0s, 1s, 2s) using three pointers.

Difference Array

Perform range updates efficiently in O(1).

Medium

Array

Range Updates

Prefix Sum

Time: O(1) per update, O(n) to finalize

Space: O(n)

function applyDifferenceArray(n: number, updates: [number, number, number][]): number[] {
  const diff = new Array(n + 1).fill(0);
  for (const [l, r, val] of updates) {
    diff[l] += val;
    if (r + 1 < n) diff[r + 1] -= val;
  }
  const result = new Array(n).fill(0);
  result[0] = diff[0];
  for (let i = 1; i < n; i++) {
    result[i] = result[i-1] + diff[i];
  }
  return result;
}

// Example:
console.log(applyDifferenceArray(5, [[1,3,2],[2,4,3]])); // [0,2,5,5,3]

How it works:

Use a difference array to mark range updates, then prefix sum to finalize values.

Reservoir Sampling

Randomly select one element from a stream of unknown length.

Hard

Array

Randomized

Sampling

Time: O(n)

Space: O(1)

function reservoirSampling(stream: number[]): number {
  let result = stream[0];
  for (let i = 1; i < stream.length; i++) {
    if (Math.floor(Math.random() * (i + 1)) === 0) {
      result = stream[i];
    }
  }
  return result;
}

// Example:
console.log(reservoirSampling([10,20,30,40,50]));

How it works:

Keeps each element with equal probability 1/n without knowing n in advance.

Mo’s Algorithm

Answer offline range queries efficiently using sqrt decomposition.

Hard

Array

Range Query

Sqrt Decomposition

Time: O((n + q) * sqrt(n))

Space: O(n)

type Query = { l: number, r: number };
function mosAlgorithm(arr: number[], queries: Query[]): number[] {
  const blockSize = Math.floor(Math.sqrt(arr.length));
  queries.sort((a, b) => {
    const blockA = Math.floor(a.l / blockSize);
    const blockB = Math.floor(b.l / blockSize);
    return blockA === blockB ? a.r - b.r : blockA - blockB;
  });
  const res: number[] = [];
  let currL = 0, currR = -1, sum = 0;
  const add = (idx: number) => { sum += arr[idx]; };
  const remove = (idx: number) => { sum -= arr[idx]; };
  for (const q of queries) {
    while (currL > q.l) add(--currL);
    while (currR < q.r) add(++currR);
    while (currL < q.l) remove(currL++);
    while (currR > q.r) remove(currR--);
    res.push(sum);
  }
  return res;
}

// Example:
console.log(mosAlgorithm([1,2,3,4,5], [{l:1,r:3},{l:0,r:4}])); // [9,15]

How it works:

Sort queries into blocks and adjust range incrementally to compute results efficiently.

Sparse Table

Efficient static range queries (min/max/gcd).

Medium

Array

Range Query

Preprocessing

Time: O(n log n) preprocessing, O(1) query

Space: O(n log n)

class SparseTable {
  st: number[][];
  log: number[];
  constructor(arr: number[]) {
    const n = arr.length;
    const K = Math.floor(Math.log2(n)) + 1;
    this.st = Array.from({length: n}, () => Array(K).fill(0));
    this.log = Array(n+1).fill(0);
    for (let i = 2; i <= n; i++) this.log[i] = this.log[Math.floor(i/2)] + 1;
    for (let i = 0; i < n; i++) this.st[i][0] = arr[i];
    for (let j = 1; j < K; j++) {
      for (let i = 0; i + (1 << j) <= n; i++) {
        this.st[i][j] = Math.min(this.st[i][j-1], this.st[i + (1 << (j-1))][j-1]);
      }
    }
  }
  query(l: number, r: number): number {
    const j = this.log[r - l + 1];
    return Math.min(this.st[l][j], this.st[r - (1<<j) + 1][j]);
  }
}

// Example:
const st = new SparseTable([1,3,2,7,9,11]);
console.log(st.query(1,3)); // 2

How it works:

Precompute answers for power-of-two ranges. Query with overlap of two ranges.

Meet in the Middle

Divide problem into halves and combine results, useful for large input sizes.

Hard

Array

Divide and Conquer

Time: O(2^(n/2))

Space: O(2^(n/2))

function meetInTheMiddle(nums: number[], target: number): boolean {
  const n = nums.length, mid = Math.floor(n/2);
  const left: number[] = [], right: number[] = [];
  const dfs = (arr: number[], idx: number, end: number, sum: number, store: number[]) => {
    if (idx === end) { store.push(sum); return; }
    dfs(arr, idx+1, end, sum, store);
    dfs(arr, idx+1, end, sum + arr[idx], store);
  };
  dfs(nums, 0, mid, 0, left);
  dfs(nums, mid, n, 0, right);
  right.sort((a,b)=>a-b);
  for (const x of left) {
    let l=0, r=right.length-1;
    while(l<=r){
      const m=Math.floor((l+r)/2);
      if(x+right[m]===target) return true;
      if(x+right[m]<target) l=m+1; else r=m-1;
    }
  }
  return false;
}

// Example:
console.log(meetInTheMiddle([3,34,4,12,5,2], 9)); // true

How it works:

Split array into halves, compute all subset sums, and binary search for complement sums.

Boyer–Moore Majority Vote

Find the majority element (> n/2 occurrences).

Easy

Array

Voting Algorithm

Time: O(n)

Space: O(1)

function majorityElement(nums: number[]): number {
  let count = 0, candidate: number | null = null;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate ? 1 : -1);
  }
  return candidate!;
}

// Example:
console.log(majorityElement([2,2,1,1,1,2,2])); // Output: 2

How it works:

Keep a candidate and adjust counter. The majority element will remain at the end.

Sliding Window Maximum

Find the maximum element in every sliding window of size k.

Hard

Sliding Window

Deque

Array

Time: O(n)

Space: O(k)

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices whose values are smaller than current
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add to result once we have a complete window
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // Output: [3, 3, 5, 5, 6, 7]

How it works:

Use a deque to maintain indices of elements in decreasing order of their values. The front always contains the index of the maximum element in the current window.