DSA Problem-Solving Patterns and Practice Problems

Sliding Window

The Sliding Window technique efficiently processes contiguous subarrays or substrings by maintaining a window and sliding it over the data. At each step, we update the result using the previous window’s computations. This pattern is ideal for problems requiring analysis of fixed-size or variable-size windows (subarrays/substrings) in an array or string. Below are practice problems that use this pattern:

Maximum Sum of Subarray of Size K (Beginner) – GeeksforGeeks: Given an array and integer k, find the maximum sum of any subarray of size k. For example, for [100,200,300,400] with k=2, the answer is 700 (subarray [300,400]).
```
function maxSubarraySum(arr, k) {
  if (arr.length < k) return null;
  let windowSum = 0, maxSum = 0;
  // Compute sum of first window of size k
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;
  // Slide the window by 1 each step
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];      // add entering, subtract leaving
    maxSum = Math.max(maxSum, windowSum); // update max sum
  }
  return maxSum;
}
// Example:
console.log(maxSubarraySum([1,4,2,10,23,3,1,0,20], 4)); // 39 ([4,2,10,23])
```
Explanation: We maintain the sum of the current window of size k, then slide one element at a time. At each slide, we add the new element entering the window and subtract the element leaving the window. This way we compute each subarray sum in O(1) after initial O(k) setup. The sliding window avoids recomputing sums from scratch.
Longest Substring Without Repeating Characters (Intermediate) – GeeksforGeeks: Given a string, find the length of the longest substring without repeating characters. For example, "geeksforgeeks" yields length 7 ("ksforge" etc.).
```
function lengthOfLongestSubstring(s) {
  let seen = new Map();
  let maxLen = 0, start = 0;
  for (let end = 0; end < s.length; end++) {
    if (seen.has(s[end])) {
      // Move start next to last occurrence to avoid duplicates
      start = Math.max(start, seen.get(s[end]) + 1);
    }
    seen.set(s[end], end);
    maxLen = Math.max(maxLen, end - start + 1);
  }
  return maxLen;
}
// Example:
console.log(lengthOfLongestSubstring("geeksforgeeks")); // 7
```
Explanation: This uses a variable-size sliding window on the string. We expand the window by moving end forward and track the last seen index of each character. If a repeat is found, we slide the start to one past the previous index of that character. This ensures the window always has unique characters. The window slides efficiently through the string, updating the maximum length.
Smallest Subarray with Sum Greater Than X (Intermediate) – GeeksforGeeks: Given an array of positives and a number x, find the length of the smallest contiguous subarray whose sum is strictly greater than x. For instance, in [1, 4, 45, 6, 0, 19] with x=51, the smallest subarray length is 3 ([4,45,6]).
```
function smallestSubarrayWithSumGreaterThan(arr, target) {
  let left = 0, sum = 0;
  let minLen = Infinity;
  for (let right = 0; right < arr.length; right++) {
    sum += arr[right];
    // Shrink window from left while sum exceeds target
    while (sum > target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= arr[left];
      left++;
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// Example:
console.log(smallestSubarrayWithSumGreaterThan([1,4,45,6,0,19], 51)); // 3
```
Explanation: We expand the window by moving right and accumulating sum. Whenever sum exceeds target, we shrink the window from the left (increasing left) to try to find a smaller subarray. We record the smallest window length that satisfies the sum condition. This two-pointer sliding window approach achieves O(n) time.

Two Pointers

The Two Pointers pattern uses two indices (often starting at opposite ends or one fixed and one moving) to solve problems in sorted arrays or linked structures. It often applies to finding pairs, removing duplicates, or container-size problems. The key is that both pointers move toward each other (or in one direction) based on some condition. Typical examples include finding pairs with a given sum or partitioning arrays.

Remove Duplicates from Sorted Array (Beginner) – GeeksforGeeks: Given a sorted array, remove duplicates in-place such that each element appears only once and return the new length. Example: [2,3,3,3,6,9,9] becomes [2,3,6,9] with length 4.
```
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1; // place to write next unique element
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i-1]) {
      nums[write] = nums[i];
      write++;
    }
  }
  return write;
}
// Example:
let arr = [2,3,3,3,6,9,9];
console.log(removeDuplicates(arr)); // 4; arr is modified to [2,3,6,9,...]
```
Explanation: We use two pointers: one (i) to scan through the array, and one (write) to build the list of unique elements. Whenever we see a new number (nums[i] != nums[i-1]), we write it into position write and increment write. This ensures all unique values are moved to the front. Because the array is sorted, duplicates are adjacent, making this approach straightforward.
Two Sum II (Sorted Array) (Intermediate) – GeeksforGeeks: Given a sorted 1-indexed array and a target, find the indices of the two numbers that add up to the target. For example, numbers = [2,7,11,15], target = 9 returns [1,2] (because 2+7=9).
```
function twoSumSorted(numbers, target) {
  let left = 0, right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) {
      return [left+1, right+1]; // 1-indexed result
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return []; // no solution
}
// Example:
console.log(twoSumSorted([2,7,11,15], 9)); // [1, 2]
```
Explanation: We place one pointer (left) at the start and the other (right) at the end of the sorted array. We compute the sum; if it’s too small, we move left rightward to increase it, and if it’s too large, we move right leftward to decrease it. This two-pointer strategy finds the pair in O(n) time.
Container With Most Water (Intermediate) – GeeksforGeeks: Given an array of non-negative heights representing vertical lines on the x-axis, find two lines that together with the x-axis form a container holding the most water. For example, [1,8,6,2,5,4,8,3,7] yields area 49 between heights 8 and 7.
```
function maxContainerArea(height) {
  let left = 0, right = height.length - 1;
  let maxArea = 0;
  while (left < right) {
    // Calculate area between lines at left and right
    const h = Math.min(height[left], height[right]);
    const area = h * (right - left);
    maxArea = Math.max(maxArea, area);
    // Move the pointer at the shorter line inward
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return maxArea;
}
// Example:
console.log(maxContainerArea([1,8,6,2,5,4,8,3,7])); // 49
```
Explanation: We use two pointers at the ends of the height array and compute the area. To potentially find a larger area, we move the pointer at the shorter line inward (since moving the taller one cannot increase the minimum height). We update maxArea as we go. This greedy two-pointer approach finds the maximum area in one pass.

Fast and Slow Pointers

The Fast and Slow Pointers (also called Floyd’s cycle-finding) pattern uses two pointers that move at different speeds through a linked structure or sequence. It’s ideal for detecting cycles or finding midpoints. For instance, moving one pointer by one step (slow) and another by two steps (fast) can detect a loop in a linked list or find the middle node in a single pass.

Linked List Cycle Detection (Beginner) – GeeksforGeeks: Given the head of a linked list, determine if there is a cycle (loop) in the list. Using Floyd’s algorithm, we advance slow = slow.next and fast = fast.next.next; if they ever meet, there is a cycle.
```
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}
// (Assumes `head` is the start of a linked list.)
```
Explanation: Both pointers start at the head. In each step slow moves one node, fast moves two. If there’s a cycle, fast will eventually lap slow inside the loop, meeting it at some node. If fast reaches the end (null), there is no cycle.
Middle of Linked List (Beginner) – LeetCode 876: Given a linked list, return its middle node. If there are two middle nodes, return the second one. For example, 1→2→3→4→5 returns 3, and 1→2→3→4→5→6 returns 4.
```
function middleNode(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;  // slow is now at middle
}
```
Explanation: Again using two pointers, fast moves twice as fast as slow. When fast reaches the end of the list, slow will be at the midpoint. This finds the middle in one pass without knowing the length in advance.
Happy Number (Intermediate) – LeetCode 202: A “happy” number is defined by iterating the sum of squares of digits: repeatedly replace the number by the sum of squares of its digits. If this process ends in 1, the number is happy; if it loops endlessly in a cycle not including 1, it’s not. For example, 19 is happy. We can use a fast/slow cycle detection:
```
function isHappy(n) {
  // Helper to compute sum of squares of digits
  function nextNum(x) {
    let sum = 0;
    while (x > 0) {
      let d = x % 10;
      sum += d*d;
      x = Math.floor(x / 10);
    }
    return sum;
  }
  let slow = n, fast = n;
  do {
    slow = nextNum(slow);
    fast = nextNum(nextNum(fast));
  } while (slow !== fast);
  return slow === 1;
}
// Example:
console.log(isHappy(19)); // true
```
Explanation: Here, treating each number as a node in a sequence, we move slow one step (nextNum(slow)) and fast two steps. If a cycle is reached (other than 1), slow will meet fast again. If the cycle is at 1, we return true. This is fast/slow pointer applied to a number transformation sequence (Floyd’s cycle detection).

Merge Intervals

Problems in the Merge Intervals category involve merging or managing overlapping intervals. The common approach is to sort intervals by start time and then iterate, merging any overlapping intervals as you go. This pattern applies to merging schedules, inserting new intervals, or counting overlapping intervals.

Merge Intervals (Beginner) – LeetCode 56: Given a collection of intervals, merge all overlapping intervals. For example, [[1,3],[2,6],[8,10],[15,18]] merges to [[1,6],[8,10],[15,18]].

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  // Sort intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      // Overlap: merge by updating the end
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      // No overlap: add new interval
      merged.push(intervals[i].slice());
    }
  }
  return merged;
}
// Example:
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]])); // [[1,6],[8,10],[15,18]]

Explanation: After sorting by start time, we keep a “last merged” interval. For each new interval, if it overlaps (its start is ≤ last end), we extend the last interval’s end. Otherwise, we append it as a separate interval. This merges all overlapping intervals in one pass.

Insert Interval (Intermediate) – LeetCode 57: Given non-overlapping intervals sorted by start and a new interval, insert the new interval and merge if needed. For example, inserting [4,8] into [[1,3],[6,9]] yields [[1,3],[4,9]].

function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  // Add all intervals that end before newInterval starts
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
  // Merge overlaps with newInterval
  let [start, end] = newInterval;
  while (i < intervals.length && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);
  // Add remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}
// Example:
console.log(insertInterval([[1,3],[6,9]], [2,5])); // [[1,5],[6,9]]

Explanation: We first add all intervals that come completely before the new one. Then we merge all overlapping intervals with the new one by extending its start/end as needed. Finally, we append the rest. This uses the merge-interval logic after handling the insertion point.

Non-overlapping Intervals (Removal) (Intermediate) – LeetCode 435: Given intervals, find the minimum number to remove so that the rest are non-overlapping. Example: [[1,2],[2,3],[3,4],[1,3]] requires removing 1 interval.
```
function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  // Sort by end time for optimal greedy removals
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0;
  let prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) {
      // Overlap: remove this interval
      count++;
    } else {
      prevEnd = intervals[i][1];
    }
  }
  return count;
}
// Example:
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1
```
Explanation: After sorting by end times, we keep track of the end of the last interval we kept. If the next interval’s start is before this end, it overlaps and must be removed (increment count). Otherwise, we move the “last end” forward. This greedy approach minimizes removals.

Binary Search

Binary Search relies on the data being sorted and repeatedly halves the search space. It’s used for finding elements, first/last occurrences, or thresholds in sorted arrays with O(log n) time.

Binary Search (Find Element) (Beginner) – Example from GeeksforGeeks: Given a sorted array and a target value, return its index or indicate not found. For example, in [10,20,40,45,55], searching for 45 returns index 3.
```
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1; // not found
}
// Example:
console.log(binarySearch([10,20,40,45,55], 45)); // 3
```
Explanation: We compare the target to the middle element. If equal, we’re done; if smaller, search left half; if larger, search right half. Each comparison halves the range.

Search in Rotated Sorted Array (Intermediate) – LeetCode 33: A sorted array is “rotated” at some pivot unknown in advance. Example: [4,5,6,7,0,1,2]. Search for a target in O(log n) time by identifying which half is normally ordered.

function searchRotated(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    // Determine which half is sorted
    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}
// Example:
console.log(searchRotated([4,5,6,7,0,1,2], 0)); // 4

Explanation: We check which half is sorted (by comparing endpoints). If the target lies in the sorted half’s range, we binary-search there; otherwise, we search the other half. This preserves O(log n) performance.

Find First and Last Position of Element (Intermediate) – LeetCode 34: Given a sorted array, find the starting and ending positions of a given target. If not found, return [-1,-1]. This uses two binary searches: one for the first occurrence and one for the last.

function searchRange(nums, target) {
  function findBound(isFirst) {
    let left = 0, right = nums.length - 1, bound = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] === target) {
        bound = mid;
        if (isFirst) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return bound;
  }
  const first = findBound(true);
  if (first === -1) return [-1, -1];
  const last = findBound(false);
  return [first, last];
}
// Example:
console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

Explanation: We perform a binary search for the first occurrence (when we find the target, keep searching left) and another for the last occurrence (search right). This finds the range in O(log n) time overall.

DFS / Backtracking

Depth-First Search (DFS) / Backtracking explores possible solutions recursively, branching on choices and backtracking when needed. This pattern is common in generating combinations, permutations, subsets, and solving puzzles like word search.

Subsets (Power Set) (Beginner) – LeetCode 78: Given a set of distinct integers, return all possible subsets. For example, [1,2,3] yields [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]].
```
function subsets(nums) {
  const result = [];
  function dfs(index, path) {
    result.push([...path]);
    for (let i = index; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1, path);
      path.pop();
    }
  }
  dfs(0, []);
  return result;
}
// Example:
console.log(subsets([1,2,3]));
// [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
```
Explanation: We recursively decide to include or exclude each element. The dfs function generates all subsets by branching on each choice. We append the current subset (path) at each node of the recursion tree, and backtrack correctly.
Permutations (Intermediate) – LeetCode 46: Given a collection of distinct integers, return all possible permutations. For example, [1,2,3] yields the six permutations.
```
function permute(nums) {
  const result = [];
  function dfs(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let num of nums) {
      if (path.includes(num)) continue;
      path.push(num);
      dfs(path);
      path.pop();
    }
  }
  dfs([]);
  return result;
}
// Example:
console.log(permute([1,2,3]));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```
Explanation: We build permutations by choosing each unused number in turn (path.includes(num) checks usage). The recursion builds sequences and backtracks. Every full-length path is a valid permutation. This approach explores the permutation tree thoroughly.

Word Search (Intermediate) – LeetCode 79: Given a 2D board and a word, determine if the word exists in the grid moving horizontally or vertically (no letter reuse). Example: In the grid [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], the word "ABCCED" exists.

function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(r, c, i) {
    if (i === word.length) return true;
    if (r<0||c<0||r>=rows||c>=cols||board[r][c] !== word[i]) return false;
    const temp = board[r][c];
    board[r][c] = '#'; // mark visited
    const found = dfs(r+1,c,i+1) || dfs(r-1,c,i+1) ||
                  dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
    board[r][c] = temp;
    return found;
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}
// Example:
const board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
];
console.log(exist(board, "ABCCED")); // true

Explanation: We perform DFS from each grid cell that matches the first letter. At each step, we mark the cell as visited to avoid reuse and explore in all 4 directions for the next character. If a path spells the word, we return true. This is recursive backtracking on the 2D grid.

BFS

Breadth-First Search (BFS) processes nodes level by level and is ideal for shortest paths or minimum steps in unweighted graphs/grids. It uses a queue to explore neighbor nodes in order of distance from the start.

Binary Tree Level Order Traversal (Beginner) – LeetCode 102: Given a binary tree, return the level order traversal of its nodes’ values. For example, a tree [3,9,20,null,null,15,7] returns [[3],[9,20],[15,7]].
```
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}
```
Explanation: We use a queue to traverse each level of the tree. At each level, we dequeue all nodes, record their values, and enqueue their children. This processes the tree one level at a time (BFS on the tree).

Rotting Oranges (Intermediate) – LeetCode 994: Given an m x n grid with 0 (empty), 1 (fresh orange), and 2 (rotten orange), each minute any fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [];
  let fresh = 0;
  // Initialize queue with all rotten oranges and count fresh oranges
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r,c,0]);
      if (grid[r][c] === 1) fresh++;
    }
  }
  let minutes = 0, dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  // BFS spread the rot
  while (queue.length) {
    const [r,c,t] = queue.shift();
    minutes = Math.max(minutes, t);
    for (let [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr>=0 && nc>=0 && nr<rows && nc<cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr,nc,t+1]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}
// Example:
console.log(orangesRotting([
  [2,1,1],[1,1,0],[0,1,1]
])); // 4

Explanation: We first enqueue all initially rotten oranges with time 0 and count fresh ones. Then we perform BFS: each rotten orange rots its fresh neighbors in 1 minute (enqueue them with time+1). We track the elapsed minutes. If all fresh oranges eventually rot, we return the time; otherwise, return -1.

Word Ladder (Length of Shortest Transformation) (Intermediate) – LeetCode 127: Given two words (beginWord, endWord) and a dictionary wordList, find the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time and using only words in the dictionary. For example, ["hit","cog","dot","dog","lot","log","cog"] from "hit" to "cog" returns 5 (the path is “hit”→“hot”→“dot”→“dog”→“cog”).
```
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const queue = [[beginWord, 1]];
  while (queue.length) {
    const [word, steps] = queue.shift();
    if (word === endWord) return steps;
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const newWord = word.slice(0,i) + String.fromCharCode(c) + word.slice(i+1);
        if (wordSet.has(newWord)) {
          wordSet.delete(newWord);
          queue.push([newWord, steps+1]);
        }
      }
    }
  }
  return 0;
}
// Example:
console.log(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"])); // 5
```
Explanation: We use BFS starting from beginWord. At each step, we generate all one-letter transformations and enqueue those that are in the dictionary. We mark visited words by removing them from the set. The first time we reach endWord, the current BFS level (steps) is the shortest transformation length.

Dynamic Programming

Dynamic Programming (DP) solves problems with overlapping subproblems and optimal substructure by storing intermediate results. Common DP problems include counting or maximizing sequences with recurrence relations.

Climbing Stairs (Beginner) – GeeksforGeeks: There are n stairs and you can climb 1 or 2 steps at a time. Count distinct ways to reach the top. For example, n=4 has 5 ways. The recurrence is ways(n) = ways(n-1) + ways(n-2).
```
function climbStairs(n) {
  if (n <= 1) return 1;
  const dp = Array(n+1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}
// Example:
console.log(climbStairs(4)); // 5
```
Explanation: This is Fibonacci-like DP. We use an array dp where dp[i] = ways to reach step i. Each step can be reached from one step before (dp[i-1]) or two steps before (dp[i-2]), so dp[i] = dp[i-1] + dp[i-2]. This builds up the solution in O(n) time.
House Robber (Intermediate) – GeeksforGeeks: You have a row of houses with money; you cannot rob adjacent houses. Find the maximum amount you can steal. For example, [6,7,1,3,8,2,4] yields 19 (rob houses 1,3,5,7).
```
function rob(houses) {
  const n = houses.length;
  if (n === 0) return 0;
  if (n === 1) return houses[0];
  const dp = Array(n);
  dp[0] = houses[0];
  dp[1] = Math.max(houses[0], houses[1]);
  for (let i = 2; i < n; i++) {
    // Either skip current or rob it and add dp[i-2]
    dp[i] = Math.max(dp[i-1], houses[i] + dp[i-2]);
  }
  return dp[n-1];
}
// Example:
console.log(rob([6,7,1,3,8,2,4])); // 19
```
Explanation: We use DP where dp[i] = max loot up to house i. For each house, we decide to skip it (dp[i-1]) or rob it (houses[i] + dp[i-2]). The recurrence ensures we never rob adjacent houses. The answer is dp[n-1].
Coin Change (Min Coins) (Intermediate) – LeetCode 322: Given coin denominations and an amount, compute the fewest coins needed to make that amount, or -1 if impossible. For example, coins=[1,2,5], amount=11 returns 3 (5+5+1).
```
function coinChange(coins, amount) {
  const dp = Array(amount+1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i-coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Example:
console.log(coinChange([1,2,5], 11)); // 3
```
Explanation: We build a DP array where dp[i] = min coins to make amount i. For each coin and each amount i, we see if using that coin leads to a smaller count: dp[i] = min(dp[i], dp[i-coin] + 1). The final answer is dp[amount].

Greedy

Greedy algorithms build a solution step-by-step choosing the locally optimal option each time. It’s suitable when that choice leads to a globally optimal solution. Examples include interval scheduling, jump games, or change-making problems.

Jump Game (Beginner) – LeetCode 55: Given non-negative integers where each element represents max jump length, determine if you can reach the last index. For example, [2,3,1,1,4] returns true.
```
function canJump(nums) {
  let reach = 0;
  for (let i = 0; i <= reach && i < nums.length; i++) {
    reach = Math.max(reach, i + nums[i]);
    if (reach >= nums.length - 1) return true;
  }
  return false;
}
// Example:
console.log(canJump([2,3,1,1,4])); // true
```
Explanation: We keep track of the farthest index reach we can get to. As we iterate, if the current index i is reachable (i <= reach), we update reach = max(reach, i+nums[i]). If reach reaches the last index, return true. This greedy approach runs in O(n).
Gas Station (Intermediate) – LeetCode 134: Given two arrays gas and cost of equal length (circular route), find the starting station index from which you can complete the circuit with an empty tank initially, or -1 if impossible. For example, gas=[1,2,3,4,5], cost=[3,4,5,1,2] returns 3 (start at index 3).
```
function canCompleteCircuit(gas, cost) {
  let totalDiff = 0, fuel = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    totalDiff += diff;
    fuel += diff;
    if (fuel < 0) {
      // Cannot reach i+1 from current start; pick next as start
      start = i + 1;
      fuel = 0;
    }
  }
  return (totalDiff < 0) ? -1 : start;
}
// Example:
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3
```
Explanation: We accumulate fuel balance (gas[i]-cost[i]) along the route. If at any point the running sum fuel drops below 0, the start cannot be any index before i+1; we reset start = i+1 and continue. If the total gas ≥ total cost (totalDiff >= 0), a solution exists and start will be correct.
Lemonade Change (Intermediate) – LeetCode 860: Each lemonade costs $5. Customers pay with $5, $10, or $20 in order; determine if you can give change to everyone. Example: [5,5,5,10,20] returns true.
```
function lemonadeChange(bills) {
  let five = 0, ten = 0;
  for (let bill of bills) {
    if (bill === 5) {
      five++;
    } else if (bill === 10) {
      if (five === 0) return false;
      five--; ten++;
    } else { // 20
      // Prefer to give one 10 and one 5 as change
      if (ten > 0 && five > 0) {
        ten--; five--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
}
// Example:
console.log(lemonadeChange([5,5,5,10,20])); // true
```
Explanation: We track the count of $5 and $10 bills. For each customer, we try to give change using the largest bills first (greedy). If a $10 bill is available when needing change for $20, we use it and a $5; otherwise, we use three $5 bills. If we ever cannot give exact change, return false.

Topological Sort / Graph-Based

Topological sorting applies to Directed Acyclic Graphs (DAGs) to order nodes such that all prerequisites come before dependents. A common approach is Kahn’s algorithm (BFS on indegrees). This pattern is used in scheduling and dependency problems.

Course Schedule (I) (Beginner) – LeetCode 207: There are numCourses labeled 0…numCourses-1 and an array prerequisites of pairs [a,b] meaning to take course a you must have taken b. Determine if you can finish all courses.

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const indegree = Array(numCourses).fill(0);
  // Build graph and indegree count
  for (let [course, pre] of prerequisites) {
    graph[pre].push(course);
    indegree[course]++;
  }
  // Enqueue courses with no prerequisites
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }
  let visited = 0;
  while (queue.length) {
    const u = queue.shift();
    visited++;
    for (let v of graph[u]) {
      indegree[v]--;
      if (indegree[v] === 0) {
        queue.push(v);
      }
    }
  }
  return visited === numCourses;
}

Explanation: We interpret courses as graph nodes and prerequisites as directed edges. We use Kahn’s algorithm: compute indegrees, enqueue nodes with indegree 0, then remove them one by one (decrementing neighbors’ indegrees). If we can visit all courses (visited === numCourses), no cycle exists and scheduling is possible.

Course Schedule (II) (Intermediate) – LeetCode 210: Same setup as above, but return an order of courses. If impossible, return an empty array.

function findOrder(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const indegree = Array(numCourses).fill(0);
  for (let [course, pre] of prerequisites) {
    graph[pre].push(course);
    indegree[course]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (let v of graph[u]) {
      indegree[v]--;
      if (indegree[v] === 0) {
        queue.push(v);
      }
    }
  }
  return order.length === numCourses ? order : [];
}

Explanation: Similar to above, but we collect the nodes in the order we dequeue them. This yields a valid topological order of courses. If not all courses are visited (cycle), we return an empty list.

Alien Dictionary (Advanced) – LeetCode 269: Given a sorted list of words in an alien language, derive the order of letters. This also requires topological sorting of the character graph. (Omitted code for brevity; it involves building a graph of letter precedences and applying a similar BFS order.)

Each of the above patterns is illustrated by the chosen problems, demonstrating how and why the pattern applies to solve the problem efficiently.

Sources: Authoritative problem descriptions and solution outlines were used, including GeeksforGeeks and LeetCode explanations.