Sorting & Searching Fundamentals

Sorting rearranges a array into ascending or descending order. Searching finds the index of a given element. JavaScript provides sort() for sorting and indexOf() for searching, but understanding underlying algorithms is essential for performance tuning and problem-solving.

Bubble Sort

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
};

Selection Sort

Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let minIndex = i;
    for (let j = i; j < this.length; j++) {
      if (this[j] < this[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      const temp = this[i];
      this[i] = this[minIndex];
      this[minIndex] = temp;
    }
  }
};

Insertion Sort

Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i++) {
    const current = this[i];
    let j = i;
    while (j > 0 && this[j - 1] > current) {
      this[j] = this[j - 1];
      j--;
    }
    this[j] = current;
  }
};

Merge Sort

Array.prototype.mergeSort = function () {
  const merge = (left, right) => {
    const result = [];
    while (left.length && right.length) {
      if (left[0] < right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    return [...result, ...left, ...right];
  };

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

  const sorted = sort(this);
  sorted.forEach((value, idx) => (this[idx] = value));
};

Quick Sort

Array.prototype.quickSort = function () {
  const sort = (arr) => {
    if (arr.length <= 1) return arr;
    const pivot = arr[0];
    const left = [],
      right = [];
    for (let i = 1; i < arr.length; i++) {
      (arr[i] < pivot ? left : right).push(arr[i]);
    }
    return [...sort(left), pivot, ...sort(right)];
  };

  const sorted = sort(this);
  sorted.forEach((value, idx) => (this[idx] = value));
};

Sequential Search

Array.prototype.sequentialSearch = function (item) {
  for (let i = 0; i < this.length; i++) {
    if (this[i] === item) return i;
  }
  return -1;
};

Binary Search

Array.prototype.binarySearch = function (item) {
  let low = 0,
    high = this.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const guess = this[mid];
    if (guess === item) return mid;
    guess < item ? (low = mid + 1) : (high = mid - 1);
  }
  return -1;
};

LeetCode Practice

21. Merge Two Sorted Lists

var mergeTwoLists = function (l1, l2) {
  const dummy = new ListNode(0);
  let current = dummy;
  let p1 = l1,
    p2 = l2;
  while (p1 && p2) {
    if (p1.val < p2.val) {
      current.next = p1;
      p1 = p1.next;
    } else {
      current.next = p2;
      p2 = p2.next;
    }
    current = current.next;
  }
  current.next = p1 || p2;
  return dummy.next;
};

374. Guess Number Higher or Lower

var guessNumber = function (n) {
  let low = 1,
    high = n;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const result = guess(mid);
    if (result === 0) return mid;
    result === 1 ? (low = mid + 1) : (high = mid - 1);
  }
};

Divide and Conquer

Divide and conquer splits a problem into smaller sub‑problems, solves them recursively, and combines results. Classic examples include merge sort and quick sort, where array division, recusrion, and merging are used.

226. Invert Binary Tree

var invertTree = function (root) {
  if (!root) return null;
  return {
    val: root.val,
    left: invertTree(root.right),
    right: invertTree(root.left),
  };
};

100. Same Tree

var isSameTree = function (p, q) {
  if (!p && !q) return true;
  if (p && q && p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
    return true;
  }
  return false;
};

101. Symmetric Tree

var isSymmetric = function (root) {
  if (!root) return true;
  const mirror = (left, right) => {
    if (!left && !right) return true;
    if (left && right && left.val === right.val && mirror(left.left, right.right) && mirror(left.right, right.left)) {
      return true;
    }
    return false;
  };
  return mirror(root.left, root.right);
};

Dynamic Programming

Dynamic programming breaks a problem into overlapping sub‑problems and solves each only once, storing results for later use.

70. Climbing Stairs

var climbStairs = function (n) {
  if (n < 2) return 1;
  let prev2 = 1,
    prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
};

198. House Robber

var rob = function (nums) {
  if (!nums.length) return 0;
  let prevNo = 0,
    prevYes = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const newPrevYes = Math.max(prevNo + nums[i], prevYes);
    prevNo = prevYes;
    prevYes = newPrevYes;
  }
  return prevYes;
};

Greedy Algorithm

Greedy algorithms pick the locally optimal choice at each step, hoping it leads to a global optimum. The result is not always optimal but works for many problems.

455. Assign Cookies

var findContentChildren = function (g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let child = 0;
  for (let cookie of s) {
    if (cookie >= g[child]) {
      child++;
    }
  }
  return child;
};

122. Best Time to Buy and Sell Stock II

var maxProfit = function (prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
};

Backtracking

Backtracking incrementally builds candidates to a solution and abandons paths that fail, often using recursion.

46. Permutations

var permute = function (nums) {
  const result = [];
  const dfs = (path) => {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let num of nums) {
      if (!path.includes(num)) {
        path.push(num);
        dfs(path);
        path.pop();
      }
    }
  };
  dfs([]);
  return result;
};

78. Subsets

var subsets = function (nums) {
  const result = [];
  const backtrack = (start, path) => {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  };
  backtrack(0, []);
  return result;
};