JavaScript Algorithms: Sorting, Searching, and Problem Solving

Algorithms are step-by-step procedures for solving computational problems. This comprehensive guide covers essential algorithms implemented in JavaScript, from basic sorting and searching to advanced graph algorithms and dynamic programming.

Sorting Algorithms

Sorting algorithms arrange elements in a specific order, typically ascending or descending.

Bubble Sort

// Bubble Sort - Simple but inefficient O(n²)
class BubbleSort {
  static sort(arr, compareFunction = (a, b) => a - b) {
    const result = [...arr];
    const n = result.length;
    let swapped;

    for (let i = 0; i < n - 1; i++) {
      swapped = false;

      for (let j = 0; j < n - i - 1; j++) {
        if (compareFunction(result[j], result[j + 1]) > 0) {
          // Swap elements
          [result[j], result[j + 1]] = [result[j + 1], result[j]];
          swapped = true;
        }
      }

      // If no swapping occurred, array is already sorted
      if (!swapped) break;
    }

    return result;
  }

  // Animated version that yields intermediate steps
  static *sortAnimated(arr, compareFunction = (a, b) => a - b) {
    const result = [...arr];
    const n = result.length;

    for (let i = 0; i < n - 1; i++) {
      let swapped = false;

      for (let j = 0; j < n - i - 1; j++) {
        // Yield current state for visualization
        yield {
          array: [...result],
          comparing: [j, j + 1],
          sorted: Array.from({ length: i }, (_, k) => n - 1 - k),
        };

        if (compareFunction(result[j], result[j + 1]) > 0) {
          [result[j], result[j + 1]] = [result[j + 1], result[j]];
          swapped = true;

          yield {
            array: [...result],
            swapped: [j, j + 1],
            sorted: Array.from({ length: i }, (_, k) => n - 1 - k),
          };
        }
      }

      if (!swapped) break;
    }

    yield {
      array: [...result],
      comparing: [],
      sorted: Array.from({ length: n }, (_, i) => i),
      completed: true,
    };

    return result;
  }
}

// Usage
console.log(BubbleSort.sort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

Quick Sort

// Quick Sort - Efficient divide-and-conquer O(n log n) average
class QuickSort {
  static sort(arr, compareFunction = (a, b) => a - b) {
    if (arr.length <= 1) return [...arr];

    const result = [...arr];
    this._quickSort(result, 0, result.length - 1, compareFunction);
    return result;
  }

  static _quickSort(arr, low, high, compareFunction) {
    if (low < high) {
      const pivotIndex = this._partition(arr, low, high, compareFunction);

      this._quickSort(arr, low, pivotIndex - 1, compareFunction);
      this._quickSort(arr, pivotIndex + 1, high, compareFunction);
    }
  }

  static _partition(arr, low, high, compareFunction) {
    // Choose the rightmost element as pivot
    const pivot = arr[high];
    let i = low - 1; // Index of smaller element

    for (let j = low; j < high; j++) {
      if (compareFunction(arr[j], pivot) <= 0) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  }

  // Three-way partitioning for handling duplicates efficiently
  static sortThreeWay(arr, compareFunction = (a, b) => a - b) {
    if (arr.length <= 1) return [...arr];

    const result = [...arr];
    this._quickSortThreeWay(result, 0, result.length - 1, compareFunction);
    return result;
  }

  static _quickSortThreeWay(arr, low, high, compareFunction) {
    if (low >= high) return;

    const [lt, gt] = this._partitionThreeWay(arr, low, high, compareFunction);

    this._quickSortThreeWay(arr, low, lt - 1, compareFunction);
    this._quickSortThreeWay(arr, gt + 1, high, compareFunction);
  }

  static _partitionThreeWay(arr, low, high, compareFunction) {
    const pivot = arr[low];
    let i = low;
    let lt = low;
    let gt = high;

    while (i <= gt) {
      const cmp = compareFunction(arr[i], pivot);

      if (cmp < 0) {
        [arr[lt++], arr[i++]] = [arr[i], arr[lt]];
      } else if (cmp > 0) {
        [arr[i], arr[gt--]] = [arr[gt], arr[i]];
      } else {
        i++;
      }
    }

    return [lt, gt];
  }
}

// Usage
const numbers = [3, 6, 8, 10, 1, 2, 1];
console.log(QuickSort.sort(numbers)); // [1, 1, 2, 3, 6, 8, 10]
console.log(QuickSort.sortThreeWay(numbers)); // [1, 1, 2, 3, 6, 8, 10]

Merge Sort

// Merge Sort - Stable divide-and-conquer O(n log n)
class MergeSort {
  static sort(arr, compareFunction = (a, b) => a - b) {
    if (arr.length <= 1) return [...arr];

    const mid = Math.floor(arr.length / 2);
    const left = this.sort(arr.slice(0, mid), compareFunction);
    const right = this.sort(arr.slice(mid), compareFunction);

    return this._merge(left, right, compareFunction);
  }

  static _merge(left, right, compareFunction) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (compareFunction(left[leftIndex], right[rightIndex]) <= 0) {
        result.push(left[leftIndex]);
        leftIndex++;
      } else {
        result.push(right[rightIndex]);
        rightIndex++;
      }
    }

    // Add remaining elements
    while (leftIndex < left.length) {
      result.push(left[leftIndex]);
      leftIndex++;
    }

    while (rightIndex < right.length) {
      result.push(right[rightIndex]);
      rightIndex++;
    }

    return result;
  }

  // In-place merge sort to save memory
  static sortInPlace(arr, compareFunction = (a, b) => a - b) {
    const result = [...arr];
    this._mergeSortInPlace(result, 0, result.length - 1, compareFunction);
    return result;
  }

  static _mergeSortInPlace(arr, left, right, compareFunction) {
    if (left >= right) return;

    const mid = Math.floor((left + right) / 2);

    this._mergeSortInPlace(arr, left, mid, compareFunction);
    this._mergeSortInPlace(arr, mid + 1, right, compareFunction);
    this._mergeInPlace(arr, left, mid, right, compareFunction);
  }

  static _mergeInPlace(arr, left, mid, right, compareFunction) {
    const leftArray = arr.slice(left, mid + 1);
    const rightArray = arr.slice(mid + 1, right + 1);

    let i = 0,
      j = 0,
      k = left;

    while (i < leftArray.length && j < rightArray.length) {
      if (compareFunction(leftArray[i], rightArray[j]) <= 0) {
        arr[k] = leftArray[i];
        i++;
      } else {
        arr[k] = rightArray[j];
        j++;
      }
      k++;
    }

    while (i < leftArray.length) {
      arr[k] = leftArray[i];
      i++;
      k++;
    }

    while (j < rightArray.length) {
      arr[k] = rightArray[j];
      j++;
      k++;
    }
  }
}

// Custom object sorting
const people = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 },
];

const sortedByAge = MergeSort.sort(people, (a, b) => a.age - b.age);
console.log(sortedByAge);

Heap Sort

// Heap Sort - In-place O(n log n) algorithm
class HeapSort {
  static sort(arr, compareFunction = (a, b) => a - b) {
    const result = [...arr];
    const n = result.length;

    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this._heapify(result, n, i, compareFunction);
    }

    // Extract elements from heap one by one
    for (let i = n - 1; i > 0; i--) {
      // Move current root to end
      [result[0], result[i]] = [result[i], result[0]];

      // Call heapify on the reduced heap
      this._heapify(result, i, 0, compareFunction);
    }

    return result;
  }

  static _heapify(arr, n, i, compareFunction) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    // If left child is larger than root
    if (left < n && compareFunction(arr[left], arr[largest]) > 0) {
      largest = left;
    }

    // If right child is larger than largest so far
    if (right < n && compareFunction(arr[right], arr[largest]) > 0) {
      largest = right;
    }

    // If largest is not root
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];

      // Recursively heapify the affected sub-tree
      this._heapify(arr, n, largest, compareFunction);
    }
  }
}

// Heap data structure for priority queues
class Heap {
  constructor(compareFunction = (a, b) => a - b) {
    this.items = [];
    this.compare = compareFunction;
  }

  insert(item) {
    this.items.push(item);
    this._heapifyUp(this.items.length - 1);
    return this;
  }

  extractMax() {
    if (this.items.length === 0) return null;
    if (this.items.length === 1) return this.items.pop();

    const max = this.items[0];
    this.items[0] = this.items.pop();
    this._heapifyDown(0);

    return max;
  }

  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }

  size() {
    return this.items.length;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  _heapifyUp(index) {
    if (index === 0) return;

    const parentIndex = Math.floor((index - 1) / 2);

    if (this.compare(this.items[index], this.items[parentIndex]) > 0) {
      [this.items[index], this.items[parentIndex]] = [
        this.items[parentIndex],
        this.items[index],
      ];
      this._heapifyUp(parentIndex);
    }
  }

  _heapifyDown(index) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let largest = index;

    if (
      leftChild < this.items.length &&
      this.compare(this.items[leftChild], this.items[largest]) > 0
    ) {
      largest = leftChild;
    }

    if (
      rightChild < this.items.length &&
      this.compare(this.items[rightChild], this.items[largest]) > 0
    ) {
      largest = rightChild;
    }

    if (largest !== index) {
      [this.items[index], this.items[largest]] = [
        this.items[largest],
        this.items[index],
      ];
      this._heapifyDown(largest);
    }
  }
}

// Usage
console.log(HeapSort.sort([12, 11, 13, 5, 6, 7])); // [5, 6, 7, 11, 12, 13]

const maxHeap = new Heap();
[3, 1, 4, 1, 5, 9, 2, 6].forEach((n) => maxHeap.insert(n));
console.log(maxHeap.extractMax()); // 9

Searching Algorithms

Binary Search

// Binary Search - O(log n) for sorted arrays
class BinarySearch {
  static search(arr, target, compareFunction = (a, b) => a - b) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const comparison = compareFunction(arr[mid], target);

      if (comparison === 0) {
        return mid; // Found target
      } else if (comparison < 0) {
        left = mid + 1; // Target is in right half
      } else {
        right = mid - 1; // Target is in left half
      }
    }

    return -1; // Target not found
  }

  // Find first occurrence of target
  static searchFirst(arr, target, compareFunction = (a, b) => a - b) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const comparison = compareFunction(arr[mid], target);

      if (comparison === 0) {
        result = mid;
        right = mid - 1; // Continue searching in left half
      } else if (comparison < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return result;
  }

  // Find last occurrence of target
  static searchLast(arr, target, compareFunction = (a, b) => a - b) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const comparison = compareFunction(arr[mid], target);

      if (comparison === 0) {
        result = mid;
        left = mid + 1; // Continue searching in right half
      } else if (comparison < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return result;
  }

  // Find insertion point for target
  static searchInsertionPoint(arr, target, compareFunction = (a, b) => a - b) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (compareFunction(arr[mid], target) < 0) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return left;
  }

  // Binary search on answer (for optimization problems)
  static searchAnswer(predicate, low, high, precision = 1e-9) {
    while (high - low > precision) {
      const mid = (low + high) / 2;

      if (predicate(mid)) {
        high = mid;
      } else {
        low = mid;
      }
    }

    return (low + high) / 2;
  }
}

// Usage examples
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(BinarySearch.search(sortedArray, 7)); // 3
console.log(BinarySearch.search(sortedArray, 8)); // -1

const duplicateArray = [1, 2, 2, 2, 3, 4, 5];
console.log(BinarySearch.searchFirst(duplicateArray, 2)); // 1
console.log(BinarySearch.searchLast(duplicateArray, 2)); // 3

// Binary search on answer example: find square root
function findSquareRoot(x, precision = 1e-6) {
  return BinarySearch.searchAnswer((mid) => mid * mid >= x, 0, x, precision);
}

console.log(findSquareRoot(25)); // ~5.0
console.log(findSquareRoot(2)); // ~1.414

Depth-First Search (DFS)

// Graph representation and DFS implementation
class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
    return this;
  }

  addEdge(vertex1, vertex2, directed = false) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);

    this.adjacencyList.get(vertex1).push(vertex2);

    if (!directed) {
      this.adjacencyList.get(vertex2).push(vertex1);
    }

    return this;
  }

  // Recursive DFS
  dfsRecursive(startVertex, callback) {
    const visited = new Set();
    const result = [];

    const dfs = (vertex) => {
      if (visited.has(vertex)) return;

      visited.add(vertex);
      result.push(vertex);

      if (callback) callback(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        dfs(neighbor);
      }
    };

    dfs(startVertex);
    return result;
  }

  // Iterative DFS using stack
  dfsIterative(startVertex, callback) {
    const visited = new Set();
    const stack = [startVertex];
    const result = [];

    while (stack.length > 0) {
      const vertex = stack.pop();

      if (visited.has(vertex)) continue;

      visited.add(vertex);
      result.push(vertex);

      if (callback) callback(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      // Add neighbors in reverse order to maintain left-to-right traversal
      for (let i = neighbors.length - 1; i >= 0; i--) {
        if (!visited.has(neighbors[i])) {
          stack.push(neighbors[i]);
        }
      }
    }

    return result;
  }

  // Find path between two vertices using DFS
  findPath(start, end) {
    const visited = new Set();
    const path = [];

    const dfs = (vertex) => {
      if (visited.has(vertex)) return false;

      visited.add(vertex);
      path.push(vertex);

      if (vertex === end) return true;

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (dfs(neighbor)) return true;
      }

      path.pop(); // Backtrack
      return false;
    };

    return dfs(start) ? path : null;
  }

  // Check if graph has cycle (for directed graph)
  hasCycle() {
    const color = new Map(); // 0: white, 1: gray, 2: black

    // Initialize all vertices as white
    for (const vertex of this.adjacencyList.keys()) {
      color.set(vertex, 0);
    }

    const dfs = (vertex) => {
      color.set(vertex, 1); // Mark as gray (visiting)

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (color.get(neighbor) === 1) {
          return true; // Back edge found - cycle detected
        }
        if (color.get(neighbor) === 0 && dfs(neighbor)) {
          return true;
        }
      }

      color.set(vertex, 2); // Mark as black (visited)
      return false;
    };

    for (const vertex of this.adjacencyList.keys()) {
      if (color.get(vertex) === 0 && dfs(vertex)) {
        return true;
      }
    }

    return false;
  }

  // Topological sort using DFS
  topologicalSort() {
    const visited = new Set();
    const stack = [];

    const dfs = (vertex) => {
      visited.add(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfs(neighbor);
        }
      }

      stack.push(vertex);
    };

    for (const vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        dfs(vertex);
      }
    }

    return stack.reverse();
  }
}

// Usage examples
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log(graph.dfsRecursive('A')); // ['A', 'B', 'D', 'E', 'C', 'F']
console.log(graph.findPath('A', 'F')); // ['A', 'B', 'D', 'F']

Breadth-First Search (BFS)

// BFS implementation for shortest path
class BFSGraph extends Graph {
  // Standard BFS traversal
  bfs(startVertex, callback) {
    const visited = new Set();
    const queue = [startVertex];
    const result = [];

    visited.add(startVertex);

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);

      if (callback) callback(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return result;
  }

  // Find shortest path using BFS
  shortestPath(start, end) {
    const visited = new Set();
    const queue = [{ vertex: start, path: [start] }];

    visited.add(start);

    while (queue.length > 0) {
      const { vertex, path } = queue.shift();

      if (vertex === end) {
        return path;
      }

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push({
            vertex: neighbor,
            path: [...path, neighbor],
          });
        }
      }
    }

    return null; // No path found
  }

  // Find shortest distance to all vertices
  shortestDistances(start) {
    const distances = new Map();
    const visited = new Set();
    const queue = [{ vertex: start, distance: 0 }];

    distances.set(start, 0);
    visited.add(start);

    while (queue.length > 0) {
      const { vertex, distance } = queue.shift();

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          distances.set(neighbor, distance + 1);
          queue.push({
            vertex: neighbor,
            distance: distance + 1,
          });
        }
      }
    }

    return distances;
  }

  // Check if graph is bipartite using BFS
  isBipartite() {
    const color = new Map();

    for (const startVertex of this.adjacencyList.keys()) {
      if (color.has(startVertex)) continue;

      const queue = [startVertex];
      color.set(startVertex, 0);

      while (queue.length > 0) {
        const vertex = queue.shift();
        const currentColor = color.get(vertex);

        const neighbors = this.adjacencyList.get(vertex) || [];
        for (const neighbor of neighbors) {
          if (!color.has(neighbor)) {
            color.set(neighbor, 1 - currentColor);
            queue.push(neighbor);
          } else if (color.get(neighbor) === currentColor) {
            return false; // Same color adjacent vertices
          }
        }
      }
    }

    return true;
  }

  // Find connected components
  connectedComponents() {
    const visited = new Set();
    const components = [];

    for (const vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        const component = [];
        const queue = [vertex];
        visited.add(vertex);

        while (queue.length > 0) {
          const current = queue.shift();
          component.push(current);

          const neighbors = this.adjacencyList.get(current) || [];
          for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
              visited.add(neighbor);
              queue.push(neighbor);
            }
          }
        }

        components.push(component);
      }
    }

    return components;
  }
}

// Usage examples
const bfsGraph = new BFSGraph();
bfsGraph.addEdge('A', 'B');
bfsGraph.addEdge('A', 'C');
bfsGraph.addEdge('B', 'D');
bfsGraph.addEdge('C', 'E');
bfsGraph.addEdge('D', 'F');
bfsGraph.addEdge('E', 'F');

console.log(bfsGraph.bfs('A')); // ['A', 'B', 'C', 'D', 'E', 'F']
console.log(bfsGraph.shortestPath('A', 'F')); // ['A', 'B', 'D', 'F']
console.log(bfsGraph.shortestDistances('A')); // Map of distances

Dynamic Programming

Common DP Problems

// Dynamic Programming utilities and common problems
class DynamicProgramming {
  // Memoization decorator
  static memoize(fn) {
    const cache = new Map();

    return function (...args) {
      const key = JSON.stringify(args);

      if (cache.has(key)) {
        return cache.get(key);
      }

      const result = fn.apply(this, args);
      cache.set(key, result);
      return result;
    };
  }

  // Fibonacci with memoization
  static fibonacci = this.memoize((n) => {
    if (n <= 1) return n;
    return (
      DynamicProgramming.fibonacci(n - 1) + DynamicProgramming.fibonacci(n - 2)
    );
  });

  // Fibonacci with tabulation (bottom-up)
  static fibonacciTabulation(n) {
    if (n <= 1) return n;

    const dp = [0, 1];

    for (let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
  }

  // Fibonacci with space optimization
  static fibonacciOptimized(n) {
    if (n <= 1) return n;

    let prev2 = 0;
    let prev1 = 1;

    for (let i = 2; i <= n; i++) {
      const current = prev1 + prev2;
      prev2 = prev1;
      prev1 = current;
    }

    return prev1;
  }

  // Longest Common Subsequence
  static longestCommonSubsequence(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array(m + 1)
      .fill()
      .map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (str1[i - 1] === str2[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[m][n];
  }

  // Knapsack Problem (0/1)
  static knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(n + 1)
      .fill()
      .map(() => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
      for (let w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
          dp[i][w] = Math.max(
            values[i - 1] + dp[i - 1][w - weights[i - 1]],
            dp[i - 1][w]
          );
        } else {
          dp[i][w] = dp[i - 1][w];
        }
      }
    }

    return dp[n][capacity];
  }

  // Coin Change Problem
  static coinChange(coins, amount) {
    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
      for (const coin of coins) {
        if (coin <= i) {
          dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
      }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
  }

  // Edit Distance (Levenshtein Distance)
  static editDistance(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array(m + 1)
      .fill()
      .map(() => Array(n + 1).fill(0));

    // Initialize base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (str1[i - 1] === str2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] =
            1 +
            Math.min(
              dp[i - 1][j], // deletion
              dp[i][j - 1], // insertion
              dp[i - 1][j - 1] // substitution
            );
        }
      }
    }

    return dp[m][n];
  }

  // Maximum Subarray Sum (Kadane's Algorithm)
  static maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
      maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
      maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
  }

  // Unique Paths in Grid
  static uniquePaths(m, n) {
    const dp = Array(m)
      .fill()
      .map(() => Array(n).fill(1));

    for (let i = 1; i < m; i++) {
      for (let j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }

    return dp[m - 1][n - 1];
  }

  // House Robber Problem
  static houseRobber(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev2 = 0;
    let prev1 = nums[0];

    for (let i = 1; i < nums.length; i++) {
      const current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }

    return prev1;
  }
}

// Usage examples
console.log(DynamicProgramming.fibonacci(10)); // 55
console.log(DynamicProgramming.longestCommonSubsequence('ABCDGH', 'AEDFHR')); // 3
console.log(DynamicProgramming.knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9
console.log(DynamicProgramming.coinChange([1, 3, 4], 6)); // 2
console.log(DynamicProgramming.editDistance('kitten', 'sitting')); // 3
console.log(DynamicProgramming.maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

Algorithm Analysis

// Performance analysis and benchmarking tools
class AlgorithmAnalysis {
  // Time a function execution
  static timeFunction(fn, ...args) {
    const start = performance.now();
    const result = fn(...args);
    const end = performance.now();

    return {
      result,
      timeMs: end - start,
      timeFormatted: this.formatTime(end - start),
    };
  }

  // Memory usage estimation (approximate)
  static estimateMemoryUsage(data) {
    const seen = new WeakSet();

    function sizeOf(obj) {
      if (obj === null || typeof obj !== 'object') {
        return 8; // Approximate size for primitives
      }

      if (seen.has(obj)) {
        return 0; // Already counted
      }

      seen.add(obj);

      let size = 0;

      if (Array.isArray(obj)) {
        size += obj.length * 8; // Approximate pointer size
        for (const item of obj) {
          size += sizeOf(item);
        }
      } else {
        const keys = Object.keys(obj);
        size += keys.length * 16; // Key-value pair overhead

        for (const key of keys) {
          size += key.length * 2; // String key size
          size += sizeOf(obj[key]);
        }
      }

      return size;
    }

    return sizeOf(data);
  }

  // Compare algorithm performance
  static compareAlgorithms(algorithms, testCases) {
    const results = [];

    for (const testCase of testCases) {
      const caseResults = {
        input: testCase.name || `Input size: ${testCase.data.length}`,
        results: [],
      };

      for (const algorithm of algorithms) {
        const timing = this.timeFunction(algorithm.fn, ...testCase.data);

        caseResults.results.push({
          name: algorithm.name,
          time: timing.timeMs,
          timeFormatted: timing.timeFormatted,
          result: timing.result,
        });
      }

      results.push(caseResults);
    }

    return results;
  }

  // Generate test data
  static generateTestData(size, type = 'random') {
    switch (type) {
      case 'random':
        return Array.from({ length: size }, () =>
          Math.floor(Math.random() * 1000)
        );

      case 'sorted':
        return Array.from({ length: size }, (_, i) => i);

      case 'reverse':
        return Array.from({ length: size }, (_, i) => size - i - 1);

      case 'nearly_sorted':
        const arr = Array.from({ length: size }, (_, i) => i);
        // Swap a few random elements
        for (let i = 0; i < size * 0.1; i++) {
          const idx1 = Math.floor(Math.random() * size);
          const idx2 = Math.floor(Math.random() * size);
          [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
        }
        return arr;

      default:
        throw new Error(`Unknown test data type: ${type}`);
    }
  }

  // Format time for display
  static formatTime(ms) {
    if (ms < 1) {
      return `${(ms * 1000).toFixed(2)}μs`;
    } else if (ms < 1000) {
      return `${ms.toFixed(2)}ms`;
    } else {
      return `${(ms / 1000).toFixed(2)}s`;
    }
  }

  // Big O complexity analyzer (simplified)
  static analyzeComplexity(fn, maxSize = 1000, step = 100) {
    const measurements = [];

    for (let size = step; size <= maxSize; size += step) {
      const data = this.generateTestData(size);
      const timing = this.timeFunction(fn, data);

      measurements.push({
        size,
        time: timing.timeMs,
      });
    }

    // Simple heuristic to guess complexity
    const ratios = [];
    for (let i = 1; i < measurements.length; i++) {
      const prev = measurements[i - 1];
      const curr = measurements[i];

      const sizeRatio = curr.size / prev.size;
      const timeRatio = curr.time / prev.time;

      ratios.push(timeRatio / sizeRatio);
    }

    const avgRatio = ratios.reduce((a, b) => a + b, 0) / ratios.length;

    let complexity;
    if (avgRatio < 1.5) {
      complexity = 'O(n)';
    } else if (avgRatio < 2.5) {
      complexity = 'O(n log n)';
    } else if (avgRatio < 4) {
      complexity = 'O(n²)';
    } else {
      complexity = 'O(n³) or higher';
    }

    return {
      measurements,
      estimatedComplexity: complexity,
      averageRatio: avgRatio,
    };
  }
}

// Usage examples
const sortingAlgorithms = [
  { name: 'Quick Sort', fn: QuickSort.sort },
  { name: 'Merge Sort', fn: MergeSort.sort },
  { name: 'Heap Sort', fn: HeapSort.sort },
  { name: 'Bubble Sort', fn: BubbleSort.sort },
];

const testCases = [
  { name: 'Small Random', data: [AlgorithmAnalysis.generateTestData(100)] },
  { name: 'Medium Random', data: [AlgorithmAnalysis.generateTestData(1000)] },
  {
    name: 'Sorted Data',
    data: [AlgorithmAnalysis.generateTestData(1000, 'sorted')],
  },
];

const comparison = AlgorithmAnalysis.compareAlgorithms(
  sortingAlgorithms,
  testCases
);
console.log('Algorithm Comparison:', comparison);

// Analyze complexity
const complexityAnalysis = AlgorithmAnalysis.analyzeComplexity(QuickSort.sort);
console.log('Quick Sort Complexity Analysis:', complexityAnalysis);

Conclusion

Mastering algorithms in JavaScript requires understanding both the theoretical concepts and practical implementations. Start with basic sorting and searching algorithms, then progress to more complex topics like graph algorithms and dynamic programming. Practice implementing these algorithms from scratch, analyze their time and space complexity, and learn when to apply each one. Remember that choosing the right algorithm for your specific use case is often more important than knowing every algorithm in detail.