1. Two Pointers

• Idea: Use two variables (pointers) moving toward/away from each other.
• Use: Sorted arrays, linked lists, subarray problems.
• Examples: Two-sum II, reverse string, palindrome.

// Classic Problem: Two Sum II (sorted array)
// Goal: Find two numbers in a sorted array that add up to target (O(n) time).
function twoSumTwoPointers(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [left , right ];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return [];
}

// Test
console.log(twoSumTwoPointers([2,7,11,15], 9)); // [1,2]

2. Sliding Window

• Idea: Maintain a dynamic window that slides over the array.
• Use: Subarray / substring with fixed or optimal length.
• Examples: Longest substring without repeating characters.

// Classic Problem: Longest Substring Without Repeating Characters
// Goal: Find length of the longest substring with no duplicate characters (O(n) time).
function lengthOfLongestSubstring(s) {
  let charSet = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      // keep deleting until find the new subarray with no-repeated element and restart couting with it
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // 3

3. Binary Search

• Idea: Repeatedly divide the search space in half.
• Condition: Data must be sorted or monotonic.
• Examples: Search in sorted array, find first/last position.

// Classic Problem: Search in Rotated Sorted Array
// Goal: Find target in a rotated sorted array (O(log n) time).
function searchRotatedArray(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;

    // Left sorted
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // Right sorted
    else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

// Test
console.log(searchRotatedArray([4,5,6,7,0,1,2], 0)); // 4

4. Recursion

• Idea: Function calls itself with smaller input.
• Use: Tree, graph, divide & conquer.
• Risk: Stack overflow if too deep.

// Classic Problem: Fibonacci Number
// Goal: Compute the nth Fibonacci number (recursive approach).
function fibRecursion(n) {
  if (n <= 1) return n;
  return fibRecursion(n - 1) + fibRecursion(n - 2);
}

// no-recursion
function fibRecursion2(n) {
  if (n <= 1) return n;
  let a = 0;
  let b = 1;
  for(let i = 2; i < n; i++){
    let temp = a
    a = b;
    b = b + temp;
  }
  return b
}

// Test
console.log(fibRecursion(5)); // 5

5. Divide and Conquer

• Idea:
  1. Divide → split problem into subproblems
  2. Conquer → solve recursively
  3. Combine → merge results
• Examples: Merge sort, quicksort, binary search.

// Classic Problem: Merge Sort
// Goal: Sort an array by dividing into subarrays, sorting, then merging (O(n log n) time).
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);

  // It is a very important point why the recursion code stands here
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // Combine the sorted results
  return merge(left, right);
}

function merge(left, right) {
  let 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)];
}

// Test
console.log(mergeSort([38,27,43,3,9])); // [3,9,27,38,43]

6. Backtracking

• Idea: Try a path → if wrong, backtrack and try another.
• Use: Combination, permutation, maze, DFS paths.
• Keyword: “Search all possibilities”.

// Classic Problem: Subsets
// Goal: Generate all possible subsets of an array (no duplicates).
function subsets(nums) {
  const result = [];

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

  backtrack([], 0);
  return result;
}

// Test
console.log(subsets([1,2,3])); // [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

7. Dynamic Programming (DP)

• Idea:
  • Store subproblem results to avoid repeated calculation
  • Use state transition
• Use: Fibonacci, knapsack, longest increasing subsequence.
• Key: Overlapping subproblems & optimal substructure.

// Classic Problem: Climbing Stairs
// Goal: Find number of ways to climb n stairs (1 or 2 steps each time).
function climbStairs(n) {
  if (n <= 2) return n;
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;

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

// Test
console.log(climbStairs(5)); // 8

8. Greedy Algorithm

• Idea: Choose locally best choice at each step.
• Use: Activity selection, Huffman coding, coin change (special cases).
• Note: Does not always give global optimum.

// Classic Problem: Jump Game
// Goal: Check if you can reach the last index (each element = max jump length).
function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

// Test
console.log(canJump([2,3,1,1,4])); // true

9. Depth-First Search (DFS)

• Idea: Go as deep as possible before backtracking.
• Use: Tree traversal, graph, connected components, backtracking.

// Classic Problem: Binary Tree Inorder Traversal
// Goal: Traverse a binary tree in left-root-right order.
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function inorderDFS(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

// Test
const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderDFS(root)); // [1,3,2]

10. Breadth-First Search (BFS)

• Idea: Explore level by level.
• Use: Shortest path in unweighted graph, level-order traversal.

// Classic Problem: Binary Tree Level Order Traversal
// Goal: Traverse a binary tree level by level (row by row).
function levelOrderBFS(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

// Test
const tree = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(levelOrderBFS(tree)); // [[3],[9,20],[15,7]]

11. Stack / Monotonic Stack

• Idea: Use stack to maintain order or track history.
• Examples: Valid parentheses, next greater element.

// Classic Problem: Valid Parentheses
// Goal: Check if parentheses are valid (balanced).
function isValidParentheses(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };

  for (const char of s) {
    if (!map[char]) {
      stack.push(char);
    } else {
      const top = stack.pop();
      if (top !== map[char]) return false;
    }
  }
  return stack.length === 0;
}

// Test
console.log(isValidParentheses("()[]{}")); // true

12. Hash Table / Hash Set

• Idea: Use O(1) lookup to speed up existence / counting.
• Examples: Two-sum, duplicate detection, frequency counting.

// Classic Problem: Contains Duplicate
// Goal: Check if array has duplicate elements (O(n) time, O(n) space).
function containsDuplicate(nums) {
  const seen = new Set();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

// Test
console.log(containsDuplicate([1,2,3,1])); // true