Lesson 42.1 · Pattern Recognition Drills
From Clue to Pattern
Ask three questions in order: what shape is the input, what kind of answer is wanted, and how large is n. Together they narrow dozens of patterns to two or three.
14 min
Think of it like this
A doctor doesn't run every test on every patient: the symptoms point to a short list of likely causes, and a couple of checks settle it. Problem wording is the symptom list.
1.Three questions
1. Input shape. Sorted array → binary search or two pointers. Unsorted array with sums or counts → hashing, prefix sums, sliding window. String with a window or anagram → sliding window + counts. Linked list → pointers. Tree → DFS/BFS. Grid or "connections" → graph. Intervals → sort + sweep. Stream → heap or monotonic structure.
2. Kind of answer. "Number of ways", "minimum cost", "can you" over choices → DP (or greedy with a proof). "All combinations / permutations" → backtracking. "Shortest / fewest steps" → BFS (unweighted) or Dijkstra. "Top / k-th" → heap or quickselect. "Next greater / smaller" → monotonic stack. "Order with dependencies" → topological sort. "Groups / connected" → union-find or DFS.
3. Constraint size sets the time budget (next lesson). If the obvious idea is too slow for n, look for the faster pattern in the same family.
Remember
- Shape, then question, then size.
- Write down two candidate patterns, then rule one out.
- Every course module lists the clue words for its patterns.
Common mistakes
- Jumping to code after recognising a familiar-looking word without checking the constraints.
Words used in this lesson
- Signal
- A word or shape in the problem that points to a pattern ("contiguous", "sorted", "k-th", "dependencies").