Pattern Recognition

The fastest competitive programmers don’t think harder—they recognize patterns faster. This chapter trains your pattern recognition to instantly spot which technique to apply.

The Recognition Framework

The Secret: After solving 500+ problems, you stop “solving” and start “recognizing.” This chapter gives you shortcuts to that recognition.

The 3-Step Recognition Process

Read the Constraint

The constraint is the FIRST clue to the algorithm.

Identify the Question Type

What are they asking? Count, optimize, find, check?

Match the Pattern

Combine constraint + question type = algorithm pattern.

Constraint → Algorithm Map

The Golden Table

Constraint (n)	Max Operations	Likely Algorithm
n ≤ 10	10! = 3.6M	Brute force, permutations, backtracking
n ≤ 20	2²⁰ = 1M	Bitmask DP, subset enumeration
n ≤ 100	n³ = 1M	Floyd-Warshall, O(n³) DP
n ≤ 500	n³ = 125M	O(n²) with optimization
n ≤ 5,000	n² = 25M	O(n²) DP, all pairs
n ≤ 10⁵	n log n	Sorting, binary search, segment tree
n ≤ 10⁶	O(n)	Linear scan, two pointers, prefix sum
n ≤ 10⁹	O(log n)	Binary search, math formula
n ≤ 10¹⁸	O(1) or O(log n)	Math formula, matrix exponentiation

Question Type Patterns

Pattern 1: “Count the number of…”

Count subarrays with property

Technique: Prefix sum + hashmap

// "Count subarrays with sum = k"
map<int, int> prefix_count;
prefix_count[0] = 1;
int sum = 0, count = 0;
for (int x : arr) {
    sum += x;
    count += prefix_count[sum - k];
    prefix_count[sum]++;
}

Count subsequences with property

Technique: DP (usually 1D or 2D)

// "Count increasing subsequences of length k"
// dp[i][j] = count ending at i, length j
for (int i = 0; i < n; i++) {
    dp[i][1] = 1;
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            for (int k = 2; k <= K; k++) {
                dp[i][k] += dp[j][k-1];
            }
        }
    }
}

Pattern 2: “Find the maximum/minimum…”

What to Optimize	First Try	If TLE, Try
Max sum subarray	Kadane’s O(n)	Already optimal
Min cost path	Dijkstra O(E log V)	0-1 BFS if weights 0/1
Max flow	Ford-Fulkerson	Dinic’s algorithm
Max matching	Hungarian O(n³)	Hopcroft-Karp O(E√V)
Min operations	BFS	Binary search on answer

Pattern 3: “Check if possible…”

Can we achieve X?

Technique: Binary search on answer

// "Can we split array into k parts 
// with max sum ≤ mid?"
int lo = max_element, hi = total_sum;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (canSplit(arr, k, mid)) {
        hi = mid;
    } else {
        lo = mid + 1;
    }
}
return lo;

Does path/assignment exist?

Technique: DFS/BFS or DP

// "Can we reach target?"
bool dfs(int node, int target, 
         vector<bool>& visited) {
    if (node == target) return true;
    visited[node] = true;
    for (int next : adj[node]) {
        if (!visited[next] && 
            dfs(next, target, visited)) {
            return true;
        }
    }
    return false;
}

Pattern 4: “Find the kth…”

Problem Type	Algorithm	Complexity
Kth smallest in array	nth_element / quickselect	O(n)
Kth smallest in sorted arrays	Binary search	O(log(min(m,n)))
Kth smallest in BST	In-order traversal	O(k)
Kth smallest sum	Priority queue	O(k log k)

Keyword → Algorithm Triggers

Instant Recognition Keywords

Keyword in Problem	Algorithm to Consider
”subarray sum”	Prefix sum, sliding window, kadane
”longest increasing”	DP, binary search + DP
”shortest path”	BFS (unweighted), Dijkstra (weighted)
“number of ways”	DP, combinatorics
”partition into k”	Binary search on answer
”lexicographically smallest”	Greedy, trie
”connected components”	DFS, DSU
”minimum spanning tree”	Kruskal, Prim
”all pairs”	Floyd-Warshall, n × Dijkstra
”parentheses/brackets”	Stack
”intervals/meetings”	Sort by end, greedy
”palindrome”	Two pointers, DP, Manacher
”permutation”	Factorial, backtracking
”subset”	Bitmask, DP
”modulo 10^9+7”	DP (count), use mod everywhere

Visual Pattern Gallery

Array Patterns

PATTERN: Contiguous subarray with property
SIGNALS: "subarray", "contiguous", "consecutive"
TECHNIQUES: 
  - Prefix sum (sum queries)
  - Sliding window (fixed or variable size)
  - Two pointers (sorted or special property)
  - Monotonic deque (min/max in window)

PATTERN: Find elements with relationship
SIGNALS: "pair", "triplet", "two numbers that"
TECHNIQUES:
  - Sort + two pointers
  - Hashmap for complement
  - Binary search after sorting

Tree Patterns

PATTERN: Path queries on tree
SIGNALS: "path between nodes", "distance", "LCA"
TECHNIQUES:
  - DFS for simple paths
  - Binary lifting for LCA
  - HLD for path updates

PATTERN: Subtree queries
SIGNALS: "sum in subtree", "count in subtree"
TECHNIQUES:
  - DFS in/out times
  - Euler tour + range queries

Graph Patterns

PATTERN: Shortest path
SIGNALS: "minimum distance", "fewest steps"
TECHNIQUES:
  - BFS (unweighted)
  - Dijkstra (positive weights)
  - Bellman-Ford (negative weights)
  - 0-1 BFS (weights 0 or 1)

PATTERN: Cycle detection
SIGNALS: "cycle", "loop", "circular dependency"
TECHNIQUES:
  - DFS with colors (directed)
  - Union-Find (undirected)
  - Check if edges ≥ vertices in component

Decision Trees for Common Problems

”Given an array…” Decision Tree

Q: What are you asked to find?
├── Sum/XOR of subarray?
│   ├── Single query → Prefix sum/XOR
│   └── Multiple queries → Prefix sum array
│
├── Maximum/Minimum in range?
│   ├── Static array → Sparse table
│   └── Updates allowed → Segment tree
│
├── Longest subarray with property?
│   ├── Two-pointer property → Two pointers
│   └── Complex property → DP
│
├── Number of subarrays with property?
│   ├── Sum = k → Hashmap + prefix sum
│   ├── Fixed length → Sliding window
│   └── Other → DP or combinatorics
│
└── Reorder/partition array?
    ├── Minimize max → Binary search on answer
    └── Specific order → Greedy or DP

”Given a string…” Decision Tree

Q: What are you asked to find?
├── Substring matching?
│   ├── Single pattern → KMP, Z-algorithm
│   └── Multiple patterns → Aho-Corasick, trie
│
├── Palindrome questions?
│   ├── Check palindrome → Two pointers
│   ├── Longest palindrome → DP, Manacher
│   └── Count palindromes → DP
│
├── Lexicographically smallest/largest?
│   ├── By deletion → Stack-based greedy
│   └── By rearrangement → Sort characters
│
└── Edit distance/similarity?
    └── DP (LCS, edit distance)

Pattern Recognition Drills

Drill 1: Speed Classification

Read each problem description and identify the pattern in under 10 seconds:

Problem Set (Click to expand)

P1: “Given an array of n integers, find the number of pairs (i,j) where i < j and a[i] + a[j] = k.”

Pattern: Two Sum → Hashmap

P2: “Given a binary tree, find the maximum path sum from any node to any node.”

Pattern: Tree DP → DFS with return value

P3: “Given n intervals, find the minimum number of points such that each interval contains at least one point.”

Pattern: Interval covering → Sort by end + greedy

P4: “Given a string, find the longest palindromic substring.”

Pattern: Palindrome → DP or expand from center

P5: “Given a weighted graph, find if negative cycle exists.”

Pattern: Negative cycle → Bellman-Ford

P6: “Given array, answer queries for minimum in range [l,r].”

Pattern: Range min query → Sparse table or segment tree

P7: “Given n items with weight and value, maximize value with capacity W.”

Pattern: 0/1 Knapsack → 2D DP

P8: “Given a sequence, count inversions (pairs where i < j but a[i] > a[j]).”

Pattern: Inversions → Merge sort or BIT

Drill 2: Constraint → Algorithm

Constraint	Your Answer
n ≤ 15	?
n ≤ 1000, find shortest path	?
n ≤ 10⁵, range sum queries	?
n ≤ 10⁶, single pass required	?
n ≤ 10¹⁸, compute nth Fibonacci	?

Answers

Constraint	Algorithm
n ≤ 15	Bitmask DP, brute force
n ≤ 1000, find shortest path	Floyd-Warshall O(n³) or BFS/Dijkstra
n ≤ 10⁵, range sum queries	Prefix sum or Segment tree
n ≤ 10⁶, single pass required	O(n) linear scan, two pointers
n ≤ 10¹⁸, compute nth Fibonacci	Matrix exponentiation

Quick Reference Cheat Sheet

One-Liner Pattern Recognition

Array + Sum → Prefix Sum
Array + Sorted + Target → Two Pointers / Binary Search
Array + Window Property → Sliding Window
Array + Subsequence → DP

String + Match → KMP / Hashing
String + Palindrome → DP / Manacher
String + Lexicographic → Greedy / Trie

Graph + Shortest → BFS (unweighted) / Dijkstra (weighted)
Graph + Connectivity → DFS / DSU
Graph + Minimum cost → MST (Kruskal/Prim)
Graph + Flow → Ford-Fulkerson / Dinic

Tree + Path → DFS
Tree + LCA → Binary Lifting
Tree + Subtree → Euler Tour

"Number of ways" → DP + mod
"Minimum steps" → BFS
"Is it possible" → Binary Search on Answer
"Maximum subset" → DP / Greedy

Pattern recognition is a skill that develops with practice.Every problem you solve adds to your pattern library. After 500 problems, you’ll look at a new problem and think “Oh, this is just [pattern] with a twist.”Keep solving. Keep recognizing. Keep winning! 🏆

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Pattern Recognition

Pattern Recognition

The Recognition Framework

The 3-Step Recognition Process

Constraint → Algorithm Map

The Golden Table

Question Type Patterns

Pattern 1: “Count the number of…”

Count subarrays with property

Count subsequences with property

Pattern 2: “Find the maximum/minimum…”

Pattern 3: “Check if possible…”

Can we achieve X?

Does path/assignment exist?

Pattern 4: “Find the kth…”

Keyword → Algorithm Triggers

Instant Recognition Keywords

Visual Pattern Gallery

Array Patterns

Tree Patterns

Graph Patterns

Decision Trees for Common Problems

”Given an array…” Decision Tree

”Given a string…” Decision Tree

Pattern Recognition Drills

Drill 1: Speed Classification

Drill 2: Constraint → Algorithm

Quick Reference Cheat Sheet

One-Liner Pattern Recognition

​ Pattern Recognition

​ The Recognition Framework

​The 3-Step Recognition Process

​ Constraint → Algorithm Map

​The Golden Table

​ Question Type Patterns

​Pattern 1: “Count the number of…”

Count subarrays with property

Count subsequences with property

​Pattern 2: “Find the maximum/minimum…”

​Pattern 3: “Check if possible…”

Can we achieve X?

Does path/assignment exist?

​Pattern 4: “Find the kth…”

​ Keyword → Algorithm Triggers

​Instant Recognition Keywords

​ Visual Pattern Gallery

​Array Patterns

​Tree Patterns

​Graph Patterns

​ Decision Trees for Common Problems

​”Given an array…” Decision Tree

​”Given a string…” Decision Tree

​ Pattern Recognition Drills

​Drill 1: Speed Classification

​Drill 2: Constraint → Algorithm

​ Quick Reference Cheat Sheet

​One-Liner Pattern Recognition

Pattern Recognition

The Recognition Framework

The 3-Step Recognition Process

Constraint → Algorithm Map

The Golden Table

Question Type Patterns

Pattern 1: “Count the number of…”

Pattern 2: “Find the maximum/minimum…”

Pattern 3: “Check if possible…”

Pattern 4: “Find the kth…”

Keyword → Algorithm Triggers

Instant Recognition Keywords

Visual Pattern Gallery

Array Patterns

Tree Patterns

Graph Patterns

Decision Trees for Common Problems

”Given an array…” Decision Tree

”Given a string…” Decision Tree

Pattern Recognition Drills

Drill 1: Speed Classification

Drill 2: Constraint → Algorithm

Quick Reference Cheat Sheet

One-Liner Pattern Recognition