Day 28: Pattern Recognition Masterclass

DAY 28 / 30 · WEEK 4

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.

Signal in the problem	Pattern	Day
“pair that sums to X,” “two elements that…”	Hash Map (unsorted) or Two Pointer (sorted)	6 / 4
“longest/shortest/max/min … contiguous substring/subarray”	Sliding Window	5
“palindrome,” “reverse in place,” converging from both ends	Two Pointer	4
“frequency,” “anagram,” “duplicate,” “group by”	Hash Map / Set	6
“kth largest/smallest,” “top k,” a running min/max as data streams in	Heap	22
“in a sorted array,” “search space is monotonic”	Binary Search	12 / 13
“detect a cycle,” “find the middle” (linked list)	Fast/Slow Pointers	16
“valid parentheses/brackets,” “next greater element,” “undo”	Stack	17
“sliding window maximum,” “process in the order added”	Queue / Deque	18
“level order,” “shortest path (unweighted),” “fewest hops/steps”	BFS	19 / 24
“explore all paths,” “backtrack,” “all combinations/permutations”	DFS / Recursion	9 / 19 / 23
“inorder gives sorted order,” “predecessor/successor”	Binary Search Tree	20
“connections/network,” “islands,” “prerequisites”	Graph	23 / 24
“minimum/maximum ways to reach,” “count distinct ways”	Dynamic Programming	25 / 26
“fewest coins/jumps/cost,” “can I reach the end”	DP — check greedy-choice property before trusting greedy	25 / 26 / 27
“schedule non-overlapping,” “meeting rooms,” “activity selection”	Greedy	27

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.

Quiz 1

“Given a string, find the length of the longest substring without repeating characters.”

Answer: Sliding Window

Explanation: Signal: “longest … substring” + “without repeating” is a contiguous-range validity condition that can grow and shrink — the canonical sliding window shape (Day 5).

Quiz 2

“Given a sorted array, determine if a target value exists, in O(log n) time.”

Answer: Binary Search

Explanation: Signal: “sorted array” + “O(log n)” is the most direct binary search tell in the whole course (Day 12).

Quiz 3

“Given the head of a linked list, determine whether it has a cycle.”

Answer: Fast/Slow Pointers

Explanation: Signal: “linked list” + “has a cycle” is Day 16’s fast/slow-pointer problem almost verbatim — no extra memory needed for a single pass.

Quiz 4

“Given a binary tree, return its level-order traversal.”

Answer: BFS (Queue)

Explanation: Signal: “level-order” IS the definition of BFS (Day 19) — a queue processes one full depth before the next.

Quiz 5

“Given coin denominations and an amount, find the fewest coins needed to make it.”

Answer: Dynamic Programming

Explanation: Signal: “fewest coins” over reusable denominations is the exact Day 25/26 unbounded-DP shape — and Day 27 proved greedy is NOT safe here for arbitrary coin systems.

Quiz 6

“Given a list of intervals, find the minimum number to remove so the rest don’t overlap.”

Answer: Greedy (sort by end time)

Explanation: Signal: “minimum to remove so none overlap” is Day 27’s Non-overlapping Intervals almost exactly — sort by end time, provably safe greedy.

Quiz 7

“Given a grid of 1s and 0s, count the number of islands (connected groups of 1s).”

Answer: Graph BFS/DFS (treat the grid as a graph)

Explanation: Signal: a grid where adjacent cells connect is a graph in disguise — no explicit “graph” wording required (Day 23). Counting islands is counting connected components via BFS/DFS.

Quiz 8

“Given a stream of numbers arriving one at a time, continuously report the kth largest seen so far.”

Answer: Heap

Explanation: Signal: “continuously” + “kth largest” as data streams in is Day 22’s exact use case — a heap keeps the running answer available in O(log n) per insert, far cheaper than re-sorting on every new number.

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

Pattern	Typical time	Typical space	Day
Two Pointer	O(n)	O(1)	4
Sliding Window	O(n)	O(1) – O(k)	5
Hash Map / Set	O(n)	O(n)	6
Comparison sorting (merge/quick)	O(n log n)	O(1) – O(n)	8 / 10 / 11
Binary Search	O(log n)	O(1)	12 / 13
Recursion (naive / memoized)	O(2²) naive, O(n) memoized	O(n) call stack	9 / 25
Linked list op at a known node	O(1)	O(1)	15 / 16
Stack / Queue op	O(1)	O(n)	17 / 18
BFS / DFS traversal	O(V + E)	O(V)	19 / 23
BST search/insert (iterative)	O(h)	O(1)	20
Heap insert/extract	O(log n)	O(n)	22
Graph shortest path (unweighted) / topo sort	O(V + E)	O(V)	24
Dynamic Programming (1D)	O(n) – O(n × options)	O(1) – O(n)	25 / 26
Greedy	O(n log n) (sort-dominated)	O(1) – O(n)	27

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

1. Product of Array Except Self

Medium — LeetCode: Product of Array Except Self

Given an array, return an array where each element is the product of every OTHER element, without using division. Keyword-only pattern-matching (“array,” “product”) could mislead toward a hash map — the real signal is “combine information from both sides,” which points to a prefix/suffix pass instead.

Hint: Build the answer in two passes: first, a left-to-right pass where each position holds the product of everything to its left. Then a right-to-left pass multiplies in the product of everything to its right. No division needed.

Solution:

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;
}

2. 3Sum Closest

Medium — LeetCode: 3Sum Closest

Given an array and a target, find the sum of 3 numbers closest to the target. The exact same sort-then-two-pointer shape as Day 11’s 3Sum practice problem — the only change is the termination condition (closest, not exact).

Hint: Sort first. Fix one number, then two-pointer the rest of the array converging toward the target — same skeleton as 3Sum, but instead of stopping the instant you find an exact match, track the closest sum seen so far and keep narrowing.

Solution:

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;
}

3. Word Search

Medium — LeetCode: Word Search

Given a grid of letters and a word, return whether the word can be traced through adjacent cells (up/down/left/right), using each cell at most once. Never labeled a “graph” or a “tree” — but a grid with adjacency IS a graph, and “trace a path” IS DFS with backtracking.

Hint: DFS from every cell that matches the word’s first letter. At each step, temporarily mark the current cell as visited (so the path can’t reuse it), recurse into all 4 neighbors looking for the next letter, then un-mark it on the way back out — classic backtracking.

Solution:

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

Question 1

What’s the first question to ask when recognizing a pattern in a cold problem?

Answer: What’s the data shape, then what’s the goal/constraint phrasing?

Explanation: Identify the data shape first (array, linked structure, tree, graph, or no explicit structure), then the goal/constraint phrasing (contiguous? sorted? min/max repeatedly? count of ways?) — matching both together narrows to a specific pattern far faster than guessing from keywords alone.

Question 2

What’s the key differentiator between sliding window and two-pointer?

Answer: Sliding window maintains a contiguous range with a shrink/grow condition; two-pointer just converges from both ends

Explanation: Sliding window maintains a CONTIGUOUS range with a validity condition that grows/shrinks as you scan; two-pointer converges from both ends and doesn’t require the elements between the pointers to form a meaningful contiguous span.

Question 3

The phrase “rearrange the characters” in a problem statement rules out which kinds of patterns?

Answer: Order-dependent patterns like two-pointer and sliding window — only counts matter now

Explanation: If a problem explicitly says characters/elements can be REARRANGED, order no longer matters — that rules out order-dependent patterns like two-pointer and sliding window, and points toward frequency counting (hash map) instead.

Question 4

True or false: a problem can be graph-shaped even if it never uses the word “graph.”

Answer: True

Explanation: Any set of entities with arbitrary connections — friend networks, course prerequisites, grid adjacency — is a graph whether or not the problem ever uses that word. Recognizing the implicit node/edge structure is the whole skill.

Question 5

When should you fall back to brute force during pattern recognition?

Answer: When you can’t identify the pattern in the first minute — its specific inefficiency usually reveals the right pattern

Explanation: When you can’t identify the pattern in the first minute, state the brute-force approach and its complexity out loud — the specific inefficiency it reveals (repeated work, unordered comparisons, unbounded search) usually points directly at the pattern that removes it.