> ## 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 # πŸ‘οΈ 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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/pattern-recognition.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=673e145fb84ed8e4ad2ef8469fbcb3a4) *** ## 🧠 The Recognition Framework > [!WARNING] > > **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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/recognition-process.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=eb510ea9847adf4add23ba54b30a1d24) **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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/constraint-algo-map.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=ba8740c8ecb96332b9d4036549985e26) | 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 > > ```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]++; > } > ``` > **Count subsequences with property** > > **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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/optimize-pattern.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=0d5ede613a254bc275eec891784c0d3d) | 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 > > ```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; > ``` > **Does path/assignment exist?** > > **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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/keyword-triggers.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=dc774416788fd9d67beff840a91454ea) ### 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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/array-patterns.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=73342ab84aded3c3441aa4be6a3c18a2) ``` 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](https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/array-decision-tree.svg?fit=max\&auto=format\&n=AEOaWh79Ur7CdHHv\&q=85\&s=0bc3206f5690549b1a8771af8e520c05) ``` 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 ``` *** > [!TIP] > > **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!** πŸ† This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.