⌕ /
Coding Interview Preparation

Recognize the pattern.
Recall the template.

Nearly every array / string / tree / graph interview question is one of sixteen recurring shapes. You don't memorize solutions — you learn to spot the pattern from the prompt and reach for its skeleton. This manual is built for that: the trigger phrases that name each pattern, the one template that solves its whole family, the canonical problems to drill, and its complexity.

16 patterns 90+ problems 1 template each code in JavaScript ✓ mirrored to runnable files

How to use this

1 · Decode

Read the prompt for signals

Map the question to a pattern using the recognition table below. 80% of the battle is choosing the right shape in the first minute.

2 · Recall

Type the skeleton

Each pattern has one template. Internalize it until it flows from muscle memory, then adapt the condition inside the loop.

3 · Drill

Solve the family

Do the easy anchor, then the variations — same template, different check. Mark a pattern studied to track progress.

4 · Deliver

Always state complexity

Close every answer with time & space. It's expected, and it proves you know why the pattern beats brute force.

Pattern recognition — the prompt decoder

The one skill that gets you hired: translate what the interviewer says into which pattern you reach for. Scan this table whenever you're stuck.
When the prompt says…Reach for
Contiguous subarray/substring, "size k", longest/shortest window, "at most K distinct"Sliding Window
Input is sorted; find a pair/triplet/quad sum; remove/dedupe in place; both endsTwo Pointers
LinkedList/sequence + cycle, "does it loop", find middle, palindrome list, happy numberFast & Slow Pointers
intervals, "overlap", "merge", meetings, rooms, appointments, CPU loadMerge Intervals
Array of n numbers in [1..n]/[0..n]; missing / duplicate / corrupt; "O(n), no extra space"Cyclic Sort
"Reverse" a list or sub-list, "in-place", reverse in groups of k, rotateIn-place Reversal
Tree, "level by level", level order, min depth, right/left view, connect siblings, zigzagTree BFS
Tree, "root-to-leaf path", path sum/sequence, count paths, diameter, max path sumTree DFS
Median of a stream / window; "smallest in one part & largest in the other"; profit schedulingTwo Heaps
"Find all subsets / permutations / combinations", generate parentheses, abbreviationsSubsets
Sorted + "find element / index / ceiling / next", rotated sorted, "O(log n)"Modified Binary Search
"Every number appears twice except…", missing number without overflow, complement, bit flipsBitwise XOR
"Top / K largest / K smallest / K most frequent", "K closest", running Kth largestTop 'K' Elements
"Merge K sorted lists/arrays", "Kth smallest across M lists", smallest covering rangeK-way Merge
Choose a subset under a capacity/target, equal partition, "can we make sum S", count ways0/1 Knapsack (DP)
Dependencies / prerequisites, "can all finish", build an order, cycle in a digraph, alien dictionaryTopological Sort

The Patterns

PATTERN 01

Sliding Window

Compute over every contiguous window without recomputing the overlap. Expand with the right edge; when it violates a constraint, shrink from the left. Turns O(N·K) brute force into O(N).

How it works
Recognize it when
contiguous subarraysubstringwindow of size klongest / shortestat most K distinctmax / min sum
Key move: keep a running aggregate (sum, frequency map). Each step add the incoming windowEnd element; while the window is invalid, subtract the outgoing windowStart element and advance start.
dynamic window · template
let windowStart = 0, best = 0;
const freq = {};
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
  const right = s[windowEnd];
  freq[right] = (freq[right] || 0) + 1;      // grow window
  while (/* window is invalid */ Object.keys(freq).length > K) {
    const left = s[windowStart];
    freq[left]--;                            // shrink from left
    if (freq[left] === 0) delete freq[left];
    windowStart++;
  }
  best = Math.max(best, windowEnd - windowStart + 1);
}
return best;
Drill these
easy
Maximum Sum Subarray of Size KFixed window: add right, at size k record max, subtract left.
▸
solution · patterns/01-sliding-window.js
function maxSubarraySumOfSizeK(arr, k) {
  let windowSum = 0, windowStart = 0, maxSum = 0;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    windowSum += arr[windowEnd];
    if (windowEnd >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[windowStart++];
    }
  }
  return maxSum;
}
easy
Smallest Subarray with Sum ≥ SVariable window: shrink while sum ≥ S, track min length.
▸
solution · patterns/01-sliding-window.js
function smallestSubarrayWithSum(arr, s) {
  let windowSum = 0, windowStart = 0, minLen = Infinity;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    windowSum += arr[windowEnd];
    while (windowSum >= s) {
      minLen = Math.min(minLen, windowEnd - windowStart + 1);
      windowSum -= arr[windowStart++];
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
med
Longest Substring with K DistinctShrink while map size > K. Fruits-into-Baskets is this with K=2.
▸
solution · patterns/01-sliding-window.js
function longestSubstringKDistinct(str, k) {
  let windowStart = 0, maxLen = 0;
  const freq = {};
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    freq[right] = (freq[right] || 0) + 1;
    while (Object.keys(freq).length > k) {
      const left = str[windowStart++];
      if (--freq[left] === 0) delete freq[left];
    }
    maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
  }
  return maxLen;
}

function fruitsIntoBaskets(fruits) {
  return longestSubstringKDistinct(fruits.join(''), 2);
}
hard
No-repeat SubstringMap char → last index; jump start to max(start, last+1).
▸
solution · patterns/01-sliding-window.js
function longestNoRepeatSubstring(str) {
  let windowStart = 0, maxLen = 0;
  const lastIndex = {};
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    if (right in lastIndex) {
      windowStart = Math.max(windowStart, lastIndex[right] + 1);
    }
    lastIndex[right] = windowEnd;
    maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
  }
  return maxLen;
}
hard
Longest Substring after K ReplacementsTrack maxRepeat; shrink when windowLen − maxRepeat > k.
▸
solution · patterns/01-sliding-window.js
function longestSubstringAfterReplacement(str, k) {
  let windowStart = 0, maxLen = 0, maxRepeat = 0;
  const freq = {};
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    freq[right] = (freq[right] || 0) + 1;
    maxRepeat = Math.max(maxRepeat, freq[right]);
    // window size - most-frequent-letter count = letters we must replace
    if (windowEnd - windowStart + 1 - maxRepeat > k) {
      freq[str[windowStart++]]--;
    }
    maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
  }
  return maxLen;
}

function longestOnesAfterReplacement(arr, k) {
  let windowStart = 0, maxLen = 0, maxOnes = 0;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    if (arr[windowEnd] === 1) maxOnes++;
    if (windowEnd - windowStart + 1 - maxOnes > k) {
      if (arr[windowStart++] === 1) maxOnes--;
    }
    maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
  }
  return maxLen;
}
hard
Permutation · Anagrams · Min Window SubstringPattern frequency map + matched counter.
▸
solution · patterns/01-sliding-window.js
function findPermutation(str, pattern) {
  const need = {};
  for (const c of pattern) need[c] = (need[c] || 0) + 1;
  let windowStart = 0, matched = 0;
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    if (right in need && --need[right] === 0) matched++;
    if (matched === Object.keys(need).length) return true;
    if (windowEnd >= pattern.length - 1) {
      const left = str[windowStart++];
      if (left in need && need[left]++ === 0) matched--;
    }
  }
  return false;
}

function findAnagrams(str, pattern) {
  const need = {};
  for (const c of pattern) need[c] = (need[c] || 0) + 1;
  const result = [];
  let windowStart = 0, matched = 0;
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    if (right in need && --need[right] === 0) matched++;
    if (matched === Object.keys(need).length) result.push(windowStart);
    if (windowEnd >= pattern.length - 1) {
      const left = str[windowStart++];
      if (left in need && need[left]++ === 0) matched--;
    }
  }
  return result;
}

function minWindowSubstring(str, pattern) {
  const need = {};
  for (const c of pattern) need[c] = (need[c] || 0) + 1;
  let windowStart = 0, matched = 0, minLen = Infinity, subStart = 0;
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
    const right = str[windowEnd];
    if (right in need && --need[right] >= 0) matched++;
    while (matched === pattern.length) {
      if (windowEnd - windowStart + 1 < minLen) {
        minLen = windowEnd - windowStart + 1;
        subStart = windowStart;
      }
      const left = str[windowStart++];
      if (left in need && need[left]++ === 0) matched--;
    }
  }
  return minLen === Infinity ? '' : str.substring(subStart, subStart + minLen);
}
Time O(N)
Space O(1)/O(K)
PATTERN 02

Two Pointers

On sorted data, walk two indices instead of nesting loops. Converge from both ends toward a target, or use a slow "write" pointer and a fast "read" pointer for in-place work.

How it works
Recognize it when
sorted arraypair / triplet / quad sumtarget sumremove in placeboth endsO(1) space
Key move: if arr[start]+arr[end] is too small, start++; too big, end--. For triplets, sort then fix i and two-pointer the rest — always skip duplicates.
converging pointers · template
arr.sort((a, b) => a - b);
let start = 0, end = arr.length - 1;
while (start < end) {
  const sum = arr[start] + arr[end];
  if (sum === target) return [start, end];
  if (sum < target) start++;   // need bigger
  else end--;                   // need smaller
}
Drill these
easy
Pair with Target Sum (sorted Two Sum)The base case. Unsorted → use a hash map instead.
▸
solution · patterns/02-two-pointers.js
function pairWithTargetSum(arr, target) {
  let start = 0, end = arr.length - 1;
  while (start < end) {
    const sum = arr[start] + arr[end];
    if (sum === target) return [start, end];
    if (sum < target) start++;
    else end--;
  }
  return [-1, -1];
}
easy
Remove Duplicates · Squaring a Sorted ArraySlow write-pointer; or fill from the back, largest-square-wins.
▸
solution · patterns/02-two-pointers.js
function removeDuplicates(arr) {
  let nextNonDup = 1;
  for (let i = 1; i < arr.length; i++) {
    if (arr[nextNonDup - 1] !== arr[i]) arr[nextNonDup++] = arr[i];
  }
  return nextNonDup;
}

function makeSquares(arr) {
  const n = arr.length;
  const squares = new Array(n).fill(0);
  let start = 0, end = n - 1, pos = n - 1;
  while (start <= end) {
    const a = arr[start] * arr[start];
    const b = arr[end] * arr[end];
    if (a > b) { squares[pos--] = a; start++; }
    else { squares[pos--] = b; end--; }
  }
  return squares;
}
med
Triplet Sum to Zero (3Sum) & variantsFix i, two-pointer for −arr[i]. Closest & count-smaller reuse this.
▸
solution · patterns/02-two-pointers.js
function tripletSumToZero(arr) {
  arr.sort((a, b) => a - b);
  const triplets = [];
  for (let i = 0; i < arr.length - 2; i++) {
    if (i > 0 && arr[i] === arr[i - 1]) continue; // skip duplicate anchors
    let start = i + 1, end = arr.length - 1;
    while (start < end) {
      const sum = arr[i] + arr[start] + arr[end];
      if (sum === 0) {
        triplets.push([arr[i], arr[start], arr[end]]);
        start++; end--;
        while (start < end && arr[start] === arr[start - 1]) start++;
        while (start < end && arr[end] === arr[end + 1]) end--;
      } else if (sum < 0) start++;
      else end--;
    }
  }
  return triplets;
}

function tripletSumCloseToTarget(arr, target) {
  arr.sort((a, b) => a - b);
  let smallestDiff = Infinity;
  for (let i = 0; i < arr.length - 2; i++) {
    let start = i + 1, end = arr.length - 1;
    while (start < end) {
      const diff = target - arr[i] - arr[start] - arr[end];
      if (diff === 0) return target;
      if (Math.abs(diff) < Math.abs(smallestDiff) ||
          (Math.abs(diff) === Math.abs(smallestDiff) && diff > smallestDiff)) {
        smallestDiff = diff;
      }
      if (diff > 0) start++; else end--;
    }
  }
  return target - smallestDiff;
}

function tripletsWithSmallerSum(arr, target) {
  arr.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < arr.length - 2; i++) {
    let start = i + 1, end = arr.length - 1;
    while (start < end) {
      if (arr[i] + arr[start] + arr[end] < target) {
        count += end - start; // every element between start..end also works
        start++;
      } else end--;
    }
  }
  return count;
}

function subarraysWithProductLessThan(arr, target) {
  let product = 1, start = 0, count = 0;
  for (let end = 0; end < arr.length; end++) {
    product *= arr[end];
    while (product >= target && start <= end) product /= arr[start++];
    count += end - start + 1; // subarrays ending at `end`
  }
  return count;
}
med
Dutch National Flag (0s/1s/2s)low / i / high; 0s to front, 2s to back in one pass.
▸
solution · patterns/02-two-pointers.js
function dutchFlagSort(arr) {
  let low = 0, high = arr.length - 1, i = 0;
  while (i <= high) {
    if (arr[i] === 0) { [arr[i], arr[low]] = [arr[low], arr[i]]; i++; low++; }
    else if (arr[i] === 1) i++;
    else { [arr[i], arr[high]] = [arr[high], arr[i]]; high--; }
  }
  return arr;
}
med
4Sum · Backspace Compare · Min Window SortQuads = two fixes + two pointers; backspace compares from the end.
▸
solution · patterns/02-two-pointers.js
function quadrupleSumToTarget(arr, target) {
  arr.sort((a, b) => a - b);
  const quads = [];
  for (let i = 0; i < arr.length - 3; i++) {
    if (i > 0 && arr[i] === arr[i - 1]) continue;
    for (let j = i + 1; j < arr.length - 2; j++) {
      if (j > i + 1 && arr[j] === arr[j - 1]) continue;
      let start = j + 1, end = arr.length - 1;
      while (start < end) {
        const sum = arr[i] + arr[j] + arr[start] + arr[end];
        if (sum === target) {
          quads.push([arr[i], arr[j], arr[start], arr[end]]);
          start++; end--;
          while (start < end && arr[start] === arr[start - 1]) start++;
          while (start < end && arr[end] === arr[end + 1]) end--;
        } else if (sum < target) start++;
        else end--;
      }
    }
  }
  return quads;
}

function backspaceCompare(str1, str2) {
  const nextValid = (str, index) => {
    let backspaces = 0;
    while (index >= 0) {
      if (str[index] === '#') backspaces++;
      else if (backspaces > 0) backspaces--;
      else break;
      index--;
    }
    return index;
  };
  let i = str1.length - 1, j = str2.length - 1;
  while (i >= 0 || j >= 0) {
    i = nextValid(str1, i);
    j = nextValid(str2, j);
    if (i < 0 && j < 0) return true;
    if (i < 0 || j < 0) return false;
    if (str1[i] !== str2[j]) return false;
    i--; j--;
  }
  return true;
}

function minWindowSort(arr) {
  let low = 0, high = arr.length - 1;
  while (low < arr.length - 1 && arr[low] <= arr[low + 1]) low++;
  if (low === arr.length - 1) return 0; // already sorted
  while (high > 0 && arr[high] >= arr[high - 1]) high--;
  let subMax = -Infinity, subMin = Infinity;
  for (let k = low; k <= high; k++) {
    subMax = Math.max(subMax, arr[k]);
    subMin = Math.min(subMin, arr[k]);
  }
  while (low > 0 && arr[low - 1] > subMin) low--;
  while (high < arr.length - 1 && arr[high + 1] < subMax) high++;
  return high - low + 1;
}
Pair O(N)
Triplet O(N²)
Quad O(N³)
Space O(1)
PATTERN 03

Fast & Slow Pointers

Two pointers move at different speeds (hare & tortoise). If a cycle exists, the fast pointer laps the slow one and they meet — all in O(1) space.

How it works
Recognize it when
linked list cycledoes it loop?find the middlepalindrome listhappy number
Why it works: in a loop the gap shrinks by one each step, so collision is guaranteed. To find the cycle start: measure length K, advance one pointer K nodes, then move both together.
cycle detection · template
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
  slow = slow.next;             // 1 step
  fast = fast.next.next;        // 2 steps
  if (slow === fast) return true;   // met → cycle
}
return false;                     // fast hit the end → no cycle
Drill these
easy
LinkedList Cycle · Middle of the LinkedListWhen fast reaches the end, slow sits on the middle.
▸
solution · patterns/03-fast-slow-pointers.js
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function middleOfList(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}
med
Start of LinkedList CycleLength K, then two pointers K apart meet at the entry.
▸
solution · patterns/03-fast-slow-pointers.js
function cycleLength(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let cur = slow, len = 0;
      do { cur = cur.next; len++; } while (cur !== slow);
      return len;
    }
  }
  return 0;
}

function findCycleStart(head) {
  const len = cycleLength(head);
  if (len === 0) return null;
  let p1 = head, p2 = head;
  for (let i = 0; i < len; i++) p2 = p2.next; // move p2 ahead by cycle length
  while (p1 !== p2) { p1 = p1.next; p2 = p2.next; }
  return p1;
}
med
Happy Number"Sum of squared digits" is a sequence; unhappy numbers cycle without hitting 1.
▸
solution · patterns/03-fast-slow-pointers.js
function isHappyNumber(num) {
  const squareSum = (n) => {
    let sum = 0;
    while (n > 0) { const d = n % 10; sum += d * d; n = Math.floor(n / 10); }
    return sum;
  };
  let slow = num, fast = num;
  do {
    slow = squareSum(slow);
    fast = squareSum(squareSum(fast));
  } while (slow !== fast);
  return slow === 1;
}
med
Palindrome LinkedList · Rearrange LinkedListFind middle, reverse the second half, compare / interleave.
▸
solution · patterns/03-fast-slow-pointers.js
function reverse(head) {
  let prev = null, cur = head;
  while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }
  return prev;
}

function isPalindromicList(head) {
  if (!head || !head.next) return true;
  // find middle
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  // reverse second half
  let secondHead = reverse(slow);
  const copy = secondHead;
  let p1 = head, p2 = secondHead, isPalindrome = true;
  while (p1 && p2) {
    if (p1.value !== p2.value) { isPalindrome = false; break; }
    p1 = p1.next; p2 = p2.next;
  }
  reverse(copy); // restore
  return isPalindrome;
}

function reorderList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let second = reverse(slow);
  let first = head;
  while (first && second) {
    let tmp = first.next; first.next = second; first = tmp;
    tmp = second.next; second.next = first; second = tmp;
  }
  if (first) first.next = null;
  return head;
}
Time O(N)
Space O(1)
PATTERN 04

Merge Intervals

Anything about overlapping ranges. Sort by start, then sweep once: intervals overlap when the next start ≤ current end. A min-heap on end-times handles "how many at once".

How it works
Recognize it when
intervalsoverlapmergemeeting roomsappointmentsfree time
Six overlap cases collapse to one test: after sorting by start, b.start ≤ a.end means overlap — merge into [a.start, max(a.end, b.end)]. For concurrency counting, track the smallest end-time in a min-heap.
merge overlapping · template
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
let [start, end] = intervals[0];
for (let i = 1; i < intervals.length; i++) {
  const [s, e] = intervals[i];
  if (s <= end) end = Math.max(end, e);   // overlap → extend
  else { merged.push([start, end]); [start, end] = [s, e]; }
}
merged.push([start, end]);
return merged;
Drill these
med
Merge Intervals · Insert IntervalInsert: skip those ending before the new start, merge the overlapping run, append the rest.
▸
solution · patterns/04-merge-intervals.js
function mergeIntervals(intervals) {
  if (intervals.length < 2) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  let [start, end] = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    const [s, e] = intervals[i];
    if (s <= end) end = Math.max(end, e); // overlap -> extend
    else { merged.push([start, end]); [start, end] = [s, e]; }
  }
  merged.push([start, end]);
  return merged;
}

function insertInterval(intervals, newInterval) {
  const merged = [];
  let i = 0, [ns, ne] = newInterval;
  while (i < intervals.length && intervals[i][1] < ns) merged.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= ne) {
    ns = Math.min(ns, intervals[i][0]);
    ne = Math.max(ne, intervals[i][1]);
    i++;
  }
  merged.push([ns, ne]);
  while (i < intervals.length) merged.push(intervals[i++]);
  return merged;
}
med
Intervals IntersectionOverlap = [max(starts), min(ends)]; advance whichever ends first.
▸
solution · patterns/04-merge-intervals.js
function intervalsIntersection(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    const start = Math.max(a[i][0], b[j][0]);
    const end = Math.min(a[i][1], b[j][1]);
    if (start <= end) result.push([start, end]);
    if (a[i][1] < b[j][1]) i++; else j++;
  }
  return result;
}
med
Conflicting AppointmentsSort, then any start < prevEnd is a conflict.
▸
solution · patterns/04-merge-intervals.js
function canAttendAll(appointments) {
  appointments.sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < appointments.length; i++) {
    if (appointments[i][0] < appointments[i - 1][1]) return false;
  }
  return true;
}
hard
Minimum Meeting Rooms · Max CPU LoadMin-heap of end times; heap size = rooms / concurrent load.
▸
solution · patterns/04-merge-intervals.js
function minMeetingRooms(meetings) {
  if (meetings.length === 0) return 0;
  meetings.sort((a, b) => a[0] - b[0]);
  const endTimes = MinHeap(); // heap of end times of active meetings
  let maxRooms = 0;
  for (const [start, end] of meetings) {
    while (!endTimes.isEmpty() && endTimes.peek() <= start) endTimes.pop();
    endTimes.push(end);
    maxRooms = Math.max(maxRooms, endTimes.size());
  }
  return maxRooms;
}

function maxCPULoad(jobs) {
  jobs.sort((a, b) => a[0] - b[0]);
  const heap = MinHeap((x, y) => x[1] - y[1]); // by end time
  let current = 0, max = 0;
  for (const job of jobs) {
    while (!heap.isEmpty() && heap.peek()[1] <= job[0]) current -= heap.pop()[2];
    heap.push(job);
    current += job[2];
    max = Math.max(max, current);
  }
  return max;
}
hard
Employee Free TimeMerge all intervals; the gaps between blocks are the free time.
▸
solution · patterns/04-merge-intervals.js
function employeeFreeTime(schedules) {
  const all = [];
  for (const emp of schedules) for (const iv of emp) all.push(iv);
  all.sort((a, b) => a[0] - b[0]);
  const free = [];
  let end = all[0][1];
  for (let i = 1; i < all.length; i++) {
    if (all[i][0] > end) { free.push([end, all[i][0]]); end = all[i][1]; }
    else end = Math.max(end, all[i][1]);
  }
  return free;
}
Time O(N log N)
Space O(N)
PATTERN 05

Cyclic Sort

When numbers live in a known range [1..n], each value has a natural home index. Swap each value to value − 1 in one pass; whatever is out of place afterward reveals the missing/duplicate number.

How it works
Recognize it when
numbers in range 1..nmissing numberduplicateO(n) timeno extra space
Key move: don't advance i after a swap — the value you just received may also be misplaced. Advance only when index i already holds its correct value.
place each number · template
let i = 0;
while (i < nums.length) {
  const j = nums[i] - 1;                 // correct home for nums[i]
  if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]];
  else i++;
}
// first index where nums[i] !== i+1 is the answer
for (i = 0; i < nums.length; i++) if (nums[i] !== i + 1) return i + 1;
Drill these
easy
Cyclic Sort · Find the Missing NumberRange 0..n → compare nums[i] to index i.
▸
solution · patterns/05-cyclic-sort.js
function cyclicSort(nums) {
  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++;
  }
  return nums;
}

function findMissingNumber(nums) {
  let i = 0;
  const n = nums.length;
  while (i < n) {
    const j = nums[i];
    if (nums[i] < n && nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]];
    else i++;
  }
  for (i = 0; i < n; i++) if (nums[i] !== i) return i;
  return n;
}
easy
Find All Missing / All Duplicate NumbersEvery nums[i] !== i+1 flags a missing (index) or duplicate (value).
▸
solution · patterns/05-cyclic-sort.js
function findAllMissingNumbers(nums) {
  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++;
  }
  const missing = [];
  for (i = 0; i < nums.length; i++) if (nums[i] !== i + 1) missing.push(i + 1);
  return missing;
}

function findAllDuplicates(nums) {
  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++;
  }
  const dups = [];
  for (i = 0; i < nums.length; i++) if (nums[i] !== i + 1) dups.push(nums[i]);
  return dups.sort((a, b) => a - b);
}
easy
Find the Duplicate · Find the Corrupt PairDuplicate also findable via fast/slow treating values as links.
▸
solution · patterns/05-cyclic-sort.js
function findDuplicate(nums) {
  let i = 0;
  while (i < nums.length) {
    if (nums[i] !== i + 1) {
      const j = nums[i] - 1;
      if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]];
      else return nums[i]; // both slots equal -> duplicate
    } else i++;
  }
  return -1;
}

function findCorruptPair(nums) {
  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++;
  }
  for (i = 0; i < nums.length; i++) if (nums[i] !== i + 1) return [nums[i], i + 1];
  return [-1, -1];
}
med
Smallest Missing PositiveIgnore values ≤ 0 or > n; first unfilled index is the answer.
▸
solution · patterns/05-cyclic-sort.js
function firstMissingPositive(nums) {
  let i = 0;
  const n = nums.length;
  while (i < n) {
    const j = nums[i] - 1;
    if (nums[i] > 0 && nums[i] <= n && nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else i++;
  }
  for (i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}
hard
First K Missing Positive NumbersCollect missing indices, extend past n while skipping seen extras.
▸
solution · patterns/05-cyclic-sort.js
function firstKMissingPositive(nums, k) {
  const n = nums.length;
  let i = 0;
  while (i < n) {
    const j = nums[i] - 1;
    if (nums[i] > 0 && nums[i] <= n && nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else i++;
  }
  const missing = [];
  const extras = new Set();
  for (i = 0; i < n && missing.length < k; i++) {
    if (nums[i] !== i + 1) { missing.push(i + 1); extras.add(nums[i]); }
  }
  let candidate = n + 1;
  while (missing.length < k) {
    if (!extras.has(candidate)) missing.push(candidate);
    candidate++;
  }
  return missing;
}
Time O(n)
Space O(1)
PATTERN 06

In-place Reversal of a LinkedList

Reverse the links of a list (or a slice) by re-pointing each node backward as you walk, using three pointers and no extra memory.

How it works
Recognize it when
reverse a linked listreverse sub-listin placereverse in groups of krotate list
Key move: cache next before overwriting current.next. For sub-lists, remember the node before the reversed part and the node that becomes its new tail, then stitch back.
reverse links · template
let current = head, previous = null;
while (current !== null) {
  const next = current.next;   // cache before we clobber it
  current.next = previous;     // flip the link
  previous = current;          // advance the trail
  current = next;
}
return previous;               // new head
Drill these
easy
Reverse a LinkedListThe base three-pointer walk.
▸
solution · patterns/06-linkedlist-reversal.js
function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}
med
Reverse a Sub-list (p → q)Skip to p, reverse q−p+1 nodes, reconnect boundaries.
▸
solution · patterns/06-linkedlist-reversal.js
function reverseSubList(head, p, q) {
  if (p === q) return head;
  let cur = head, prev = null, i = 1;
  while (cur && i < p) { prev = cur; cur = cur.next; i++; }
  const lastOfFirst = prev;      // node before the sub-list
  const lastOfSub = cur;         // becomes the tail of the reversed sub-list
  let next = null;
  i = 0;
  while (cur && i < q - p + 1) {
    next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
    i++;
  }
  if (lastOfFirst) lastOfFirst.next = prev; else head = prev;
  lastOfSub.next = cur;          // connect to the remainder
  return head;
}
med
Reverse every K-element Sub-listLoop the sub-list reversal; connect each block to the previous.
▸
solution · patterns/06-linkedlist-reversal.js
function reverseEveryKElements(head, k) {
  if (k <= 1 || !head) return head;
  let cur = head, prev = null;
  while (true) {
    const lastOfPrev = prev;
    const lastOfSub = cur;
    let next = null, i = 0;
    while (cur && i < k) {
      next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
      i++;
    }
    if (lastOfPrev) lastOfPrev.next = prev; else head = prev;
    lastOfSub.next = cur;
    if (!cur) break;
    prev = lastOfSub;
  }
  return head;
}
med
Reverse Alternating K · Rotate a LinkedListReverse k, skip k. Rotate = circularize, break at len − k%len.
▸
solution · patterns/06-linkedlist-reversal.js
function reverseAlternatingK(head, k) {
  if (k <= 1 || !head) return head;
  let cur = head, prev = null;
  while (cur) {
    const lastOfPrev = prev;
    const lastOfSub = cur;
    let next = null, i = 0;
    while (cur && i < k) {          // reverse k
      next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
      i++;
    }
    if (lastOfPrev) lastOfPrev.next = prev; else head = prev;
    lastOfSub.next = cur;
    i = 0;
    while (cur && i < k) { prev = cur; cur = cur.next; i++; } // skip k
  }
  return head;
}

function rotateList(head, k) {
  if (!head || !head.next || k <= 0) return head;
  let last = head, length = 1;
  while (last.next) { last = last.next; length++; }
  last.next = head; // make it circular
  k %= length;
  const skip = length - k;
  let newTail = head;
  for (let i = 0; i < skip - 1; i++) newTail = newTail.next;
  const newHead = newTail.next;
  newTail.next = null;
  return newHead;
}
Time O(N)
Space O(1)
PATTERN 07

Tree Breadth-First Search

Traverse a tree level by level with a queue. The trick that makes it per-level: snapshot the queue's size at the top of each loop and process exactly that many nodes.

How it works
Recognize it when
level orderlevel by leveleach levelminimum depthright/left viewconnect siblings
Key move: levelSize = queue.length before the inner loop freezes the current level, so children you enqueue don't bleed into it.
level-order · template
const result = [], queue = [root];
while (queue.length > 0) {
  const levelSize = queue.length, level = [];
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    level.push(node.value);
    if (node.left)  queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  result.push(level);
}
return result;
Drill these
easy
Level Order & Reverse Level OrderReverse = unshift each level to the front.
▸
solution · patterns/07-tree-bfs.js
function levelOrder(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

function reverseLevelOrder(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.unshift(level);
  }
  return result;
}
med
Zigzag TraversalFlip a leftToRight flag; unshift on reverse levels.
▸
solution · patterns/07-tree-bfs.js
function zigzagLevelOrder(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (leftToRight) level.push(node.value);
      else level.unshift(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
    leftToRight = !leftToRight;
  }
  return result;
}
easy
Level Averages · Maximums · Minimum DepthRunning sum/max per level; min depth returns at the first leaf.
▸
solution · patterns/07-tree-bfs.js
function levelAverages(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    let sum = 0;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      sum += node.value;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(sum / size);
  }
  return result;
}

function minDepth(root) {
  if (!root) return 0;
  const queue = [root];
  let depth = 0;
  while (queue.length) {
    depth++;
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (!node.left && !node.right) return depth;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return depth;
}
med
Connect Level-Order Siblings · Right ViewRemember previous node to set .next; right view = last of each level.
▸
solution · patterns/07-tree-bfs.js
function connectLevelSiblings(root) {
  if (!root) return root;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    let prev = null;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (prev) prev.next = node;
      prev = node;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return root;
}

function rightView(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (i === size - 1) result.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}
Time O(N)
Space O(W) widest level
PATTERN 08

Tree Depth-First Search

Recurse down each branch to a leaf, carrying state (remaining sum, current path). Space is O(H), the height — the recursion stack, not a queue.

How it works
Recognize it when
root-to-leaf pathpath sumpath sequencecount pathstree diametermax path sum
Key move: a leaf is !node.left && !node.right. To collect all paths, push the node, recurse, then pop on the way up (backtrack). For diameter/max-sum, return a value up while updating a global.
root-to-leaf · template
function hasPath(node, sum) {
  if (node === null) return false;
  if (node.value === sum && !node.left && !node.right) return true;  // leaf
  return hasPath(node.left,  sum - node.value)
      || hasPath(node.right, sum - node.value);
}
Drill these
easy
Binary Tree Path Sum (exists?)Subtract node value going down; check at the leaf.
▸
solution · patterns/08-tree-dfs.js
function hasPathSum(node, sum) {
  if (!node) return false;
  if (node.value === sum && !node.left && !node.right) return true;
  return hasPathSum(node.left, sum - node.value) ||
         hasPathSum(node.right, sum - node.value);
}
med
All Paths for a Sum · Sum of Path NumbersCarry a path array (backtrack), or build 10*prev + val.
▸
solution · patterns/08-tree-dfs.js
function allPathsForSum(root, sum) {
  const result = [];
  const dfs = (node, remaining, path) => {
    if (!node) return;
    path.push(node.value);
    if (node.value === remaining && !node.left && !node.right) {
      result.push([...path]);
    } else {
      dfs(node.left, remaining - node.value, path);
      dfs(node.right, remaining - node.value, path);
    }
    path.pop(); // backtrack
  };
  dfs(root, sum, []);
  return result;
}

function sumOfPathNumbers(root) {
  const dfs = (node, pathNum) => {
    if (!node) return 0;
    pathNum = pathNum * 10 + node.value;
    if (!node.left && !node.right) return pathNum;
    return dfs(node.left, pathNum) + dfs(node.right, pathNum);
  };
  return dfs(root, 0);
}
med
Path With Sequence · Count Paths for a SumCount-paths sums every suffix of the current path at each node.
▸
solution · patterns/08-tree-dfs.js
function hasPathSequence(root, sequence) {
  const dfs = (node, index) => {
    if (!node) return false;
    if (index >= sequence.length || node.value !== sequence[index]) return false;
    if (!node.left && !node.right && index === sequence.length - 1) return true;
    return dfs(node.left, index + 1) || dfs(node.right, index + 1);
  };
  return dfs(root, 0);
}

function countPathsForSum(root, S) {
  const dfs = (node, path) => {
    if (!node) return 0;
    path.push(node.value);
    let count = 0, sum = 0;
    for (let i = path.length - 1; i >= 0; i--) {
      sum += path[i];
      if (sum === S) count++;
    }
    count += dfs(node.left, path) + dfs(node.right, path);
    path.pop(); // backtrack
    return count;
  };
  return dfs(root, []);
}
med
Tree DiameterleftH + rightH is a candidate; return max(l,r)+1 upward.
▸
solution · patterns/08-tree-dfs.js
function treeDiameter(root) {
  let diameter = 0;
  const height = (node) => {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    diameter = Math.max(diameter, left + right + 1);
    return Math.max(left, right) + 1;
  };
  height(root);
  return diameter;
}
hard
Maximum Path Sum (any node to any node)Clamp negative children to 0; global = left+right+val.
▸
solution · patterns/08-tree-dfs.js
function maxPathSum(root) {
  let max = -Infinity;
  const dfs = (node) => {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);   // ignore negative contributions
    const right = Math.max(dfs(node.right), 0);
    max = Math.max(max, left + right + node.value);
    return Math.max(left, right) + node.value;
  };
  dfs(root);
  return max;
}
Time O(N)
Space O(H) stack
PATTERN 09

Two Heaps

Split the data into a smaller half and a larger half. A max-heap holds the small half (top = largest small), a min-heap the large half (top = smallest large). The median lives at the tops.

How it works
Recognize it when
median of a streamsliding window mediansmallest in one part, largest in otherschedule by profit
Key move: after each insert, rebalance so the heaps differ in size by at most 1 (keep the extra in the max-heap). Median = max-heap top (odd) or the average of both tops (even).
median of a stream · logic
// maxHeap = smaller half, minHeap = larger half
function insert(num) {
  if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.push(num);
  else minHeap.push(num);
  if (maxHeap.size() > minHeap.size() + 1) minHeap.push(maxHeap.pop());
  else if (minHeap.size() > maxHeap.size())     maxHeap.push(minHeap.pop());
}
function findMedian() {
  return maxHeap.size() === minHeap.size()
    ? (maxHeap.peek() + minHeap.peek()) / 2
    : maxHeap.peek();
}
Drill these
med
Median of a Number StreamAnchor problem — insert O(log N), median O(1).
▸
solution · patterns/09-two-heaps.js
class MedianFinder {
  constructor() {
    this.low = MaxHeap();  // smaller half (top = largest of the small)
    this.high = MinHeap(); // larger half  (top = smallest of the large)
  }
  insert(num) {
    if (this.low.isEmpty() || num <= this.low.peek()) this.low.push(num);
    else this.high.push(num);
    // rebalance
    if (this.low.size() > this.high.size() + 1) this.high.push(this.low.pop());
    else if (this.high.size() > this.low.size()) this.low.push(this.high.pop());
  }
  findMedian() {
    if (this.low.size() === this.high.size()) {
      return (this.low.peek() + this.high.peek()) / 2;
    }
    return this.low.peek();
  }
}
hard
Sliding Window MedianSame two heaps; also remove the element leaving the window, then rebalance.
▸
solution · patterns/09-two-heaps.js
function slidingWindowMedian(nums, k) {
  const result = [];
  for (let i = 0; i + k <= nums.length; i++) {
    const window = nums.slice(i, i + k).sort((a, b) => a - b);
    const mid = Math.floor(k / 2);
    result.push(k % 2 ? window[mid] : (window[mid - 1] + window[mid]) / 2);
  }
  return result;
}
hard
Maximize Capital (IPO) · Next IntervalHeap by capital + heap by profit; greedily take the most profitable affordable project.
▸
solution · patterns/09-two-heaps.js
function maximizeCapital(capital, profits, k, initialCapital) {
  const n = capital.length;
  const byCapital = MinHeap((a, b) => capital[a] - capital[b]); // project indices
  const byProfit = MaxHeap((a, b) => profits[b] - profits[a]);
  for (let i = 0; i < n; i++) byCapital.push(i);
  let available = initialCapital;
  for (let c = 0; c < k; c++) {
    while (!byCapital.isEmpty() && capital[byCapital.peek()] <= available) {
      byProfit.push(byCapital.pop());
    }
    if (byProfit.isEmpty()) break;
    available += profits[byProfit.pop()];
  }
  return available;
}
Insert O(log N)
Median O(1)
PATTERN 10

Subsets

Generate all subsets / permutations / combinations by building on what you already have: start from a seed and, for each new element, extend every existing partial result.

How it works
Recognize it when
all subsetsall permutationsall combinationsgenerate parenthesesevery arrangement
Key move: subsets double each step (add num to every existing set). Permutations insert the new num at every position of each arrangement. With duplicates: sort first, extend only subsets created in the previous step.
all subsets (BFS) · template
const subsets = [[]];
for (const num of nums) {
  const n = subsets.length;
  for (let i = 0; i < n; i++) {
    subsets.push([...subsets[i], num]);   // extend every existing subset
  }
}
return subsets;
Drill these
easy
SubsetsThe doubling template.
▸
solution · patterns/10-subsets.js
function subsets(nums) {
  const result = [[]];
  for (const num of nums) {
    const n = result.length;
    for (let i = 0; i < n; i++) result.push([...result[i], num]);
  }
  return result;
}
med
Subsets With DuplicatesSort; on num === prev, only extend the last round's subsets.
▸
solution · patterns/10-subsets.js
function subsetsWithDuplicates(nums) {
  nums.sort((a, b) => a - b);
  const result = [[]];
  let start = 0;
  for (let i = 0; i < nums.length; i++) {
    // if current == previous, only extend subsets added in the previous step
    const from = (i > 0 && nums[i] === nums[i - 1]) ? start : 0;
    const end = result.length;
    start = end;
    for (let j = from; j < end; j++) result.push([...result[j], nums[i]]);
  }
  return result;
}
med
Permutations · By Changing CaseInsert num at every gap; for case-perms branch upper/lower.
▸
solution · patterns/10-subsets.js
function permutations(nums) {
  let perms = [[]];
  for (const num of nums) {
    const next = [];
    for (const perm of perms) {
      for (let i = 0; i <= perm.length; i++) {
        const copy = [...perm];
        copy.splice(i, 0, num);
        next.push(copy);
      }
    }
    perms = next;
  }
  return perms;
}

function letterCasePermutations(str) {
  let perms = [''];
  for (const ch of str) {
    const next = [];
    for (const p of perms) {
      if (ch >= '0' && ch <= '9') next.push(p + ch);
      else { next.push(p + ch.toLowerCase()); next.push(p + ch.toUpperCase()); }
    }
    perms = next;
  }
  return perms;
}
hard
Balanced Parentheses · AbbreviationsBacktrack over partial strings; prune invalid branches early.
▸
solution · patterns/10-subsets.js
function generateParentheses(n) {
  const result = [];
  const backtrack = (current, open, close) => {
    if (current.length === 2 * n) { result.push(current); return; }
    if (open < n) backtrack(current + '(', open + 1, close);
    if (close < open) backtrack(current + ')', open, close + 1);
  };
  backtrack('', 0, 0);
  return result;
}
hard
Evaluate Expression · Unique BSTsDivide at each operator/root; combine left & right sub-results.
▸
solution · patterns/10-subsets.js
function diffWaysToCompute(input) {
  const memo = new Map();
  const solve = (expr) => {
    if (memo.has(expr)) return memo.get(expr);
    if (/^\d+$/.test(expr)) return [parseInt(expr, 10)];
    const res = [];
    for (let i = 0; i < expr.length; i++) {
      const ch = expr[i];
      if (ch === '+' || ch === '-' || ch === '*') {
        for (const l of solve(expr.slice(0, i))) {
          for (const r of solve(expr.slice(i + 1))) {
            res.push(ch === '+' ? l + r : ch === '-' ? l - r : l * r);
          }
        }
      }
    }
    memo.set(expr, res);
    return res;
  };
  return solve(input).sort((a, b) => a - b);
}

function countUniqueBSTs(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = dp[1] = 1;
  for (let nodes = 2; nodes <= n; nodes++) {
    for (let root = 1; root <= nodes; root++) {
      dp[nodes] += dp[root - 1] * dp[nodes - root]; // left subtrees × right subtrees
    }
  }
  return dp[n];
}
Subsets O(N·2ᴺ)
Permutations O(N·N!)
PATTERN 11

Modified Binary Search

Any sorted structure + "find something" = halve the search space each step. Master the base loop, then adapt the comparison for ceilings, rotations, and unknown sort order.

How it works
Recognize it when
sorted array / matrixfind element or indexceiling / next letterrotated sortedO(log n)
Key move: mid = start + (end − start) / 2 avoids overflow. Order-agnostic: peek at arr[start] vs arr[end] to learn direction, then flip the comparison.
order-agnostic search · template
let start = 0, end = arr.length - 1;
const asc = arr[start] < arr[end];
while (start <= end) {
  const mid = start + Math.floor((end - start) / 2);
  if (arr[mid] === key) return mid;
  if (asc ? key < arr[mid] : key > arr[mid]) end = mid - 1;
  else start = mid + 1;
}
return -1;
Drill these
easy
Order-agnostic Binary SearchDetect direction, then standard halving.
▸
solution · patterns/11-modified-binary-search.js
function orderAgnosticSearch(arr, key) {
  let start = 0, end = arr.length - 1;
  const asc = arr[start] < arr[end];
  while (start <= end) {
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] === key) return mid;
    if (asc ? key < arr[mid] : key > arr[mid]) end = mid - 1;
    else start = mid + 1;
  }
  return -1;
}
med
Ceiling / Floor · Next LetterOn "not found", start lands on the ceiling index (wrap for next-letter).
▸
solution · patterns/11-modified-binary-search.js
function ceilingOfNumber(arr, key) {
  if (key > arr[arr.length - 1]) return -1;
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    const mid = start + Math.floor((end - start) / 2);
    if (key < arr[mid]) end = mid - 1;
    else if (key > arr[mid]) start = mid + 1;
    else return mid;
  }
  return start; // start is the ceiling index once the loop exits
}

function nextLetter(letters, key) {
  let start = 0, end = letters.length - 1;
  while (start <= end) {
    const mid = start + Math.floor((end - start) / 2);
    if (key < letters[mid]) end = mid - 1;
    else start = mid + 1;
  }
  return letters[start % letters.length];
}
med
Number Range · Search Rotated ArrayRange = two searches. Rotated: one half is always sorted — pick it.
▸
solution · patterns/11-modified-binary-search.js
function numberRange(arr, key) {
  const find = (findFirst) => {
    let idx = -1, start = 0, end = arr.length - 1;
    while (start <= end) {
      const mid = start + Math.floor((end - start) / 2);
      if (key < arr[mid]) end = mid - 1;
      else if (key > arr[mid]) start = mid + 1;
      else { idx = mid; if (findFirst) end = mid - 1; else start = mid + 1; }
    }
    return idx;
  };
  return [find(true), find(false)];
}

function searchRotated(arr, key) {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] === key) return mid;
    if (arr[start] <= arr[mid]) {          // left half is sorted
      if (key >= arr[start] && key < arr[mid]) end = mid - 1;
      else start = mid + 1;
    } else {                                // right half is sorted
      if (key > arr[mid] && key <= arr[end]) start = mid + 1;
      else end = mid - 1;
    }
  }
  return -1;
}
med
Search a Bitonic ArrayBinary-search the peak, then search each monotonic side.
▸
solution · patterns/11-modified-binary-search.js
function findMaxInBitonic(arr) {
  let start = 0, end = arr.length - 1;
  while (start < end) {
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] > arr[mid + 1]) end = mid;   // peak is at mid or to the left
    else start = mid + 1;                     // peak is to the right
  }
  return arr[start];
}
Time O(log N)
Space O(1)
PATTERN 12

Bitwise XOR

XOR cancels pairs: a ^ a = 0, a ^ 0 = a, and it's commutative & associative. XOR a whole collection and everything appearing twice vanishes, leaving the odd one out — no extra space, no overflow.

How it works
Recognize it when
every number appears twice except…missing numbersingle numbercomplementflip bits
Two single numbers? XOR everything → n1 ^ n2. Isolate any set bit (the rightmost 1), partition all numbers by that bit into two groups, XOR each group to recover both singles.
single number · template
let x = 0;
for (const n of nums) x ^= n;   // pairs cancel, single survives
return x;

// missing number in [1..n] without overflow:
// XOR of 1..n  ^  XOR of the array  =  the missing value
Drill these
easy
Missing Number · Single NumberXOR beats the sum formula — it can't overflow.
▸
solution · patterns/12-bitwise-xor.js
function findMissingNumber(arr) {
  const n = arr.length + 1;
  let x1 = 0;
  for (let i = 1; i <= n; i++) x1 ^= i;   // XOR of 1..n
  let x2 = 0;
  for (const v of arr) x2 ^= v;           // XOR of the array
  return x1 ^ x2;                          // survivors cancel; missing remains
}

function singleNumber(arr) {
  let x = 0;
  for (const v of arr) x ^= v;
  return x;
}
med
Two Single NumbersPartition by a differing bit, XOR each group.
▸
solution · patterns/12-bitwise-xor.js
function twoSingleNumbers(nums) {
  let n1xn2 = 0;
  for (const v of nums) n1xn2 ^= v;       // = num1 ^ num2
  // isolate the rightmost set bit — a bit where num1 and num2 differ
  const rightmostSetBit = n1xn2 & -n1xn2;
  let num1 = 0, num2 = 0;
  for (const v of nums) {
    if (v & rightmostSetBit) num1 ^= v;   // group A
    else num2 ^= v;                        // group B
  }
  return [num1, num2].sort((a, b) => a - b);
}
med
Complement of Base-10 Numbercomplement = num ^ allBitsSet, allBitsSet = 2^bits − 1.
▸
solution · patterns/12-bitwise-xor.js
function bitwiseComplement(num) {
  if (num === 0) return 1;
  let bitCount = 0, n = num;
  while (n > 0) { bitCount++; n >>= 1; }
  const allBitsSet = Math.pow(2, bitCount) - 1;
  return num ^ allBitsSet;                 // complement = num ^ allBitsSet
}
hard
Flip and Invert Binary MatrixReverse each row, then XOR each bit with 1.
▸
solution · patterns/12-bitwise-xor.js
function flipAndInvertMatrix(matrix) {
  return matrix.map((row) => row.reverse().map((bit) => bit ^ 1));
}
Time O(N)
Space O(1)
PATTERN 13

Top 'K' Elements

Whenever you need the top / smallest / most-frequent K of something, hold a heap of size K instead of sorting everything. For the K largest use a min-heap (evict the smallest); for the K smallest use a max-heap.

How it works
Recognize it when
top KK largest / smallestK most frequentK closestrunning Kth largest
Key move: push every element; whenever the heap exceeds size K, pop the top. A min-heap keeps the K largest (its top is the weakest survivor = the Kth largest). Flip to a max-heap for the K smallest.
Kth largest · template
const heap = new MinHeap();          // smallest of the K largest on top
for (const n of nums) {
  heap.push(n);
  if (heap.size() > k) heap.pop();     // evict the smallest
}
return heap.peek();                    // the Kth largest
Drill these
easy
Kth Largest / Smallest NumberMin-heap of size k (largest) / max-heap of size k (smallest).
▸
solution · patterns/13-top-k-elements.js
function findKthLargest(nums, k) {
  const heap = MinHeap(); // smallest of the K largest stays on top
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

function findKthSmallest(nums, k) {
  const heap = MaxHeap(); // largest of the K smallest stays on top
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

function findKLargest(nums, k) {
  const heap = MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.data.slice().sort((a, b) => a - b);
}
easy
Kth Largest in a StreamKeep a size-k min-heap alive across inserts; top is the answer each time.
▸
solution · patterns/13-top-k-elements.js
class KthLargestInStream {
  constructor(k, nums = []) {
    this.k = k;
    this.heap = MinHeap();
    for (const n of nums) this.add(n);
  }
  add(num) {
    this.heap.push(num);
    if (this.heap.size() > this.k) this.heap.pop();
    return this.heap.peek();
  }
}
med
K Closest Points to Origin · K Closest NumbersMax-heap of size k by distance; evict the farthest.
▸
solution · patterns/13-top-k-elements.js
function kClosestPointsToOrigin(points, k) {
  const dist = (p) => p[0] * p[0] + p[1] * p[1];
  // keep the K closest -> evict the farthest -> largest distance on top
  const heap = new Heap((a, b) => dist(b) - dist(a));
  for (const p of points) {
    heap.push(p);
    if (heap.size() > k) heap.pop();
  }
  return heap.data.slice().sort((a, b) => dist(a) - dist(b));
}

function findClosestElements(arr, k, x) {
  let lo = 0, hi = arr.length - k;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1; // window better if shifted right
    else hi = mid;
  }
  return arr.slice(lo, lo + k);
}
med
Top K Frequent · Frequency SortCount with a map, then a heap keyed by frequency.
▸
solution · patterns/13-top-k-elements.js
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // keep K most frequent -> evict least frequent -> smallest freq on top
  const heap = new Heap((a, b) => freq.get(a) - freq.get(b));
  for (const n of freq.keys()) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  // tie-break by value descending so the result is deterministic
  return heap.data.slice().sort((a, b) => freq.get(b) - freq.get(a) || b - a);
}

function frequencySort(str) {
  const freq = new Map();
  for (const c of str) freq.set(c, (freq.get(c) || 0) + 1);
  const heap = new Heap((a, b) =>
    freq.get(b) - freq.get(a) || a.charCodeAt(0) - b.charCodeAt(0)); // most frequent, then a..z
  for (const c of freq.keys()) heap.push(c);
  let result = '';
  while (!heap.isEmpty()) {
    const c = heap.pop();
    result += c.repeat(freq.get(c));
  }
  return result;
}
med
Connect Ropes for Minimum CostMin-heap; repeatedly join the two shortest, push the sum back.
▸
solution · patterns/13-top-k-elements.js
function connectRopesMinCost(lengths) {
  const heap = MinHeap();
  for (const l of lengths) heap.push(l);
  let cost = 0;
  while (heap.size() > 1) {
    const joined = heap.pop() + heap.pop();
    cost += joined;
    heap.push(joined);
  }
  return cost;
}
Time O(N log K)
Space O(K)
PATTERN 14

K-way Merge

To combine or query across K sorted lists at once, seed a min-heap with the head of each list. Each pop yields the global-next element; then push that element's successor from the same list.

How it works
Recognize it when
merge K sorted listsKth smallest across M listssorted matrixsmallest range covering all
Key move: the heap only ever holds one candidate per list (≤ K items), so it always surfaces the smallest un-taken element in O(log K). Track which list each entry came from to push its successor.
merge K sorted lists · template
const heap = new MinHeap((a, b) => a.value - b.value);
for (const list of lists) if (list) heap.push(list);  // seed heads
const out = [];
while (!heap.isEmpty()) {
  const node = heap.pop();
  out.push(node.value);
  if (node.next) heap.push(node.next);            // pull successor
}
return out;
Drill these
med
Merge K Sorted Lists / ArraysThe template — heap of heads, push successor on each pop.
▸
solution · patterns/14-k-way-merge.js
function mergeKSortedArrays(arrays) {
  // heap entries: [value, listIndex, elemIndex]
  const heap = MinHeap((a, b) => a[0] - b[0]);
  arrays.forEach((arr, i) => { if (arr.length) heap.push([arr[0], i, 0]); });
  const result = [];
  while (!heap.isEmpty()) {
    const [val, list, idx] = heap.pop();
    result.push(val);
    if (idx + 1 < arrays[list].length) heap.push([arrays[list][idx + 1], list, idx + 1]);
  }
  return result;
}

function mergeKSortedLists(lists) {
  const heap = new Heap((a, b) => a.value - b.value);
  for (const node of lists) if (node) heap.push(node);
  const dummy = new ListNode(0);
  let tail = dummy;
  while (!heap.isEmpty()) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  tail.next = null;
  return dummy.next;
}
med
Kth Smallest in M Sorted ArraysSame merge; stop after popping k elements.
▸
solution · patterns/14-k-way-merge.js
function kthSmallestInMArrays(arrays, k) {
  const heap = MinHeap((a, b) => a[0] - b[0]);
  arrays.forEach((arr, i) => { if (arr.length) heap.push([arr[0], i, 0]); });
  let count = 0;
  while (!heap.isEmpty()) {
    const [val, list, idx] = heap.pop();
    if (++count === k) return val;
    if (idx + 1 < arrays[list].length) heap.push([arrays[list][idx + 1], list, idx + 1]);
  }
  return -1;
}
med
Kth Smallest in a Sorted MatrixTreat each row as a sorted list; merge rows.
▸
solution · patterns/14-k-way-merge.js
function kthSmallestInSortedMatrix(matrix, k) {
  const heap = MinHeap((a, b) => a[0] - b[0]); // [value, row, col]
  const n = matrix.length;
  for (let r = 0; r < Math.min(n, k); r++) heap.push([matrix[r][0], r, 0]);
  let count = 0;
  while (!heap.isEmpty()) {
    const [val, r, c] = heap.pop();
    if (++count === k) return val;
    if (c + 1 < matrix[r].length) heap.push([matrix[r][c + 1], r, c + 1]);
  }
  return -1;
}
hard
Smallest Number RangeTrack current max across the heads; range = [heap.top, curMax]; shrink as you advance.
▸
solution · patterns/14-k-way-merge.js
function smallestRange(lists) {
  const heap = MinHeap((a, b) => a[0] - b[0]); // [value, listIndex, elemIndex]
  let currentMax = -Infinity;
  lists.forEach((list, i) => {
    if (list.length) { heap.push([list[0], i, 0]); currentMax = Math.max(currentMax, list[0]); }
  });
  let rangeStart = 0, rangeEnd = Infinity;
  while (heap.size() === lists.length) { // every list still represented
    const [val, list, idx] = heap.pop();
    if (currentMax - val < rangeEnd - rangeStart) { rangeStart = val; rangeEnd = currentMax; }
    if (idx + 1 < lists[list].length) {
      const next = lists[list][idx + 1];
      heap.push([next, list, idx + 1]);
      currentMax = Math.max(currentMax, next);
    }
  }
  return [rangeStart, rangeEnd];
}
Time O(N log K)
Space O(K)
PATTERN 15

0/1 Knapsack (Dynamic Programming)

Choose a subset of items — each taken at most once — to satisfy a capacity or target. Build a DP table over (items processed, capacity). A huge family of "can we make sum S / max value under weight W / equal partition" problems reduces to this.

How it works
Recognize it when
subset under a capacitytarget sumequal partitioncan we make sum Scount of ways
Key move: collapse the 2-D table to a rolling 1-D array of size capacity+1, and iterate capacity downward — that guarantees each item is used at most once (the "0/1"). Iterating upward would allow reuse (unbounded knapsack).
0/1 knapsack · template
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
  for (let c = capacity; c >= weight[i]; c--) {   // downward = each item once
    dp[c] = Math.max(dp[c], profit[i] + dp[c - weight[i]]);
  }
}
return dp[capacity];
Drill these
med
0/1 KnapsackMax profit within a weight capacity.
▸
solution · patterns/15-knapsack-dp.js
function solveKnapsack(profits, weights, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < profits.length; i++) {
    // iterate capacity downward so each item is used at most once
    for (let c = capacity; c >= weights[i]; c--) {
      dp[c] = Math.max(dp[c], profits[i] + dp[c - weights[i]]);
    }
  }
  return dp[capacity];
}
med
Equal Subset Sum Partition · Subset SumBoolean dp: can we hit total/2 (or target)?
▸
solution · patterns/15-knapsack-dp.js
function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  return subsetSum(nums, total / 2);
}

function subsetSum(nums, target) {
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let s = target; s >= num; s--) {
      dp[s] = dp[s] || dp[s - num];
    }
  }
  return dp[target];
}
hard
Minimum Subset Sum DifferenceLargest achievable sum ≤ total/2 → diff = total − 2·s.
▸
solution · patterns/15-knapsack-dp.js
function minSubsetSumDifference(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  const half = Math.floor(total / 2);
  const dp = new Array(half + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let s = half; s >= num; s--) dp[s] = dp[s] || dp[s - num];
  }
  for (let s = half; s >= 0; s--) {
    if (dp[s]) return total - 2 * s; // s is the largest achievable sum <= total/2
  }
  return total;
}
hard
Count of Subset Sum · Target SumInteger dp counting ways; Target Sum reduces to a subset-count.
▸
solution · patterns/15-knapsack-dp.js
function countSubsetSum(nums, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (const num of nums) {
    for (let s = target; s >= num; s--) {
      dp[s] += dp[s - num];
    }
  }
  return dp[target];
}

function targetSum(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
  return countSubsetSum(nums, (total + target) / 2);
}
Time O(N·C)
Space O(C) (rolling)
PATTERN 16

Topological Sort

Order the nodes of a directed graph so every edge points forward — the classic "do X before Y" scheduling shape. Kahn's algorithm: repeatedly emit any node with no remaining prerequisites.

How it works
Recognize it when
dependencies / prerequisitescan all tasks finish?build a valid ordercycle in a digraphalien dictionary
Key move: count each node's in-degree; queue those at 0; when you emit a node, decrement its neighbors and enqueue any that hit 0. If you emit fewer than V nodes, the graph has a cycle (no valid order).
Kahn's algorithm · template
const inDegree = Array(V).fill(0);
const graph = Array.from({ length: V }, () => []);
for (const [from, to] of edges) { graph[from].push(to); inDegree[to]++; }

const queue = [], order = [];
for (let i = 0; i < V; i++) if (inDegree[i] === 0) queue.push(i);
while (queue.length) {
  const node = queue.shift();
  order.push(node);
  for (const next of graph[node]) if (--inDegree[next] === 0) queue.push(next);
}
return order.length === V ? order : [];   // [] ⇒ cycle
Drill these
med
Topological Sort of a DAGThe template; empty result signals a cycle.
▸
solution · patterns/16-topological-sort.js
function topologicalSort(vertexCount, edges) {
  const inDegree = new Array(vertexCount).fill(0);
  const graph = Array.from({ length: vertexCount }, () => []);
  for (const [from, to] of edges) { graph[from].push(to); inDegree[to]++; }
  const queue = [];
  for (let i = 0; i < vertexCount; i++) if (inDegree[i] === 0) queue.push(i);
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) if (--inDegree[next] === 0) queue.push(next);
  }
  return order.length === vertexCount ? order : []; // [] => cycle
}
med
Tasks Scheduling (can finish?) · OrderPrerequisite [task, pre] becomes edge pre → task.
▸
solution · patterns/16-topological-sort.js
function canFinishTasks(taskCount, prerequisites) {
  const edges = prerequisites.map(([task, pre]) => [pre, task]); // pre -> task
  return topologicalSort(taskCount, edges).length === taskCount;
}

function findTaskOrder(taskCount, prerequisites) {
  const edges = prerequisites.map(([task, pre]) => [pre, task]);
  return topologicalSort(taskCount, edges);
}
med
Course Schedule I / IISame as tasks scheduling — feasibility, then a concrete order.
▸
solution · patterns/16-topological-sort.js
function canFinishTasks(taskCount, prerequisites) {
  const edges = prerequisites.map(([task, pre]) => [pre, task]); // pre -> task
  return topologicalSort(taskCount, edges).length === taskCount;
}

function findTaskOrder(taskCount, prerequisites) {
  const edges = prerequisites.map(([task, pre]) => [pre, task]);
  return topologicalSort(taskCount, edges);
}
hard
Alien DictionaryDerive letter-ordering edges from adjacent words, then topo-sort the letters.
▸
solution · patterns/16-topological-sort.js
function alienDictionaryOrder(words) {
  const graph = new Map();
  const inDegree = new Map();
  for (const word of words) for (const ch of word) {
    if (!graph.has(ch)) { graph.set(ch, new Set()); inDegree.set(ch, 0); }
  }
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const len = Math.min(w1.length, w2.length);
    let j = 0;
    for (; j < len; j++) {
      if (w1[j] !== w2[j]) {
        if (!graph.get(w1[j]).has(w2[j])) {
          graph.get(w1[j]).add(w2[j]);
          inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
        }
        break;
      }
    }
    // invalid: a longer word appears before its own prefix ("abc" before "ab")
    if (j === len && w1.length > w2.length) return '';
  }
  const queue = [];
  for (const [ch, deg] of inDegree) if (deg === 0) queue.push(ch);
  queue.sort(); // deterministic order among equal candidates
  let order = '';
  while (queue.length) {
    const ch = queue.shift();
    order += ch;
    const nexts = [...graph.get(ch)].sort();
    for (const next of nexts) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) { queue.push(next); queue.sort(); }
    }
  }
  return order.length === inDegree.size ? order : ''; // cycle => ''
}
Time O(V + E)
Space O(V + E)
No patterns match “”.

One-screen cheat sheet

PatternData / signalCore ideaTime
Sliding Windowcontiguous subarray/substringgrow right, shrink left on violationO(N)
Two Pointerssorted; pair/triplet; in-placeconverge from both endsO(N)–O(N³)
Fast & Slowlinked list / cyclic sequence1× vs 2× speed → meet in cycleO(N)
Merge Intervalsintervals, overlap, schedulesort by start, sweep onceO(N log N)
Cyclic Sortnumbers in range [1..n]swap value to its home indexO(n)
LL Reversalreverse list / sub-list in placethree-pointer re-linkingO(N)
Tree BFSlevel-by-level tree workqueue + freeze levelSizeO(N)
Tree DFSroot-to-leaf pathsrecurse + carry state / backtrackO(N)
Two Heapsmedian / partition extremesmax-heap low half, min-heap high halfO(log N) ins
Subsetsall subsets/perms/combosextend every existing partial resultO(N·2ᴺ)
Binary Searchsorted + findhalve the search spaceO(log N)
Bitwise XORpairs cancel / bit tricksa^a=0, a^0=aO(N)
Top 'K' Elementstop / K largest / most frequentheap of size KO(N log K)
K-way MergeK sorted lists / matrixmin-heap over the K headsO(N log K)
0/1 Knapsacksubset under capacity / targetDP over (items, capacity), iterate downO(N·C)
Topological Sortdependencies / orderingKahn — emit in-degree 0O(V+E)

Interview delivery — the 6-step loop

Step 1 · Clarify

Restate & probe

Repeat the problem back. Ask about input size, sorting, ranges, duplicates, empty/negative cases. This often reveals the pattern ("it's sorted" → Two Pointers / Binary Search).

Step 2 · Brute force

State the naive cost

Name the O(N²)/O(N·K) approach in one sentence with its complexity. Shows the baseline you're about to beat.

Step 3 · Name it

"This is a sliding-window problem because…"

Say the pattern out loud and why the signal fits. This is the moment that reads as senior.

Step 4 · Dry-run

Walk a tiny example

Trace the template on a 4–5 element input before coding. Catches off-by-one and edge cases while they're cheap.

Step 5 · Code

Skeleton, then the condition

Type the pattern's template first; the problem-specific logic is only the check inside the loop. Narrate as you go.

Step 6 · Verify

Test edges, state cost

Run empty, single-element, all-duplicates. Finish with O(time)/O(space) — always. Then mention any trade-off.