02 — Pattern Recognition at Speed

The difference between a solver who grinds for 45 minutes and one who sees the structure in 3 minutes isn’t intelligence — it’s a trained pattern-matching reflex built over hundreds of problems. You don’t need to be faster at thinking. You need to recognize that you’ve seen this shape before. This file builds that recognition system.

The 3-Second Glance

Before reading anything else, your eyes should land on three things in the first 3 seconds of opening any problem:

  1. Constraints — what’s the scale? (n = ?, time limit?)

  2. Input/output type — array of integers? graph edges? strings? tree?

  3. What you’re optimizing or counting — minimum cost? all subsets? number of paths?

These three signals eliminate 80% of possible algorithms before you’ve read the problem body. Train yourself to do this automatically. After that, read the problem carefully. But those 3 seconds set your hypothesis before you read.

Constraints as Algorithmic Clues

This is the single most high-leverage pattern recognition skill in competitive programming. Constraints are not just limits — they’re hints. Problem setters choose constraints to make exactly one complexity class work.

Constraint

Implied Complexity

Typical Algorithms

n ≤ 10

O(n!)

Full backtracking, permutation search

n ≤ 20

O(2ⁿ)

Bitmask DP, meet-in-the-middle

n ≤ 100

O(n³) or O(2ⁿ)

Floyd-Warshall, DP on subsets

n ≤ 500

O(n³)

Interval DP, matrix DP

n ≤ 5,000

O(n²)

Pairwise DP, O(n²) greedy

n ≤ 10⁵

O(n log n)

Sort, segment tree, Dijkstra, BFS/DFS

n ≤ 10⁶

O(n)

Linear DP, two pointers, sliding window

n ≤ 10⁹

O(log n) or O(1)

Binary search on answer, math

Multiple test cases, large n

O(n) total

Amortized structures, offline processing

How to use this in practice: When you read n ≤ 5000 and you’re thinking O(n log n), stop — you’re probably overthinking it. An O(n²) solution will pass. When you see n ≤ 10⁹ and you’re thinking O(n), you’re wrong — there’s no way to iterate that many elements.

Keyword-to-Pattern Map

Problem statements use language patterns that map reliably to algorithmic families. This is community-tested over decades of competitive programming. The map below is a starting point — your job is to extend it with your own solved problem history.

Keyword / Phrase

Most Likely Pattern

Secondary Possibility

“minimum cost to reach”

DP or Dijkstra

Greedy (if structure allows)

“maximum subarray / subarray sum”

Kadane’s / prefix sums

Segment tree for range queries

“all possible / enumerate all”

Backtracking

Bitmask DP (if n ≤ 20)

“shortest path / minimum steps”

BFS (unweighted) / Dijkstra (weighted)

DP on DAG

“count the number of ways”

DP

Combinatorics / math

“count subsets with property”

DP (subset sum family)

Bitmask for small n

“connected components”

Union-Find or DFS/BFS

—

“next greater / previous smaller”

Monotonic stack

—

“sliding window / subarray of length k”

Two pointers / sliding window

—

“k-th largest / median”

Heap / binary search

Quickselect

“longest increasing subsequence”

DP O(n²) or patience sorting O(n log n)

—

“interval scheduling / overlap”

Greedy (sort by end time)

Sweep line

“range sum / range update queries”

Segment tree / BIT

Prefix sums (if static)

“cycle detection in graph”

DFS (coloring) / Union-Find

Floyd’s algorithm (linked list)

“topological order / dependency”

Topological sort (Kahn’s or DFS)

—

“palindrome / symmetric”

DP (interval) / two pointers

Manacher’s (if O(n) needed)

“string matching / find pattern”

KMP / Z-function

Rabin-Karp

“minimum spanning tree”

Kruskal / Prim

—

“number of distinct / unique”

Hash map / sorting

Trie (if prefix-based)

“can we achieve X?” (binary answer)

Binary search on answer

DP feasibility

How to Build Your Own Keyword-to-Pattern Map

The table above is generic. Yours will be better — because it’ll reflect the exact mistakes you’ve made. Here’s the process:

After every problem you solve (or upsolve):

  1. Write the problem title and one sentence describing what it was asking.

  2. Note which pattern solved it.

  3. Note which keyword or constraint SHOULD have pointed you there.

  4. If you missed it, write what you were thinking instead.

Over 3 months, this becomes a personalized lookup table worth more than any generic resource. Store it in lab_notebook/pattern_map.md in your repo.

Review it before every contest. Five minutes of pattern review before competing is worth more than 30 minutes of problem-solving review. You’re priming the associative network, not cramming algorithms.

The “Why Isn’t This O(n²)?” Reflex

Every time you have an O(n²) solution, ask yourself this question before moving on:

“Is there a monotonic structure, a sorted order, or a prefix property I’m ignoring?”

This single question has a historically high hit rate for unlocking O(n log n) or O(n) solutions:

  • Monotonic stack: eliminates the inner loop in “next greater element” class problems

  • Two pointers: eliminates the inner loop in “pair with target sum” or “sliding window” problems

  • Binary search: eliminates the inner loop when one dimension is sorted

  • Prefix sums: eliminates the inner loop in subarray sum queries

  • Sorting + greedy: turns O(n²) comparisons into a single sorted pass

When you’re stuck at O(n²) and the constraint says n ≤ 10⁵, your problem is almost always in one of these five buckets.

What Most People Get Wrong

Most people try to recognize patterns by memorizing algorithms. That’s the wrong unit of analysis.

The correct unit is problem shape. Shapes are:

  • “I have a sorted sequence and I’m looking for a boundary” → binary search

  • “I have a sequence and I need the best sub-structure” → DP

  • “I have events in time and I need to track active intervals” → sweep line / heap

Algorithms are implementations. Shapes are recognition cues. Memorize shapes, not code.

The second mistake: people read the problem statement before looking at constraints. Flip the order. Constraints first, then statement. The constraints tell you the budget; the statement tells you the specifics. Budget first, then plan.

Recognition Speed Drill

Once a week, spend 15 minutes on this drill — not solving problems, just identifying them:

  1. Open 5 random problems at your target difficulty.

  2. For each: read only the title and constraints (not the problem body).

  3. Write down your hypothesis: what algorithm family does this look like?

  4. Then read the problem and check if you were right.

  5. Log mismatches.

This trains the 3-second glance as an isolated skill. It compounds fast.