> ## Documentation Index
> Fetch the complete documentation index at: https://mintlify.com/Chalarangelo/30-seconds-of-code/llms.txt
> Use this file to discover all available pages before exploring further.

# 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.

```javascript theme={null}
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.

<Note>
  This implementation does not account for duplicate values in the array.
</Note>

### Linear Search

Simple search that checks every element:

```javascript theme={null}
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.

```javascript theme={null}
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.

```javascript theme={null}
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:

```javascript theme={null}
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:

```javascript theme={null}
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

```javascript theme={null}
// 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)

```javascript theme={null}
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

```javascript theme={null}
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

```javascript theme={null}
// 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

```javascript theme={null}
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

```javascript theme={null}
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)

```javascript theme={null}
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

```javascript theme={null}
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

<AccordionGroup>
  <Accordion title="O(1) - Constant Time">
    Operations that take the same amount of time regardless of input size. Example: array access by index, object property lookup.
  </Accordion>

  <Accordion title="O(log n) - Logarithmic Time">
    Algorithms that divide the problem in half each iteration. Example: binary search.
  </Accordion>

  <Accordion title="O(n) - Linear Time">
    Operations that scale linearly with input size. Example: linear search, array iteration.
  </Accordion>

  <Accordion title="O(n log n) - Linearithmic Time">
    Efficient sorting algorithms. Example: merge sort, quick sort (average case).
  </Accordion>

  <Accordion title="O(n²) - Quadratic Time">
    Nested iterations over the input. Example: bubble sort, selection sort, naive duplicate detection.
  </Accordion>

  <Accordion title="O(2^n) - Exponential Time">
    Algorithms that double with each addition to input. Example: recursive fibonacci, subset generation.
  </Accordion>
</AccordionGroup>

## Best Practices

<AccordionGroup>
  <Accordion title="Choose the right algorithm">
    Understand the time and space complexity trade-offs. A simple algorithm may be better for small datasets.
  </Accordion>

  <Accordion title="Consider memoization">
    Cache results of expensive function calls to improve performance of recursive algorithms.
  </Accordion>

  <Accordion title="Use built-in methods when possible">
    JavaScript's built-in methods like `Array.prototype.sort()` are often optimized and faster than custom implementations.
  </Accordion>

  <Accordion title="Test edge cases">
    Always test with empty inputs, single elements, and large datasets to ensure correctness.
  </Accordion>
</AccordionGroup>