Drop in a LeetCode description, title, or problem # — we'll match it against your pattern library and suggest approaches.
Contiguous subarray/substring problems: max sum of size k, longest substring without repeats, minimum window substring.
pattern.js
1function slidingWindow(s, k) {
2 let left = 0;
3 let best = 0;
4 let windowState = new Map(); // or sum / count
5
6 for (let right = 0; right < s.length; right++) {
7 // expand: add s[right] to window
8
9 while (/* window invalid */) {
10 // shrink: remove s[left]
11 left++;
12 }
13
14 best = Math.max(best, right - left + 1);
15 }
16
17 return best;
18}Find length of longest substring with all unique chars.
Approach: Expand right; while duplicate exists, shrink left and drop chars from map.
Longest subarray of 1s if you can flip at most k zeros.
Approach: Track zero count in window; shrink while zeros > k.
Need O(1) lookups: anagrams, two-sum (unsorted), counting occurrences, first unique char, grouping.
pattern.js
1function frequencyCounter(nums) {
2 const freq = new Map();
3
4 for (const n of nums) {
5 freq.set(n, (freq.get(n) ?? 0) + 1);
6 }
7
8 for (const [key, count] of freq) {
9 // decide based on counts
10 }
11}Return indices where nums[i] + nums[j] === target.
Approach: Store value → index; for each x check if target - x was seen.
Group strings that are anagrams of each other.
Approach: Key by sorted string or 26-char frequency signature.
Sorted data, search space reduction, find boundary (first/last true), minimize/maximize with monotonic condition.
pattern.js
1function binarySearch(nums, target) {
2 let lo = 0;
3 let hi = nums.length - 1;
4
5 while (lo <= hi) {
6 const mid = lo + Math.floor((hi - lo) / 2);
7
8 if (nums[mid] === target) return mid;
9 if (nums[mid] < target) lo = mid + 1;
10 else hi = mid - 1;
11 }
12
13 return -1;
14}
15
16// On answer space (minimize maximum):
17function searchOnAnswer(min, max, canDo) {
18 let lo = min;
19 let hi = max;
20 let best = max;
21
22 while (lo <= hi) {
23 const mid = lo + Math.floor((hi - lo) / 2);
24 if (canDo(mid)) {
25 best = mid;
26 hi = mid - 1;
27 } else {
28 lo = mid + 1;
29 }
30 }
31
32 return best;
33}Find index where target belongs in sorted array.
Approach: Standard binary search; lo ends at insertion point when loop exits.
Minimize eating speed k to finish piles in h hours.
Approach: Binary search k; check feasibility with greedy pile simulation.
Shortest path in unweighted graphs, level-order traversal, multi-source spread (rotting oranges), minimum steps.
pattern.js
1function bfs(start, isTarget) {
2 const queue = [start];
3 const visited = new Set([key(start)]);
4 let steps = 0;
5
6 while (queue.length) {
7 const size = queue.length;
8
9 for (let i = 0; i < size; i++) {
10 const node = queue.shift();
11 if (isTarget(node)) return steps;
12
13 for (const next of neighbors(node)) {
14 const id = key(next);
15 if (!visited.has(id)) {
16 visited.add(id);
17 queue.push(next);
18 }
19 }
20 }
21
22 steps++;
23 }
24
25 return -1;
26}Return values grouped by depth.
Approach: Process queue level-by-level using snapshot size before shifting.
Shortest transformation sequence from beginWord to endWord.
Approach: BFS on words; try changing each char; use Set for dictionary lookup.
Explore all paths, tree recursion, connected components, backtracking, topological intuition on graphs.
pattern.js
1function dfs(node, visited) {
2 if (!node || visited.has(node)) return;
3
4 visited.add(node);
5 // process node
6
7 for (const next of neighbors(node)) {
8 dfs(next, visited);
9 }
10}
11
12// Tree variant
13function dfsTree(root) {
14 if (!root) return;
15
16 dfsTree(root.left);
17 dfsTree(root.right);
18 // or pre/in/post order processing
19}Count connected '1' regions in a grid.
Approach: For each unvisited land cell, DFS flood-fill and mark visited.
Return deepest node distance from root.
Approach: 1 + max(dfs(left), dfs(right)); base case null → 0.
Next greater/smaller element, daily temperatures, histogram largest rectangle, stock span problems.
pattern.js
1function nextGreater(nums) {
2 const stack = []; // indices, decreasing values
3 const result = Array(nums.length).fill(-1);
4
5 for (let i = 0; i < nums.length; i++) {
6 while (stack.length && nums[i] > nums[stack.at(-1)]) {
7 const idx = stack.pop();
8 result[idx] = nums[i];
9 }
10 stack.push(i);
11 }
12
13 return result;
14}Days until a warmer temperature.
Approach: Monotonic decreasing stack of indices; pop when current is warmer.
Max rectangular area under histogram bars.
Approach: Increasing stack; when bar is lower, compute area with popped bar as height.
K largest/smallest, merge K sorted lists, median stream, scheduling by priority, Dijkstra-like expansions.
pattern.js
1class MinHeap {
2 constructor() { this.data = []; }
3
4 push(val) {
5 this.data.push(val);
6 this.bubbleUp(this.data.length - 1);
7 }
8
9 pop() {
10 if (this.data.length === 1) return this.data.pop();
11 const top = this.data[0];
12 this.data[0] = this.data.pop();
13 this.bubbleDown(0);
14 return top;
15 }
16
17 peek() { return this.data[0]; }
18 size() { return this.data.length; }
19
20 bubbleUp(i) { /* ... */ }
21 bubbleDown(i) { /* ... */ }
22}
23
24// Top K largest: keep size-k min-heap
25function topKLargest(nums, k) {
26 const heap = new MinHeap();
27 for (const n of nums) {
28 heap.push(n);
29 if (heap.size() > k) heap.pop();
30 }
31 return heap.data;
32}Return the kth largest value (not kth distinct).
Approach: Size-k min-heap; root is kth largest after one pass.
Merge linked lists into one sorted list.
Approach: Min-heap of list heads; pop smallest, push that list's next node.
Optimal substructure with overlapping subproblems: climbing stairs, house robber, coin change, LIS, decode ways.
pattern.js
1function dp1d(n) {
2 const dp = Array(n + 1).fill(0);
3 dp[0] = baseCase0;
4 dp[1] = baseCase1;
5
6 for (let i = 2; i <= n; i++) {
7 dp[i] = Math.max(
8 dp[i - 1], // skip
9 dp[i - 2] + value(i) // take
10 );
11 }
12
13 return dp[n];
14}
15
16// Space optimized
17function dp1dOptimized(n) {
18 let prev2 = 0;
19 let prev1 = 1;
20
21 for (let i = 2; i <= n; i++) {
22 const curr = prev1 + prev2;
23 prev2 = prev1;
24 prev1 = curr;
25 }
26
27 return prev1;
28}Max money without robbing adjacent houses.
Approach: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Fewest coins to make amount (or -1).
Approach: dp[a] = min over coins of dp[a-coin] + 1; initialize infinity except dp[0]=0.
Generate combinations, permutations, subsets, sudoku, word search — explore choices and undo.
pattern.js
1function backtrack(path, choices, result) {
2 result.push([...path]);
3
4 for (let i = 0; i < choices.length; i++) {
5 path.push(choices[i]);
6 backtrack(path, choices.slice(i + 1), result);
7 path.pop(); // undo
8 }
9}
10
11// With pruning
12function backtrackPruned(path, start, nums, result) {
13 result.push([...path]);
14
15 for (let i = start; i < nums.length; i++) {
16 if (shouldSkip(i)) continue;
17 path.push(nums[i]);
18 backtrackPruned(path, i + 1, nums, result);
19 path.pop();
20 }
21}Return all possible subsets of distinct integers.
Approach: Include/exclude each element or use start index to avoid duplicates.
Combinations that sum to target (reuse allowed).
Approach: Same start index can be reused; stop when sum exceeds target.
Prefix/suffix lookups, autocomplete, word search on board, longest common prefix, dictionary of strings with shared prefixes.
pattern.js
1class TrieNode {
2 constructor() {
3 this.children = new Map();
4 this.isWord = false;
5 }
6}
7
8class Trie {
9 constructor() {
10 this.root = new TrieNode();
11 }
12
13 insert(word) {
14 let node = this.root;
15 for (const ch of word) {
16 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
17 node = node.children.get(ch);
18 }
19 node.isWord = true;
20 }
21
22 search(word) {
23 const node = this._walk(word);
24 return Boolean(node?.isWord);
25 }
26
27 startsWith(prefix) {
28 return Boolean(this._walk(prefix));
29 }
30
31 _walk(str) {
32 let node = this.root;
33 for (const ch of str) {
34 if (!node.children.has(ch)) return null;
35 node = node.children.get(ch);
36 }
37 return node;
38 }
39}Support insert, search exact word, and startsWith.
Approach: Each node holds char → child map; mark terminal nodes for full words.
Find all dictionary words on a letter grid.
Approach: Build trie from words; DFS grid while walking trie; prune dead branches.
Dynamic connectivity, count connected components, detect cycle in undirected graph, Kruskal MST, grouping by equivalence.
pattern.js
1class UnionFind {
2 constructor(n) {
3 this.parent = Array.from({ length: n }, (_, i) => i);
4 this.rank = Array(n).fill(0);
5 this.components = n;
6 }
7
8 find(x) {
9 if (this.parent[x] !== x) {
10 this.parent[x] = this.find(this.parent[x]); // path compression
11 }
12 return this.parent[x];
13 }
14
15 union(a, b) {
16 let ra = this.find(a);
17 let rb = this.find(b);
18 if (ra === rb) return false;
19
20 if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
21 this.parent[rb] = ra;
22 if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
23 this.components--;
24 return true;
25 }
26
27 connected(a, b) {
28 return this.find(a) === this.find(b);
29 }
30}Count components as edges are added online.
Approach: Start with n components; each successful union decrements count.
Find edge that creates a cycle in undirected graph.
Approach: Union nodes per edge; first union that fails (already connected) is redundant.
Shortest path with non-negative edge weights, cheapest flight with stops, network delay, path in weighted grid.
pattern.js
1function dijkstra(n, adj, src) {
2 const dist = Array(n).fill(Infinity);
3 dist[src] = 0;
4
5 const heap = new MinHeap(); // [cost, node]
6 heap.push([0, src]);
7
8 while (heap.size()) {
9 const [cost, u] = heap.pop();
10 if (cost > dist[u]) continue;
11
12 for (const [v, w] of adj[u]) {
13 const next = cost + w;
14 if (next < dist[v]) {
15 dist[v] = next;
16 heap.push([next, v]);
17 }
18 }
19 }
20
21 return dist;
22}Time for signal to reach all nodes from source k.
Approach: Dijkstra from k; answer is max distance or -1 if unreachable.
Cheapest price with at most k layovers.
Approach: Modified Dijkstra/BFS tracking (node, stops); relax only if stops <= k.
Task ordering with prerequisites, course schedule, alien dictionary, detect cycle in directed graph, build order.
pattern.js
1// Kahn's algorithm (BFS on indegree)
2function topoSortKahn(n, edges) {
3 const indeg = Array(n).fill(0);
4 const adj = Array.from({ length: n }, () => []);
5
6 for (const [u, v] of edges) {
7 adj[u].push(v);
8 indeg[v]++;
9 }
10
11 const queue = [];
12 for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
13
14 const order = [];
15 while (queue.length) {
16 const u = queue.shift();
17 order.push(u);
18 for (const v of adj[u]) {
19 if (--indeg[v] === 0) queue.push(v);
20 }
21 }
22
23 return order.length === n ? order : []; // empty => cycle
24}
25
26// DFS postorder variant
27function topoSortDFS(n, adj) {
28 const state = Array(n).fill(0); // 0=unseen 1=visiting 2=done
29 const order = [];
30
31 function dfs(u) {
32 state[u] = 1;
33 for (const v of adj[u]) {
34 if (state[v] === 1) return false; // cycle
35 if (state[v] === 0 && !dfs(v)) return false;
36 }
37 state[u] = 2;
38 order.push(u);
39 return true;
40 }
41
42 for (let i = 0; i < n; i++) {
43 if (state[i] === 0 && !dfs(i)) return [];
44 }
45
46 return order.reverse();
47}Can you finish all courses given prerequisites?
Approach: Cycle detection via Kahn or DFS; finishable iff valid topo order exists.
Return one valid order to take all courses.
Approach: Return Kahn order; if length < n, return [].
Optimal merging/bursting/partitioning on ranges, matrix chain multiplication, palindrome partitioning, burst balloons.
pattern.js
1function intervalDP(arr) {
2 const n = arr.length;
3 const dp = Array.from({ length: n }, () => Array(n).fill(0));
4
5 // length = window size
6 for (let len = 2; len <= n; len++) {
7 for (let i = 0; i + len - 1 < n; i++) {
8 const j = i + len - 1;
9 dp[i][j] = Infinity;
10
11 for (let k = i; k < j; k++) {
12 const cost = dp[i][k] + dp[k + 1][j] + mergeCost(i, k, j);
13 dp[i][j] = Math.min(dp[i][j], cost);
14 }
15 }
16 }
17
18 return dp[0][n - 1];
19}Max coins by bursting balloons; coins = left * current * right.
Approach: dp[i][j] = max over last balloon k in (i,j) of dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j].
Cut stick at given positions; cost = length of current stick per cut.
Approach: Sort cuts, pad with 0 and length, run interval DP on cut indices.
Sliding window maximum/minimum in O(n), constrained subarray with monotonic queue, jump game variants with range.
pattern.js
1function maxSlidingWindow(nums, k) {
2 const deque = []; // indices, decreasing values
3 const result = [];
4
5 for (let i = 0; i < nums.length; i++) {
6 while (deque.length && deque[0] <= i - k) deque.shift();
7 while (deque.length && nums[i] >= nums[deque.at(-1)]) deque.pop();
8
9 deque.push(i);
10 if (i >= k - 1) result.push(nums[deque[0]]);
11 }
12
13 return result;
14}Return max in each window of size k.
Approach: Monotonic deque stores useful indices; front is always current max.
Minimum length subarray sum >= k (may include negatives).
Approach: Prefix sums + deque of increasing indices to skip dominated prefixes.
Single number XOR tricks, count bits, power of two, subsets via bitmask, union of bitsets, finding missing/duplicate.
pattern.js
1// XOR cancels pairs
2function singleNumber(nums) {
3 return nums.reduce((acc, n) => acc ^ n, 0);
4}
5
6// i-th bit set?
7const isSet = (n, i) => ((n >> i) & 1) === 1;
8
9// turn on i-th bit
10const setBit = (n, i) => n | (1 << i);
11
12// count set bits
13function countBits(n) {
14 let count = 0;
15 while (n) {
16 n &= n - 1; // drop lowest set bit
17 count++;
18 }
19 return count;
20}
21
22// enumerate all subsets of n items
23for (let mask = 0; mask < 1 << n; mask++) {
24 // include nums[i] if isSet(mask, i)
25}Every element appears twice except one.
Approach: XOR all numbers; duplicates cancel to 0.
Return all subsets of distinct integers.
Approach: For mask 0..2^n-1, collect nums[i] where bit i is set.
Shortest path with negative edges, detect negative cycle, limited relax rounds (k+1 passes), currency arbitrage style.
pattern.js
1function bellmanFord(n, edges, src) {
2 const dist = Array(n).fill(Infinity);
3 dist[src] = 0;
4
5 for (let i = 0; i < n - 1; i++) {
6 let updated = false;
7 for (const [u, v, w] of edges) {
8 if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
9 dist[v] = dist[u] + w;
10 updated = true;
11 }
12 }
13 if (!updated) break;
14 }
15
16 // optional: one more pass detects negative cycle
17 for (const [u, v, w] of edges) {
18 if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
19 return { dist, hasNegativeCycle: true };
20 }
21 }
22
23 return { dist, hasNegativeCycle: false };
24}Cheapest price with at most k edges.
Approach: Run k+1 relaxation rounds (not full V-1); copy prev dist each round to avoid reusing same flight twice in one round.
Shortest paths when negative weights exist but no negative cycles.
Approach: Bellman-Ford from source; if extra round improves dist, negative cycle exists.
Design get/put O(1) with capacity eviction, cache with recency order, linked hash map pattern in interviews.
pattern.js
1class LRUCache {
2 constructor(capacity) {
3 this.cap = capacity;
4 this.map = new Map(); // key -> value, Map preserves insertion order
5 }
6
7 get(key) {
8 if (!this.map.has(key)) return -1;
9 const val = this.map.get(key);
10 this.map.delete(key);
11 this.map.set(key, val); // move to recent end
12 return val;
13 }
14
15 put(key, value) {
16 if (this.map.has(key)) this.map.delete(key);
17 this.map.set(key, value);
18 if (this.map.size > this.cap) {
19 const oldest = this.map.keys().next().value;
20 this.map.delete(oldest);
21 }
22 }
23}Implement get and put with O(1) and evict least recently used.
Approach: JS Map insertion order: delete+set on access; evict first key when over capacity.
Evict least frequently used; tie-break by recency.
Approach: Map key→{val,freq} + freq buckets as doubly-linked lists or nested Maps.
Find pattern in text in O(n+m), repeated substring checks, shortest palindrome by prefix, stream matching.
pattern.js
1function buildLPS(pattern) {
2 const lps = Array(pattern.length).fill(0);
3 let len = 0;
4 let i = 1;
5
6 while (i < pattern.length) {
7 if (pattern[i] === pattern[len]) {
8 lps[i++] = ++len;
9 } else if (len > 0) {
10 len = lps[len - 1];
11 } else {
12 lps[i++] = 0;
13 }
14 }
15
16 return lps;
17}
18
19function kmpSearch(text, pattern) {
20 const lps = buildLPS(pattern);
21 let i = 0;
22 let j = 0;
23
24 while (i < text.length) {
25 if (text[i] === pattern[j]) {
26 i++;
27 j++;
28 if (j === pattern.length) return i - j;
29 } else if (j > 0) {
30 j = lps[j - 1];
31 } else {
32 i++;
33 }
34 }
35
36 return -1;
37}Return first index of needle in haystack or -1.
Approach: Classic KMP with LPS to avoid re-checking matched prefix.
Can string be formed by repeating a substring?
Approach: Check if s is in (s+s).slice(1,-1) or use KMP on border length.
Meeting rooms, merge overlapping intervals, minimum arrows/points to cover intervals, skyline, scheduling conflicts.
pattern.js
1function mergeIntervals(intervals) {
2 intervals.sort((a, b) => a[0] - b[0]);
3 const merged = [];
4
5 for (const [start, end] of intervals) {
6 if (!merged.length || start > merged.at(-1)[1]) {
7 merged.push([start, end]);
8 } else {
9 merged.at(-1)[1] = Math.max(merged.at(-1)[1], end);
10 }
11 }
12
13 return merged;
14}
15
16// sweep with events
17function minMeetingRooms(intervals) {
18 const events = [];
19 for (const [s, e] of intervals) {
20 events.push([s, 1]);
21 events.push([e, -1]);
22 }
23 events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
24
25 let rooms = 0;
26 let maxRooms = 0;
27 for (const [, delta] of events) {
28 rooms += delta;
29 maxRooms = Math.max(maxRooms, rooms);
30 }
31 return maxRooms;
32}Merge all overlapping intervals.
Approach: Sort by start; extend last merged end if overlap.
Minimum conference rooms required.
Approach: Line sweep: +1 at start, -1 at end; track running max.
Pick the right sort for interviews: array size, stability needs, nearly sorted input, integer range, or in-place constraints.
pattern.js
1/*
2 Algorithm | Time (avg) | Time (worst) | Space | Stable | In-place
3 ---------------|--------------|--------------|--------|--------|----------
4 Bubble | O(n²) | O(n²) | O(1) | Yes | Yes
5 Insertion | O(n²) | O(n²) | O(1) | Yes | Yes
6 Selection | O(n²) | O(n²) | O(1) | No | Yes
7 Merge | O(n log n) | O(n log n) | O(n) | Yes | No
8 Quick | O(n log n) | O(n²) | O(log n)| No | Yes
9 Heap | O(n log n) | O(n log n) | O(1) | No | Yes
10 Counting | O(n + k) | O(n + k) | O(k) | Yes | No
11 Radix | O(d·(n+b)) | O(d·(n+b)) | O(n+b) | Yes | No
12 Bucket | O(n + k) avg | O(n²) worst | O(n) | Yes | No
13
14 JS: arr.sort((a, b) => a - b) // numeric ascending
15 arr.sort((a, b) => b - a) // numeric descending
16 arr.sort((a, b) => a.localeCompare(b)) // strings
17
18 Stable in modern JS (V8): sort is stable since ES2019.
19*/Sort nums ascending without built-in sort (interview variant).
Approach: Merge sort or quick sort for general case; mention O(n log n) lower bound for comparison sorts.
Input is almost sorted, n is small.
Approach: Insertion sort shines: O(n) best case when inversions are few.
Small n, teaching fundamentals, or insertion when data is nearly sorted. Rare as final answer for large n but good to know.
pattern.js
1// Bubble — swap adjacent out-of-order pairs
2function bubbleSort(arr) {
3 const a = [...arr];
4 for (let i = 0; i < a.length; i++) {
5 let swapped = false;
6 for (let j = 0; j < a.length - 1 - i; j++) {
7 if (a[j] > a[j + 1]) {
8 [a[j], a[j + 1]] = [a[j + 1], a[j]];
9 swapped = true;
10 }
11 }
12 if (!swapped) break; // early exit if sorted
13 }
14 return a;
15}
16
17// Insertion — grow sorted prefix
18function insertionSort(arr) {
19 const a = [...arr];
20 for (let i = 1; i < a.length; i++) {
21 let j = i;
22 while (j > 0 && a[j - 1] > a[j]) {
23 [a[j - 1], a[j]] = [a[j], a[j - 1]];
24 j--;
25 }
26 }
27 return a;
28}
29
30// Selection — pick min for each position
31function selectionSort(arr) {
32 const a = [...arr];
33 for (let i = 0; i < a.length; i++) {
34 let minIdx = i;
35 for (let j = i + 1; j < a.length; j++) {
36 if (a[j] < a[minIdx]) minIdx = j;
37 }
38 if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
39 }
40 return a;
41}Array with only a few elements out of place.
Approach: Each element moves left only as far as needed — linear when k inversions is small.
Same O(n²) but more swaps than insertion on average.
Approach: Mention insertion or move to O(n log n) instead unless n is tiny.
Guaranteed O(n log n), stable sort, linked lists, external sort, inversion count, merge step in problems (merge sorted arrays).
pattern.js
1function mergeSort(arr) {
2 if (arr.length <= 1) return arr;
3
4 const mid = Math.floor(arr.length / 2);
5 const left = mergeSort(arr.slice(0, mid));
6 const right = mergeSort(arr.slice(mid));
7
8 return merge(left, right);
9}
10
11function merge(left, right) {
12 const result = [];
13 let i = 0;
14 let j = 0;
15
16 while (i < left.length && j < right.length) {
17 if (left[i] <= right[j]) result.push(left[i++]);
18 else result.push(right[j++]);
19 }
20
21 return result.concat(left.slice(i), right.slice(j));
22}
23
24// In-place merge sort variant uses O(n) aux per level — prefer iterative bottom-up for linked listsMerge nums2 into nums1 in-place from the end.
Approach: Three pointers from rear; larger goes to end — no extra array needed.
For each index, count smaller elements to the right.
Approach: Merge sort with index tracking; count cross-inversions during merge.
Fast in-place average case, partition problems (Quickselect), Dutch flag variants, sort colors, kth largest.
pattern.js
1function quickSort(arr, lo = 0, hi = arr.length - 1) {
2 if (lo >= hi) return arr;
3
4 const p = partition(arr, lo, hi);
5 quickSort(arr, lo, p - 1);
6 quickSort(arr, p + 1, hi);
7 return arr;
8}
9
10function partition(arr, lo, hi) {
11 const pivot = arr[hi];
12 let i = lo;
13
14 for (let j = lo; j < hi; j++) {
15 if (arr[j] <= pivot) {
16 [arr[i], arr[j]] = [arr[j], arr[i]];
17 i++;
18 }
19 }
20
21 [arr[i], arr[hi]] = [arr[hi], arr[i]];
22 return i;
23}
24
25// Quickselect — kth smallest in average O(n)
26function quickSelect(nums, k) {
27 let lo = 0;
28 let hi = nums.length - 1;
29
30 while (lo <= hi) {
31 const p = partition(nums, lo, hi);
32 if (p === k) return nums[p];
33 if (p < k) lo = p + 1;
34 else hi = p - 1;
35 }
36}Find kth largest without full sort.
Approach: Quickselect on index n-k; average O(n), worst O(n²) — use random pivot or heap for safety.
Sort array of 0s, 1s, 2s in one pass.
Approach: Dutch national flag: three pointers (lt, i, gt) — 3-way partition.
In-place O(n log n) worst-case without merge's extra space, priority queue patterns, top-k, streaming median.
pattern.js
1function heapSort(arr) {
2 const n = arr.length;
3
4 // build max-heap
5 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6 heapify(arr, n, i);
7 }
8
9 for (let end = n - 1; end > 0; end--) {
10 [arr[0], arr[end]] = [arr[end], arr[0]];
11 heapify(arr, end, 0);
12 }
13
14 return arr;
15}
16
17function heapify(arr, size, i) {
18 let largest = i;
19 const left = 2 * i + 1;
20 const right = 2 * i + 2;
21
22 if (left < size && arr[left] > arr[largest]) largest = left;
23 if (right < size && arr[right] > arr[largest]) largest = right;
24
25 if (largest !== i) {
26 [arr[i], arr[largest]] = [arr[largest], arr[i]];
27 heapify(arr, size, largest);
28 }
29}Find top k frequent elements.
Approach: Size-k min-heap instead of sorting entire array — O(n log k).
Combine k sorted linked lists.
Approach: Min-heap of heads beats sorting all values when k is small.
Integers in bounded range, digits/fixed-width keys, non-comparison linear sorts when O(n log n) can be beaten.
pattern.js
1// Counting sort — keys in [0, k]
2function countingSort(arr, k) {
3 const count = Array(k + 1).fill(0);
4 for (const n of arr) count[n]++;
5
6 const out = [];
7 for (let val = 0; val <= k; val++) {
8 while (count[val]-- > 0) out.push(val);
9 }
10 return out;
11}
12
13// Radix sort — stable digit-by-digit (LSD)
14function radixSort(arr) {
15 const a = [...arr];
16 const max = Math.max(...a);
17 let exp = 1;
18
19 while (Math.floor(max / exp) > 0) {
20 a.sort((x, y) => ((x / exp) % 10) - ((y / exp) % 10)); // use counting per digit in production
21 exp *= 10;
22 }
23 return a;
24}
25
26// Bucket sort — distribute into buckets, sort each
27function bucketSort(arr, bucketCount = 5) {
28 const min = Math.min(...arr);
29 const max = Math.max(...arr);
30 const buckets = Array.from({ length: bucketCount }, () => []);
31
32 for (const n of arr) {
33 const idx = Math.floor(((n - min) / (max - min + 1)) * bucketCount);
34 buckets[Math.min(idx, bucketCount - 1)].push(n);
35 }
36
37 return buckets.flatMap((b) => b.sort((x, y) => x - y));
38}Sort by popcount then by value.
Approach: Custom comparator, or bucket into 32 buckets by bit count then concatenate.
Max difference between adjacent elements in sorted order in O(n).
Approach: Bucket/pigeonhole — max gap must be at least ceil((max-min)/n).
Sort 3 values (0/1/2), partition around pivot with duplicates, quick sort 3-way optimization, segregate odd/even.
pattern.js
1function sortColors(nums) {
2 let low = 0; // next 0 slot
3 let mid = 0; // current
4 let high = nums.length - 1; // next 2 slot
5
6 while (mid <= high) {
7 if (nums[mid] === 0) {
8 [nums[low], nums[mid]] = [nums[mid], nums[low]];
9 low++;
10 mid++;
11 } else if (nums[mid] === 1) {
12 mid++;
13 } else {
14 [nums[mid], nums[high]] = [nums[high], nums[mid]];
15 high--;
16 }
17 }
18}In-place sort of red(0), white(1), blue(2).
Approach: Three pointers: [0..low-1]=0, [low..mid-1]=1, [high+1..end]=2.
Move all 0s to end while keeping relative order of non-zeros.
Approach: Two-pointer write index — same spirit as flag partition for 0/non-0.