DAY 28 / 30 · WEEK 4

Pattern Recognition Masterclass

Goal of the day

• Learn to recognize, from a cold problem statement with no day label attached, which of the 12+ patterns from this course actually applies — the real skill an interview tests, more than any single memorized algorithm.
• Build a signal-words reference connecting common problem phrasing directly to a pattern, so recognition becomes fast and automatic instead of a guessing game.
• Drill recognition on unlabeled problem statements, then apply the process to 3 new problems.

Concept

Days 1 through 27 each taught "here is how pattern X works" — and each one came with the single biggest hint of all: the day number itself told you which pattern to use before you'd even read the problem. A real interview strips that hint away completely. You get a paragraph of prose and a blank editor, and the actual test is whether you can look at that paragraph and know, within the first minute, which toolbox to open. Closing that gap — cold recognition, not just "I remember how sliding window works when someone tells me it's a sliding window problem" — is the single highest-leverage thing left to practice.

A reliable 3-step process gets you there:

1. What's the data shape? A flat array/string, a linked chain, a tree/BST, a general graph (nodes with arbitrary connections), or no explicit structure at all — just a sequence of decisions to make (that last one is usually DP or greedy territory).
2. What's the goal/constraint phrasing? Contiguous range? Already sorted, or benefits from being sorted? Need the current min/max repeatedly? Counting distinct ways? Reachability (yes/no)? An optimal sequence of choices?
3. Match shape + goal to the narrowest pattern that fits, and sanity-check against the signal words below.

One honest caveat: some problems deliberately combine two patterns, and this course has built several of them on purpose — Day 14's quickselect (partition + halving), Day 21's BST validation (a stack doing a tree traversal's job), Day 26/27's coin change (the exact same problem, correct under DP, wrong under greedy). Recognition isn't always "pick the one right answer" — sometimes it's "which two patterns compose, and in what order."

Diagram: the master dispatch — which week's toolkit do I need?

Signal words — problem phrasing → pattern

This is the fast lookup table for the 30-second recognition window. Scan for the phrase, not the exact wording — interviewers rarely use these words verbatim, but the underlying signal is the same.

Interactive: pattern recognition drill

8 unlabeled problem statements. Pick the pattern before checking the reasoning — this is the exact 30-second judgment call an interview asks for.

The code: every core template, side by side

Not one new algorithm today — the reference sheet of every pattern's minimal skeleton, so you can scan straight to the shape you need mid-interview.

// TWO POINTERS (Day 4) — converge from both ends
function twoPointerTemplate(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    // inspect arr[lo] and arr[hi], then narrow toward the middle
    if (/* need a bigger value */ false) lo++;
    else hi--;
  }
}

// SLIDING WINDOW (Day 5) — grow/shrink a contiguous range
function slidingWindowTemplate(arr) {
  let left = 0;
  for (let right = 0; right < arr.length; right++) {
    // expand the window to include arr[right]
    while (/* window is invalid */ false) {
      left++;                          // shrink from the left until valid again
    }
    // window [left, right] is valid here — record a result
  }
}

// HASH MAP FREQUENCY (Day 6) — count/lookup in O(1) amortized
function frequencyTemplate(arr) {
  const seen = new Map();
  for (const x of arr) seen.set(x, (seen.get(x) || 0) + 1);
  return seen;
}

// BINARY SEARCH — exact match (Day 12)
function binarySearchTemplate(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// BFS (Day 19/24) — level order or shortest path, uses a QUEUE
function bfsTemplate(start, getNeighbors) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length > 0) {
    const node = queue.shift();
    for (const next of getNeighbors(node)) {
      if (!visited.has(next)) { visited.add(next); queue.push(next); }
    }
  }
}

// DFS (Day 9/19/23) — full-depth exploration, recursion or an explicit STACK
function dfsTemplate(node, getNeighbors, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const next of getNeighbors(node)) dfsTemplate(next, getNeighbors, visited);
}

// DYNAMIC PROGRAMMING (Day 25/26) — cache overlapping subproblems
function dpTemplate(n) {
  const dp = new Array(n + 1).fill(0);
  // seed the base case(s) here
  for (let i = 1; i <= n; i++) {
    // dp[i] = combine(dp[i-1], dp[i-2], ...) — sum, max, or min, depending on the problem
  }
  return dp[n];
}

// GREEDY (Day 27) — sort by the property that makes the choice safe, then one pass
function greedyTemplate(items) {
  items.sort((a, b) => 0 /* the key that makes THIS greedy choice provably safe */);
  let result = 0;
  for (const item of items) {
    // make the locally-best choice and never revisit it
  }
  return result;
}

Worked example: applying the 3-step process cold

Problem: "Given a string, return true if you can rearrange its characters to form a palindrome."

1. Data shape: a flat string — Week 1 territory.
2. Goal phrasing: "can be rearranged" is the key word. It explicitly says order doesn't matter — which immediately rules out two-pointer and sliding window (both depend on position/order). If order is irrelevant and only counts matter, that's a hash map / frequency-counting signal (Day 6).
3. Match: a string's characters can be rearranged into a palindrome if and only if at most one character has an odd count (that lone odd-count character sits in the middle; every other character needs an even count to mirror on both sides).

function canFormPalindrome(s) {
  const freq = new Map();
  for (const ch of s) freq.set(ch, (freq.get(ch) || 0) + 1);
  let oddCount = 0;
  for (const count of freq.values()) if (count % 2 !== 0) oddCount++;
  return oddCount <= 1;
}
// canFormPalindrome("civic") -> true (already a palindrome)
// canFormPalindrome("ivicc") -> true (rearranges to "civic")
// canFormPalindrome("hello") -> false (too many odd-count characters)

Complexity — every pattern from the course, at a glance

Interview corner

• What do you do when a problem seems to fit two patterns at once? Name both out loud, then let whichever constraint is hardest to satisfy drive the choice. If a hash map and a two-pointer sweep would both technically work but the array isn't sorted and sorting it first would cost more than the hash map's O(n) space is worth, the hash map wins — say that trade-off explicitly rather than silently picking one.
• What's the biggest tell that a problem is graph-shaped, even when it's never drawn as one? Any time entities have connections to each other that aren't a strict parent-child hierarchy — friend networks, course prerequisites, word ladders, grid adjacency — model it as nodes and edges even if the word "graph" never appears in the prompt. A grid where you can move to adjacent cells is a graph with implicit edges.
• How do you avoid pattern-matching too early and missing a simpler approach? Treat your first guess as a hypothesis, not a commitment — trace it against the example given in the problem before writing real code.
  ⚠ Trap: this is exactly the discipline Day 27 taught with the coin-change counter-example — a plausible-looking greedy guess can pass the given example and still be wrong. Always hand-trace before committing.
• What if you genuinely can't identify the pattern in the first minute? Fall back to brute force, state its complexity out loud, and look for the specific inefficiency: work that repeats (memoize or hash it), comparisons that could be skipped if the data were ordered (sort or two-pointer it), or a search space that's monotonic (binary search it).
  ↳ Common follow-up: "So brute force is a valid thing to say out loud?" — yes, always. Naming the brute force and its complexity, then explaining what's wasteful about it, is a stronger interview signal than sitting silently searching for the "clever" answer.

3 more problems — recognize first, then solve

function productExceptSelf(nums) {
  const n = nums.length;
  const res = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    res[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= suffix;
    suffix *= nums[i];
  }
  return res;
}

function threeSumClosest(nums, target) {
  nums = nums.slice().sort((a, b) => a - b);
  let closest = nums[0] + nums[1] + nums[2];
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum;
      if (sum === target) return sum;
      else if (sum < target) lo++;
      else hi--;
    }
  }
  return closest;
}

function wordExist(board, word) {
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;

    const original = board[r][c];
    board[r][c] = '#';                 // mark visited so this path can't reuse it
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
               || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = original;            // un-mark on the way back out (backtrack)
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Quiz