Problem Solving: Approach & Patterns

0. How to use this guide

Interviews reward two things: a clear process and the ability to spot which known technique fits. Sections 1–3 build the process; sections 4–8 teach the patterns; sections 9–10 help you recognize them under pressure and practice until they stick.

The patterns at a glance

• 01 Frequency Counter Compare collections, count, find duplicates or a complement O(n) · O(n)
• 02 Multiple Pointers Sorted array, pairs or triplets, in-place clean-up O(n) · O(1)
• 03 Sliding Window Contiguous subarray or substring: size k, longest, shortest O(n) · O(1)–O(k)
• 04 Divide and Conquer Sorted data, “minimum X such that…”, split in halves O(log n) · O(n log n)
• 05 Dynamic Programming “How many ways…?”, minimum cost, overlapping subproblems Polynomial
• 06 Greedy Pick intervals or tasks in a natural order, with a proof O(n log n)
• 07 Backtracking All combinations, permutations, or subsets Exponential
• 08 Prefix Sum Range sums, subarrays summing to k, negatives allowed O(n) · O(n)

FOUNDATIONS

1. Big O in five minutes

An algorithm is a process or set of steps to accomplish a task. In interviews it is not enough for it to be correct: its time complexity (how many operations it performs relative to the input size n) and its space complexity (how much extra memory it uses) are evaluated. Every pattern in this guide exists to lower one of those two.

1.1 The complexities you will see

1.2 Quick rules for computing Big O

• Drop constants: O(2n) = O(n); O(500) = O(1).
• Keep only the dominant term: O(n² + n) = O(n²).
• Sequential loops add; nested loops multiply.
• Different inputs, different variables: iterating over a and then b is O(a + b); nested is O(a·b).
• Watch for hidden loops: indexOf, includes, splice, slice, shift and the spread [...arr] are O(n). A single for that calls indexOf inside is already O(n²) (you will see this in section 4.3).
• Hash lookups are O(1) on average: Object, Map and Set keys have O(1) average lookup and insertion. This is the foundation of the Frequency Counter.
• Recursion uses memory: it takes up space on the call stack; a recursion of depth d uses O(d) space.

1.3 Read the constraints to guess the solution

If the problem statement gives the maximum input size, it is telling you what complexity they are looking for. Assuming ~10⁸ simple operations per second:

THE METHOD

2. The problem-solving method

George Polya described a five-step strategy in How to Solve It (1945). In a technical interview the method is the same, but you have to do it out loud: the interviewer evaluates the process as much as the code. A widely used interview framework that maps almost 1-to-1 to Polya is UMPIRE: Understand, Match, Plan, Implement, Review, Evaluate.

2.1 Understand: questions to ask every time

Start by restating the problem in your own words, naming the inputs and outputs, and checking which terms you do not fully understand. Then these clarifications prevent most misunderstandings:

Types and ranges

Integers or decimals? Can they be negative? What is the maximum input size?

Order

Is the input sorted? If so, think two pointers or binary search right away.

Duplicates

Can there be repeated values? Do they count as distinct?

Strings

Are uppercase and lowercase the same? Do spaces and punctuation count? ASCII only or Unicode?

Output

Values or indices? The first answer or all of them? What if there is no answer (null, -1, undefined, an exception)?

Mutation

Can I modify the input or must I leave it intact?

Priority

Do I optimize for time or memory?

2.2 Explore examples: edge-case checklist

Write simple examples, complex examples, empty inputs and invalid inputs. They clarify the problem now and become your tests later. A concrete list to go through:

2.3 Break it down and simplify

Write the steps as comments before writing code: if you later get stuck on syntax, the interviewer has already seen that you have the idea. If the whole problem is too hard, solve a simpler version first and add the difficult part afterwards.

The most useful technique is: first state the brute force out loud with its Big O, then ask “what work am I repeating?”. Repeated work is exactly what the patterns eliminate:

2.4 Look back before saying “done”

1. Dry run. Walk through the code line by line with one of your examples, noting the value of each variable.
2. Edge cases. Mentally test the checklist, especially empty and single-element inputs.
3. Classic mistakes. Off-by-one indices, < vs <= in the while, undeclared variables, accidentally mutating the input, forgetting the return.
4. Complexity. State time and space, and whether there is a trade-off (for example, more memory in exchange for less time).
5. Alternatives. Mention improvements or other approaches even if you don’t implement them.

2.5 Time management in a 45-minute interview

THE METHOD IN ACTION

3. Worked example: charCount

1. Step 1 — Understand

   • Restate: given a string, return an object where each key is a character and the value is how many times it appears.
   • Inputs: a string. Output: an object.
   • Questions: do I count spaces and punctuation? Are "A" and "a" the same character? Do I include characters with 0 occurrences? Agreed decision: only letters and digits, case-insensitive, only the ones that appear.

2. Step 2 — Explore examples

   charCount("aaaa")              // { a: 4 }
   charCount("hello")             // { h: 1, e: 1, l: 2, o: 1 }
   charCount("Hello hi")          // { h: 2, e: 1, l: 2, o: 1, i: 1 }   case-insensitive
   charCount("Your PIN is 1234!") // spaces and "!" are ignored; digits count
   charCount("")                  // {}

3. Step 3 — Break it down

   // create an empty object for the result
   // loop over each character in the string
   //   convert it to lowercase
   //   if it is a letter or a number:
   //     if it is already in the object -> add 1
   //     if it is not                   -> add it with value 1
   //   if it is not alphanumeric: ignore it
   // return the object

4. Step 4 — Solve

   If the “is alphanumeric” part turns out to be hard, apply Simplify: first count every character without filtering, and then add the filter. Final version:

   function charCount(str) {
     const result = {};
     for (const ch of str.toLowerCase()) {
       if (/[a-z0-9]/.test(ch)) {
         result[ch] = (result[ch] || 0) + 1;
       }
     }
     return result;
   }

5. Step 5 — Look back & refactor

   Readability

   for...of is clearer than an indexed for, and (result[ch] || 0) + 1 replaces the if/else.

   Performance

   Running the regex on every iteration has a cost. A faster alternative compares the character code: charCodeAt between 48–57 (digits) or 97–122 (a–z). Benchmark before optimizing; in an interview it is enough to mention it.

   Structure

   Map avoids collisions with inherited properties ("constructor", "__proto__") and preserves insertion order.

   Complexity

   O(n) time; O(k) space, where k is the number of distinct characters (at most 36 with this filter, i.e. O(1)).

PATTERN 01 · HASH MAPS

4. Frequency Counter

Instead of searching for a value inside another loop, iterate over the collection once and store counts or presence in an object, Map or Set. After that, each lookup costs O(1).

Use it when

You compare two collections, count occurrences, look for duplicates, or need a complement in unsorted data.

Core idea

One pass stores counts or presence in a Map, Set, or object; after that every lookup is O(1).

Cost

Turns O(n²) into O(n) time in exchange for O(n) memory.

Classic trap

Plain-object keys are always strings, and helpers like splice silently mutate the caller’s array.

4.1 When to use it

• Comparing two collections: “same elements”, “same frequency”, anagrams, permutations.
• Questions like “is there a duplicate?”, “how many times does it appear?”, “the first non-repeating one”.
• Looking for a complement: “two numbers that add up to X” in an unsorted array.
• Grouping elements by a key (for example, grouping anagrams).

4.2 Template

function frequencyCounter(a, b) {
  if (a.length !== b.length) return false;      // cheap shortcut
  const freq = new Map();
  for (const x of a) freq.set(x, (freq.get(x) || 0) + 1);  // count
  for (const x of b) {                                       // consume
    if (!freq.get(x)) return false;
    freq.set(x, freq.get(x) - 1);
  }
  return true;
}

4.3 Common pitfalls

Take same(arr1, arr2): return true if every value in arr1 has its square in arr2, with the same frequency. The first idea most people write is this:

// Naive version: O(n²), and it empties arr2 as a side effect
function sameNaive(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;
  for (let i = 0; i < arr1.length; i++) {
    const index = arr2.indexOf(arr1[i] ** 2); // hidden O(n) loop
    if (index === -1) return false;
    arr2.splice(index, 1);                    // hidden O(n) loop + mutation
  }
  return true;
}

• It is O(n²): indexOf and splice are O(n) inside an O(n) loop.
• It modifies the caller's array: after sameNaive(a, b), b ends up empty or incomplete. If you need to mutate, work on a copy: const copy = [...arr2].
• Object keys are always strings: if you count with a plain object, key ** 2 only works because JS converts "2" to a number when using **. It is fragile: with a Map keys keep their type.
• Redundant checks: a guard like if (!(key ** 2 in freq2)) before comparing counts is unnecessary: if the key doesn't exist, the comparison already yields undefined !== n.

Version using Map, with no coercion or mutation:

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;
  const freq1 = new Map();
  const freq2 = new Map();
  for (const v of arr1) freq1.set(v, (freq1.get(v) || 0) + 1);
  for (const v of arr2) freq2.set(v, (freq2.get(v) || 0) + 1);
  for (const [v, count] of freq1) {
    if (freq2.get(v ** 2) !== count) return false;
  }
  return true;
}

4.4 Worked example: validAnagram

Count the letters of the first string and “consume” them with the second. If any letter is not available (count 0 or missing), it is not an anagram. Since we already checked that the lengths are equal, there is no need for a third loop to verify that everything ends at 0.

function validAnagram(a, b) {
  if (a.length !== b.length) return false;
  const lookup = {};
  for (const ch of a) lookup[ch] = (lookup[ch] || 0) + 1;
  for (const ch of b) {
    if (!lookup[ch]) return false;
    lookup[ch] -= 1;
  }
  return true;
}

O(n) timeO(1) space for a fixed 26-letter alphabet · O(k) in general

Alternative: sort both strings and compare them: [...a].sort().join('') === [...b].sort().join('') is O(n log n); worth mentioning as the brute force.

4.5 Exercises

sameFrequency(182, 281)          // true
sameFrequency(34, 14)            // false
sameFrequency(3589578, 5879385)  // true

function sameFrequency(n1, n2) {
  const s1 = String(n1), s2 = String(n2);
  if (s1.length !== s2.length) return false;
  const freq = {};
  for (const d of s1) freq[d] = (freq[d] || 0) + 1;
  for (const d of s2) {
    if (!freq[d]) return false;
    freq[d]--;
  }
  return true;
}

function areThereDuplicates(...args) {
  return new Set(args).size !== args.length;
}

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

4.6 Practice on LeetCode

• 242Valid Anagram
• 1Two Sum
• 49Group Anagrams
• 387First Unique Character
• 383Ransom Note
• 217Contains Duplicate
• 128Longest Consecutive Sequence
• 560Subarray Sum Equals K (with prefix sums, 8.4)

PATTERN 02 · INDICES

5. Multiple Pointers

Use two (or more) indices that traverse the structure and move based on a condition. It avoids the nested loop and usually uses O(1) extra memory. Most of the time it requires the input to be sorted (or sorting it to be acceptable, O(n log n)).

Use it when

The input is sorted (or sorting is acceptable) and you compare pairs, clean up in place, or walk two sequences.

Core idea

Two or more indices move by a rule; each move safely discards at least one candidate.

Cost

O(n) time and O(1) extra memory, plus O(n log n) if you have to sort first.

Classic trap

Using left <= right lets one element pair with itself.

5.1 The three variants

5.2 Why it works: sumZero

function sumZero(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === 0) return [arr[left], arr[right]];
    if (sum > 0) right--;
    else left++;
  }
}

With the array sorted: if arr[left] + arr[right] > 0, no pair using arr[right] can add up to 0 (any other left is even larger), so right is discarded. Symmetrically, if the sum is less than 0, left is discarded. Each step eliminates one candidate: n steps in total, O(n). This “I safely discard one candidate” argument is what you should explain in the interview.

5.3 Worked example: countUniqueValues

Pointer i marks the last unique value found; j explores. When arr[j] differs from arr[i], advance i and copy the new value there. At the end, the first i + 1 elements are the unique ones.

function countUniqueValues(arr) {
  if (arr.length === 0) return 0;
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1;
}

This version modifies the input (it is the LeetCode 26 Remove Duplicates technique). If you can't mutate, it is enough to count each time an element differs from the previous one:

function countUniqueValuesPure(arr) {
  let count = 0;
  for (let j = 0; j < arr.length; j++) {
    if (j === 0 || arr[j] !== arr[j - 1]) count++;
  }
  return count;
}

Both: O(n) timeO(1) space

5.4 Exercises

function averagePair(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const avg = (arr[left] + arr[right]) / 2;
    if (avg === target) return true;
    if (avg < target) left++;
    else right--;
  }
  return false;
}

isSubsequence('sing', 'sting')       // true
isSubsequence('abc', 'abracadabra')  // true
isSubsequence('abc', 'acb')          // false (order matters)

function isSubsequence(sub, str) {
  let i = 0;
  for (let j = 0; j < str.length && i < sub.length; j++) {
    if (sub[i] === str[j]) i++;
  }
  return i === sub.length;
}

function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}

5.5 Practice on LeetCode

• 167Two Sum II
• 125Valid Palindrome
• 26Remove Duplicates from Sorted Array
• 283Move Zeroes
• 11Container With Most Water
• 153Sum
• 88Merge Sorted Array
• 141Linked List Cycle (slow/fast, Floyd’s algorithm)

PATTERN 03 · CONTIGUOUS RANGES

6. Sliding Window

Maintain a “window” (a contiguous range [left, right]) over an array or string and update its state incrementally as it moves, instead of recomputing it from scratch. It only applies to contiguous subarrays/substrings.

Use it when

The question is about a contiguous subarray or substring: of size k, or the longest/shortest one that satisfies X.

Core idea

Keep the state of a window and update it as it slides instead of recomputing it from scratch.

Cost

O(n) time; O(1) memory for sums, O(k) for character maps.

Classic trap

The variable window only works with positive numbers; with negatives switch to prefix sums.

6.1 Fixed vs variable window

6.2 Fixed window: maxSubarraySum

The brute force recomputes every window from scratch:

// Naive version: recomputes every window, O(n · num)
function maxSubarraySumNaive(arr, num) {
  if (num > arr.length) return null;
  let max = -Infinity;
  for (let i = 0; i <= arr.length - num; i++) {
    let temp = 0; // writing "temp = 0" without let creates a global
    for (let j = 0; j < num; j++) temp += arr[i + j];
    max = Math.max(max, temp);
  }
  return max;
}

• It is O(n · num): consecutive windows share all but two elements, and that shared work is repeated.
• Declare the accumulator: writing temp = 0 without let creates an implicit global variable (and throws in strict mode or in ES modules).
• Define num <= 0: with num = 0 a careless version returns 0 even though the result isn't well defined. Agree with the interviewer on what to return.
• Initialize from real data: initializing maxSum with the sum of the first real window (not with 0) is what makes it work with negative numbers. Starting at maxSum = 0 is a classic bug.

Robust sliding-window version — add the element that enters, subtract the one that leaves:

function maxSubarraySum(arr, num) {
  if (num <= 0 || arr.length < num) return null;
  let windowSum = 0;
  for (let i = 0; i < num; i++) windowSum += arr[i];
  let maxSum = windowSum;
  for (let i = num; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - num];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

6.3 Variable window template

let left = 0;
for (let right = 0; right < arr.length; right++) {
  // 1. add arr[right] to the window state
  while (/* the window became invalid (or is already valid, if looking for the minimum) */) {
    // 2. (if looking for the minimum) update the answer here
    // 3. remove arr[left] from the state and advance left
    left++;
  }
  // 4. (if looking for the maximum) update the answer with right - left + 1
}

Each index enters the window once and leaves it once, so even though there is a while inside the for, the total is O(n), not O(n²). Interviewers ask about this often. Here is the template running on exercise 6.A:

6.4 Exercises

minSubArrayLen([2,3,1,2,4,3], 7)            // 2  -> [4,3]
minSubArrayLen([1,4,16,22,5,7,8,9,10], 39)  // 3  -> [16,22,5]
minSubArrayLen([1,4,16,22,5,7,8,9,10], 95)  // 0  -> none exists

function minSubArrayLen(nums, target) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

findLongestSubstring('rithmschool')    // 7  -> 'rithmsc'
findLongestSubstring('thisisawesome')  // 6  -> 'awesom'
findLongestSubstring('bbbbbb')         // 1

function findLongestSubstring(str) {
  const lastSeen = {}; // char -> last index
  let left = 0, longest = 0;
  for (let right = 0; right < str.length; right++) {
    const ch = str[right];
    if (lastSeen[ch] !== undefined && lastSeen[ch] >= left) {
      left = lastSeen[ch] + 1;
    }
    lastSeen[ch] = right;
    longest = Math.max(longest, right - left + 1);
  }
  return longest;
}

6.5 Practice on LeetCode

• 643Maximum Average Subarray I (fixed)
• 209Minimum Size Subarray Sum
• 3Longest Substring Without Repeating Characters
• 424Longest Repeating Character Replacement
• 567Permutation in String
• 438Find All Anagrams
• 76Minimum Window Substring (hard)

PATTERN 04 · HALVING

7. Divide and Conquer

Split the problem into smaller parts, solve each one (often recursively) and combine the results. The two canonical examples are binary search (one half is discarded: O(log n)) and merge sort (both halves are solved and combined: O(n log n)).

Use it when

The data is sorted, the condition is monotonic, or the problem splits naturally into halves.

Core idea

Discard half of the search space (binary search) or solve both halves and combine them (merge sort).

Cost

O(log n) for binary search; O(n log n) time and O(n) space for merge sort.

Classic trap

Off-by-one bounds: lo <= hi vs lo < hi, and lo = mid causing an infinite loop.

7.1 Bug-free binary search

Binary search is easy to understand and very easy to get wrong. The details that matter:

Precondition

The array must be sorted (or, more generally, the condition must be monotonic).

Invariant

If the value exists, it is inside [lo, hi]. Every branch must preserve this.

Closed interval

lo <= hi with hi = n - 1 to search for an exact value. Using < here would skip the single-element case.

Move past the middle

lo = mid + 1 / hi = mid - 1. Assigning lo = mid can cause an infinite loop.

Overflow

lo + Math.floor((hi - lo) / 2) is the safe form. In JS (lo + hi) / 2 doesn't overflow, but in Java/C++ it does; mentioning it earns points.

function search(arr, val) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < val) lo = mid + 1;
    else if (arr[mid] > val) hi = mid - 1;
    else return mid;
  }
  return -1;
}

7.2 Lower bound: the first position ≥ val

Many problems don't ask “is it there?” but “where is the first/last occurrence?” or “where would I insert it?”. The template with a half-open interval [lo, hi) handles all of those cases:

function lowerBound(arr, val) {
  let lo = 0, hi = arr.length; // [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < val) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

7.3 Exercises

function countZeroes(arr) {
  // arr: ones followed by zeros. We look for the first 0.
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === 1) lo = mid + 1;
    else hi = mid;
  }
  return arr.length - lo;
}

function sortedFrequency(arr, val) {
  const first = lowerBound(arr, val);
  if (first === arr.length || arr[first] !== val) return -1;
  return lowerBound(arr, val + 1) - first;
}

findRotatedIndex([6,7,8,9,1,2,3,4], 8)       // 2
findRotatedIndex([6,7,8,9,1,2,3,4], 3)       // 6
findRotatedIndex([37,44,66,102,10,22], 14)   // -1

function findRotatedIndex(arr, val) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === val) return mid;
    if (arr[lo] <= arr[mid]) {            // left half is sorted
      if (arr[lo] <= val && val < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                              // right half is sorted
      if (arr[mid] < val && val <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

7.4 Merge sort

The other side of divide and conquer: instead of discarding a half, solve both halves and combine them.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

There are log n levels of splitting and at each level merge processes n elements: O(n log n) time, O(n) space. The merge function is an example of Multiple Pointers over two sequences.

7.5 Binary search on the answer

When the problem asks for “the minimum value X such that a condition holds” and the condition is monotonic (if it holds for X, it holds for every larger value), you can binary search over the range of possible answers instead of over an array. Examples: LeetCode 875 Koko Eating Bananas, 1011 Capacity to Ship Packages, 69 Sqrt(x).

7.6 Practice on LeetCode

• 704Binary Search
• 35Search Insert Position
• 34First and Last Position
• 33Search in Rotated Sorted Array
• 153Find Minimum in Rotated Sorted Array
• 912Sort an Array (merge sort)
• 875Koko Eating Bananas

NEXT LEVEL

8. Beyond the core four

Dynamic Programming, Greedy and Backtracking show up as soon as problems involve choices; Prefix Sum quietly powers many array questions. Here is enough of each to recognize it and write a first solution.

8.1 Dynamic Programming (DP)

It applies when the problem can be expressed in terms of smaller subproblems that repeat (“overlapping subproblems”) and the optimal solution is built from the optimal solutions of the subproblems (“optimal substructure”). The idea: solve each subproblem only once and store the result.

Top-down (memoization)

Recursion + cache. Write the natural recursion first and add a memo object to it.

Bottom-up (tabulation)

Fill a table from the base cases upward. Avoids the risk of stack overflow.

Signals

“Number of ways to...”, “minimum/maximum cost to...”, “is it possible to reach...?”, sequential decisions.

Recipe

1) define the state (dp[i] = what it means), 2) the recurrence, 3) the base cases, 4) the computation order, 5) where the answer is.

function fibMemo(n, memo = {}) {
  if (n <= 2) return 1;
  if (memo[n]) return memo[n];
  return (memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo));
}

Without memo, recursive fibonacci is O(2ⁿ); with memo it is O(n). fibMemo(50) returns instantly.

Climbing Stairs (bottom-up)

function climbStairs(n) {
  let prev = 1, curr = 1; // ways to reach step 0 and step 1
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

Number of ways to climb n steps taking 1 or 2 at a time: ways(n) = ways(n-1) + ways(n-2). Since only the two previous values are used, space drops to O(1).

Coin Change

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

dp[a] = minimum number of coins to make amount a. O(amount · coins).

8.2 Greedy

At each step, take the decision that looks best locally, without going back. It is simple and fast, but only correct if you can justify that the local choice never prevents reaching the optimum.

Maximum number of non-overlapping intervals

function maxNonOverlapping(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // by end
  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) { count++; lastEnd = end; }
  }
  return count;
}

Sort by end and always take the one that ends first (it leaves the most free room). Correct and O(n log n).

Kadane’s algorithm

Another famous greedy algorithm: maximum subarray sum (LeetCode 53), which can also be seen as DP.

function maxSubarray(nums) {
  let best = nums[0], curr = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curr = Math.max(nums[i], curr + nums[i]);
    best = Math.max(best, curr);
  }
  return best;
}

8.3 Backtracking

Explore all candidate solutions by building them step by step, and “undo” the last choice to try the next one. It is used to generate combinations, permutations, subsets, or to solve puzzles (N-Queens, Sudoku). The complexity is exponential; the key is to prune branches that cannot lead to a valid solution.

function backtrack(state) {
  if (/* state is a complete solution */) { save(copy of state); return; }
  for (const option of validOptions(state)) {
    choose(option);        // modify state
    backtrack(state);      // explore
    undo(option);          // go back
  }
}

Subsets

function subsets(nums) {
  const result = [];
  const path = [];
  function backtrack(start) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);      // choose
      backtrack(i + 1);        // explore
      path.pop();              // undo
    }
  }
  backtrack(0);
  return result;
}

Permutations

function permutations(nums) {
  const result = [], path = [], used = new Array(nums.length).fill(false);
  function backtrack() {
    if (path.length === nums.length) { result.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      backtrack();
      path.pop(); used[i] = false;
    }
  }
  backtrack();
  return result;
}

Subsets: O(2ⁿ · n)Permutations: O(n! · n)

8.4 Prefix Sum

Precompute prefix[i] = sum of the first i elements; then the sum of any range [i, j] is prefix[j+1] - prefix[i] in O(1).

function rangeSums(nums) {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return (i, j) => prefix[j + 1] - prefix[i]; // sum of nums[i..j]
}

Combined with a Frequency Counter it solves “number of subarrays with sum k” even with negatives, which is exactly where Sliding Window fails:

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]); // prefix -> how many times
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

8.5 Other patterns you will meet later

CHEAT SHEET

9. How to recognize the pattern

The hardest part of an interview is not implementing the pattern, but realizing which one to use. Walk this decision chain from the most specific signal to the most general:

And the same signals as a reference table:

MAKE IT STICK

10. Practice plan

10.1 How to practice each problem

1. Simulate the interview. Read the problem and apply the 5 steps out loud (or in writing), as if there were an interviewer.
2. Use a timer. 25 minutes for an easy/medium problem. If you didn't get it, look at just one hint (the pattern's name), and take 10 more minutes.
3. Rewrite from memory. If you read the solution, close it and rewrite it from memory the next day.
4. Keep a log. Problem, pattern, mistake you made, Big O. Review the log every week.
5. Space your repetitions. Solve each problem again after 3, 7 and 21 days.

10.2 A two-week plan

10.3 Resources

• George Polya, How to Solve It (1945) — the source of the five-step strategy in section 2.
• Colt Steele, JavaScript Algorithms and Data Structures Masterclass — the course this guide grew out of; the exercises follow its practice set.
• LeetCode (leetcode.com) — the problem numbers cited in each section. The NeetCode 150 list (neetcode.io) organizes problems by pattern.
• Gayle Laakmann McDowell, Cracking the Coding Interview — chapters on Big O and interview technique.
• Big-O Cheat Sheet (bigocheatsheet.com) — complexities of data structures and sorting algorithms.
• VisuAlgo (visualgo.net) — step-by-step visualizations of searching, sorting and more.