Skip to main content

​
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. Pattern Recognition Flow

​
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

3-Step Recognition
1

Read the Constraint

The constraint is the FIRST clue to the algorithm.
2

Identify the Question Type

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

Match the Pattern

Combine constraint + question type = algorithm pattern.

​
Constraint → Algorithm Map

​
The Golden Table

Constraint to Algorithm Map
Constraint (n)Max OperationsLikely Algorithm
n ≤ 1010! = 3.6MBrute force, permutations, backtracking
n ≤ 202²⁰ = 1MBitmask DP, subset enumeration
n ≤ 100n³ = 1MFloyd-Warshall, O(n³) DP
n ≤ 500n³ = 125MO(n²) with optimization
n ≤ 5,000n² = 25MO(n²) DP, all pairs
n ≤ 10⁵n log nSorting, 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…”

Optimization Patterns
What to OptimizeFirst TryIf TLE, Try
Max sum subarrayKadane’s O(n)Already optimal
Min cost pathDijkstra O(E log V)0-1 BFS if weights 0/1
Max flowFord-FulkersonDinic’s algorithm
Max matchingHungarian O(n³)Hopcroft-Karp O(E√V)
Min operationsBFSBinary 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 TypeAlgorithmComplexity
Kth smallest in arraynth_element / quickselectO(n)
Kth smallest in sorted arraysBinary searchO(log(min(m,n)))
Kth smallest in BSTIn-order traversalO(k)
Kth smallest sumPriority queueO(k log k)

​
Keyword → Algorithm Triggers

Keyword Triggers

​
Instant Recognition Keywords

Keyword in ProblemAlgorithm 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

​
Array Patterns

Array Pattern Recognition 
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

Array Problem 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:
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

ConstraintYour Answer
n ≤ 15?
n ≤ 1000, find shortest path?
n ≤ 10⁵, range sum queries?
n ≤ 10⁶, single pass required?
n ≤ 10¹⁸, compute nth Fibonacci?
ConstraintAlgorithm
n ≤ 15Bitmask DP, brute force
n ≤ 1000, find shortest pathFloyd-Warshall O(n³) or BFS/Dijkstra
n ≤ 10⁵, range sum queriesPrefix sum or Segment tree
n ≤ 10⁶, single pass requiredO(n) linear scan, two pointers
n ≤ 10¹⁸, compute nth FibonacciMatrix 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! 🏆