Problem-Solving Patterns
Most DSA problems are not unique — they are instances of one of ~15 recurring patterns. Learning to recognize the pattern is the hardest and most important skill. Once you see the pattern, the implementation becomes nearly mechanical. This page maps each pattern to its recognition cues and archetypal problems.
1. Two Pointers
When to use: sorted array, pair/triplet sum, palindrome check, remove duplicates.
// Two Sum II (sorted array) — O(n) time, O(1) space
function twoSum(numbers: number[], target: number): [number, number] {
let lo = 0, hi = numbers.length - 1;
while (lo < hi) {
const sum = numbers[lo] + numbers[hi];
if (sum === target) return [lo + 1, hi + 1];
if (sum < target) lo++;
else hi--;
}
return [-1, -1];
}2. Sliding Window
When to use: substring / subarray with constraint (max/min length, sum = k, at most k distinct chars).
// Longest substring without repeating characters — O(n) time, O(1) space
function lengthOfLongestSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let maxLen = 0, left = 0;
for (let right = 0; right < s.length; right++) {
if (lastSeen.has(s[right]) && lastSeen.get(s[right])! >= left) {
left = lastSeen.get(s[right])! + 1;
}
lastSeen.set(s[right], right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}3. Fast & Slow Pointers (Floyd's Cycle)
When to use: detect cycle in linked list, find cycle start, find middle of list, detect duplicate number.
// Linked list cycle detection
function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// Find cycle entry: after detection, reset slow to head, advance both by 1 — they meet at entry4. Merge Intervals
When to use: overlapping intervals, meeting rooms, calendar scheduling, range merging.
// Merge Intervals — O(n log n)
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const result: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
else result.push(intervals[i]);
}
return result;
}5. Cyclic Sort
When to use: array of n numbers in range [1..n] or [0..n]. Place each number at its correct index.
// Find all duplicates in array — O(n), O(1) extra space
function cyclicSort(nums: number[]): void {
let i = 0;
while (i < nums.length) {
const j = nums[i] - 1;
if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]];
else i++;
}
}6. In-Place Linked List Reversal
When to use: reverse a list or sublist, reverse every k elements, palindrome list check.
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}7. Tree BFS (Level Order)
When to use: level order traversal, min depth, connect level siblings, right side view.
function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const result: number[][] = [];
const queue: TreeNode[] = [root];
while (queue.length) {
const level: number[] = [];
const size = queue.length;
for (let i = 0; i < size; 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;
}8. Tree DFS
When to use: path sum, validate BST, max depth, lowest common ancestor, diameter of tree.
// Path sum — does root-to-leaf path summing to target exist?
function hasPathSum(root: TreeNode | null, target: number): boolean {
if (!root) return false;
if (!root.left && !root.right) return root.val === target;
return hasPathSum(root.left, target - root.val) ||
hasPathSum(root.right, target - root.val);
}9. Two Heaps (Median of Data Stream)
When to use: find median dynamically, split data into two halves, sliding window median.
Max-heap: holds lower half of numbers (top = lower median)
Min-heap: holds upper half of numbers (top = upper median)
Balance: sizes differ by at most 1
Median = top of larger heap, or average of both tops if equal size
10. Subsets / Power Set
When to use: generate all subsets, permutations, combinations, letter case permutations.
// All subsets — BFS approach
function subsets(nums: number[]): number[][] {
const result: number[][] = [[]];
for (const n of nums) {
const newSubsets = result.map(s => [...s, n]);
result.push(...newSubsets);
}
return result;
}
// [1,2,3] → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]11. Modified Binary Search
When to use: search in rotated/nearly sorted array, find first/last position, search in 2D matrix.
// Search in rotated sorted array
function searchRotated(nums: number[], target: number): number {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) { // left half is sorted
if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}12. Bitwise XOR
When to use: find unique element, missing number, pairs cancel each other out.
// Find two non-repeating elements — XOR all, split by differing bit
function singleNumberIII(nums: number[]): number[] {
const xorAll = nums.reduce((a, b) => a ^ b, 0);
const diffBit = xorAll & (-xorAll); // rightmost differing bit
let a = 0, b = 0;
for (const n of nums) {
if (n & diffBit) a ^= n;
else b ^= n;
}
return [a, b];
}13. Top K Elements
When to use: kth largest/smallest, k most frequent, k closest points.
// K most frequent elements using bucket sort — O(n)
function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [n, f] of freq) buckets[f].push(n);
const result: number[] = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
result.push(...buckets[i]);
}
return result.slice(0, k);
}14. K-Way Merge
When to use: merge k sorted lists/arrays, find smallest range covering k sorted lists.
Push first element of each list into a min-heap
Pop the minimum, add to result, push the next element from that list
Time: O(n log k) where n = total elements, k = number of lists
15. 0/1 Knapsack DP
When to use: subset sum, partition equal subset, target sum, count of subsets with given sum.
// Subset Sum — can we reach exactly target? O(n*target)
function canPartition(nums: number[]): boolean {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
const target = sum / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const n of nums) {
for (let j = target; j >= n; j--) {
dp[j] = dp[j] || dp[j - n];
}
}
return dp[target];
}Pattern Recognition Quick Guide
Cue in problem | Try this pattern |
|---|---|
Sorted array + pair/sum constraint | Two Pointers |
Contiguous subarray/substring with constraint | Sliding Window |
Linked list cycle / middle / kth from end | Fast & Slow Pointers |
Overlapping intervals, scheduling | Merge Intervals |
Array [1..n], find missing/duplicate | Cyclic Sort or XOR |
Reverse sublist / palindrome check | In-place Reversal |
Level-by-level tree processing | Tree BFS |
Root-to-leaf paths, DFS on tree | Tree DFS |
Running median, balance two halves | Two Heaps |
Generate all combinations/subsets | Subsets / Backtracking |
Binary search on answer / rotated array | Modified Binary Search |
Pair cancel, unique element, XOR | Bitwise XOR |
Kth largest/smallest, most frequent | Heap / Quick Select |
Merge k sorted structures | K-way Merge + Heap |
Choose or skip items, sum = target | 0/1 Knapsack DP |