> ## Documentation Index > Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt > Use this file to discover all available pages before exploring further. # Pattern Recognition > Learn to instantly recognize common problem patterns and select the right algorithm export const Icon = ({icon}) => { const iconMap = { 'calendar-check': 'πŸ“…', 'sun': 'β˜€οΈ', 'stopwatch': '⏱️', 'clock': 'πŸ•', 'bug': 'πŸ›', 'heart-pulse': 'πŸ’“', 'moon': 'πŸŒ™', 'trophy': 'πŸ†', 'chart-line': 'πŸ“ˆ', 'list-check': 'βœ…', 'book': 'πŸ“–', 'brain': '🧠', 'pencil': '✏️', 'database': 'πŸ—„οΈ', 'chart-pie': 'πŸ“Š', 'shield': 'πŸ›‘οΈ', 'clipboard': 'πŸ“‹', 'bolt': '⚑', 'graduation-cap': 'πŸŽ“', 'eye': 'πŸ‘οΈ', 'ruler': 'πŸ“', 'search': 'πŸ”', 'wand-magic-sparkles': '✨', 'diagram-project': 'πŸ“', 'sitemap': 'πŸ—ΊοΈ', 'dumbbell': 'πŸ‹οΈ', 'toolbox': '🧰', 'calculator': 'πŸ”’', 'list-ol': 'πŸ“', 'magnifying-glass': 'πŸ”', 'tree': '🌳', 'table': 'πŸ“Š', 'layer-group': 'πŸ“š', 'shuffle': 'πŸ”€' }; return {iconMap[icon] || 'πŸ“Œ'}; }; # 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 The constraint is the FIRST clue to the algorithm. What are they asking? Count, optimize, find, check? Combine constraint + question type = algorithm pattern. *** ## Constraint β†’ Algorithm Map ### The Golden Table Constraint to Algorithm Map | 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..." **Technique:** Prefix sum + hashmap ```cpp theme={null} // "Count subarrays with sum = k" map 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]++; } ``` **Technique:** DP (usually 1D or 2D) ```cpp theme={null} // "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 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..." **Technique:** Binary search on answer ```cpp theme={null} // "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; ``` **Technique:** DFS/BFS or DP ```cpp theme={null} // "Can we reach target?" bool dfs(int node, int target, vector& 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 Keyword 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 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 | 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 | ? | | 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!** πŸ†