JavaScript Algorithms

Learn common algorithms and their implementations in JavaScript

Algorithms in JavaScript

Algorithms are step-by-step procedures for solving problems. Understanding common algorithms helps you write more efficient code and solve complex problems.

Searching Algorithms

Binary Search

The binary search algorithm is a fast and efficient way to find the index of a given element in a sorted array. It works by repeatedly dividing the search interval in half, narrowing down the possible locations of the element.

A binary search is much faster than a linear search, especially for large arrays, as it has a time complexity of O(log n). However, it requires the array to be sorted beforehand.

const binarySearch = (arr, item) => {
  let l = 0, r = arr.length - 1;

  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const guess = arr[mid];

    if (guess === item) return mid;
    if (guess > item) r = mid - 1;
    else l = mid + 1;
  }

  return -1;
};

binarySearch([1, 2, 3, 4, 5], 1); // 0
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

In order to implement the algorithm, we keep track of the left and right boundaries of the search interval, and repeatedly divide it in half until the element is found or the interval is empty.

This implementation does not account for duplicate values in the array.

Linear Search

Simple search that checks every element:

const linearSearch = (arr, item) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === item) return i;
  }
  return -1;
};

linearSearch([3, 1, 4, 1, 5], 4); // 2
linearSearch([3, 1, 4, 1, 5], 6); // -1

Sorting Algorithms

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements and swaps them if they are in the wrong order. The pass through the array is repeated until the array is sorted.

const bubbleSort = arr => {
  let swapped = false;
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    swapped = false;
    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) return a;
  }
  return a;
};

bubbleSort([2, 1, 4, 3]); // [1, 2, 3, 4]

Implementation steps:

• Declare a variable, swapped, that indicates if any values were swapped during the current iteration
• Use the spread operator (...) to clone the original array, arr
• Use a for loop to iterate over the elements of the cloned array, terminating before the last element
• Use a nested for loop to iterate over the segment of the array between 0 and i, swapping any adjacent out of order elements and setting swapped to true
• If swapped is false after an iteration, no more changes are needed, so the cloned array is returned

The algorithm has an average time complexity of O(n^2), where n is the size of the input array.

Selection Sort

Selection sort is an in-place comparison sorting algorithm. It divides the input array into a sorted and an unsorted subarray. It then repeatedly finds the minimum element in the unsorted subarray and swaps it with the leftmost element in the unsorted subarray.

const selectionSort = arr => {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    const min = a
      .slice(i + 1)
      .reduce((acc, val, j) => (val < a[acc] ? j + i + 1 : acc), i);
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
};

selectionSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

Implementation:

• Use the spread operator (...) to clone the original array, arr
• Use a for loop to iterate over elements in the array
• Use Array.prototype.slice() and Array.prototype.reduce() to find the index of the minimum element in the subarray to the right of the current index
• Perform a swap, if necessary

The algorithm has an average time complexity of O(n^2), where n is the size of the input array.

Quick Sort

Efficient divide-and-conquer sorting algorithm:

const quickSort = arr => {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[arr.length - 1];
  const left = arr.filter((x, i) => x <= pivot && i < arr.length - 1);
  const right = arr.filter(x => x > pivot);
  
  return [...quickSort(left), pivot, ...quickSort(right)];
};

quickSort([3, 1, 4, 1, 5, 9, 2, 6]); // [1, 1, 2, 3, 4, 5, 6, 9]

Time complexity: O(n log n) average case, O(n^2) worst case.

Merge Sort

Stable sorting algorithm using divide and conquer:

const mergeSort = arr => {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
};

const merge = (left, right) => {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return [...result, ...left.slice(i), ...right.slice(j)];
};

mergeSort([3, 1, 4, 1, 5, 9, 2, 6]); // [1, 1, 2, 3, 4, 5, 6, 9]

Time complexity: O(n log n) in all cases.

Mathematical Algorithms

Fibonacci Sequence

// Recursive (slow)
const fibonacci = n => {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
};

// Iterative (fast)
const fibonacciIterative = n => {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
};

// Memoized (best of both)
const fibonacciMemo = (() => {
  const cache = new Map([[0, 0], [1, 1]]);
  return function fib(n) {
    if (cache.has(n)) return cache.get(n);
    const result = fib(n - 1) + fib(n - 2);
    cache.set(n, result);
    return result;
  };
})();

fibonacciMemo(10); // 55
fibonacciMemo(50); // 12586269025 (fast!)

Greatest Common Divisor (GCD)

const gcd = (a, b) => {
  if (b === 0) return a;
  return gcd(b, a % b);
};

gcd(48, 18); // 6
gcd(100, 50); // 50

Prime Number Check

const isPrime = n => {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  
  return true;
};

isPrime(17); // true
isPrime(18); // false

Factorial

// Recursive
const factorial = n => n <= 1 ? 1 : n * factorial(n - 1);

// Iterative
const factorialIterative = n => {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
};

factorial(5); // 120
factorialIterative(5); // 120

String Algorithms

Palindrome Check

const isPalindrome = str => {
  const cleaned = str.toLowerCase().replace(/[^a-z0-9]/g, '');
  return cleaned === cleaned.split('').reverse().join('');
};

isPalindrome('A man, a plan, a canal: Panama'); // true
isPalindrome('race a car'); // false

Anagram Check

const isAnagram = (str1, str2) => {
  const normalize = str => str.toLowerCase().replace(/[^a-z]/g, '').split('').sort().join('');
  return normalize(str1) === normalize(str2);
};

isAnagram('listen', 'silent'); // true
isAnagram('hello', 'world'); // false

Array Algorithms

Find Maximum Subarray Sum (Kadane’s Algorithm)

const 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;
};

maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6 ([4, -1, 2, 1])

Two Sum Problem

const twoSum = (arr, target) => {
  const map = new Map();
  
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(arr[i], i);
  }
  
  return null;
};

twoSum([2, 7, 11, 15], 9); // [0, 1] (2 + 7 = 9)
twoSum([3, 2, 4], 6); // [1, 2] (2 + 4 = 6)

Algorithm Complexity

O(1) - Constant Time

Operations that take the same amount of time regardless of input size. Example: array access by index, object property lookup.

O(log n) - Logarithmic Time

Algorithms that divide the problem in half each iteration. Example: binary search.

O(n) - Linear Time

Operations that scale linearly with input size. Example: linear search, array iteration.

O(n log n) - Linearithmic Time

Efficient sorting algorithms. Example: merge sort, quick sort (average case).

O(n²) - Quadratic Time

Nested iterations over the input. Example: bubble sort, selection sort, naive duplicate detection.

O(2^n) - Exponential Time

Algorithms that double with each addition to input. Example: recursive fibonacci, subset generation.

Best Practices

Choose the right algorithm

Understand the time and space complexity trade-offs. A simple algorithm may be better for small datasets.

Consider memoization

Cache results of expensive function calls to improve performance of recursive algorithms.

Use built-in methods when possible

JavaScript’s built-in methods like Array.prototype.sort() are often optimized and faster than custom implementations.

Test edge cases

Always test with empty inputs, single elements, and large datasets to ensure correctness.