Pattern-Based Problem Solving
Patterns are the skeleton of every algorithm. Learn the skeleton once, and you can apply it to hundreds of problems. This guide maps every pattern to the problems in this repository - 38,000+ problems, organized by the shape of their solution.
Most DSA problems are not truly unique. They are variations of a smaller set of structural patterns. When you recognise the pattern behind a problem, you already know 80% of the solution. The remaining 20% is adapting the template to the specific twist.
Nobody remembers 38,000 solutions. But you can remember 40 patterns and derive the rest. This is how strong engineers think: they don't brute-force recall solutions, they identify the structure of the problem and pick the matching template.
Many problems sit at the intersection of multiple patterns. A problem might use sliding window for the outer loop and a hash map for the inner state. This guide marks primary and secondary pattern assignments, so you see how patterns compose.
The patterns below are grouped by experience level - not by data structure or topic. This is intentional: you should learn patterns in an order that builds on itself. Each level assumes comfort with the patterns before it.
Use a hash map to count occurrences, track pair sums, or detect duplicates in O(1) average lookup time. The bread and butter of O(n) solutions.
Two indices moving through a sequence - opposite direction or same direction. Turns O(n²) comparisons into O(n) by maintaining an invariant about pointer positions.
Maintain a window over a contiguous segment of an array/string. Expand the right edge, shrink the left edge when the window becomes invalid. Turns O(n²) subarray enumeration into O(n).
Precompute running sums so that sum(l..r) = prefix[r] - prefix[l-1] in O(1). Works with hash maps to count subarrays matching a target.
Sorting is not a pattern itself, but many problems become trivial once the input is sorted. Sort + two pointers, sort + greedy, sort + binary search - the prep step that unlocks linear passes.
Last-in-first-out structure. Used for matching problems (parentheses), undo operations, expression evaluation, and maintaining a history of elements to compare against later elements.
First-in-first-out structure. Used for level-order traversal, BFS, streaming data, and maintaining elements in arrival order.
Repeatedly divide the search space in half. Works when the search space is monotonic - sorted arrays, or any predicate that transitions from false to true.
Dummy nodes, reversal, slow/fast pointers, merging, partitioning. Linked lists enforce sequential access, so the patterns focus on pointer manipulation and two-pass techniques.
Solve a problem by solving smaller instances of the same problem. Every recursive solution needs a base case and a recurrence that moves toward the base. The foundation for trees, DP, backtracking.
Explore all candidate solutions by building incrementally and abandoning (pruning) paths that cannot lead to a valid solution. State space search with undo.
Recursive depth-first traversal of a tree. Pre-order (process before children), in-order (process between children - gives sorted order in BST), post-order (process after children - need child results first).
Queue-based level-by-level traversal of a tree. Process all nodes at depth d before depth d+1. Level averages, right side view, zigzag, connect siblings.
Iterating a 2D grid systematically - row-major, spiral order, diagonal traversal, neighbor iteration with delta arrays (dr/dc). Often combined with BFS/DFS.
Recursive or stack-based depth-first graph traversal. Mark visited on entry. Count connected components, detect cycles (track parent undirected, path[] for directed), topological sort via post-order.
Queue-based breadth-first graph traversal. Guarantees shortest path in unweighted graphs. Level-by-level expansion. Multi-source variant: enqueue all sources at level 0.
Always extract the min/max element in O(log n). Used for top-K, median finding, Dijkstra, merge K sorted lists, scheduling, and anytime you need repeated extreme-value queries.
Sort by start time, then merge, intersect, or compare adjacent intervals. Overlap check: max(start1, start2) < min(end1, end2). Sweep-line for complex coverage.
Make the locally optimal choice at each step, trusting it leads to the global optimum. Works when the problem has optimal substructure and a greedy choice property. Classic: interval scheduling, coin change (canonical).
Start with a problem...
├── Is it about counting or looking up something fast?
│ └── ✓ Hash Map / Frequency Counting
│
├── Is the input a sorted array or string?
│ ├── Looking for a pair with a target? → Two Pointers
│ ├── Looking for a contiguous subarray/substring? → Sliding Window
│ └── Looking for a specific value? → Binary Search
│
├── Can you precompute something to answer queries fast?
│ └── ✓ Prefix Sum, Difference Array, Rolling Hash
│
├── Does the problem ask for all permutations/combinations/subsets?
│ └── ✓ Backtracking
│
├── Is it a tree?
│ ├── Need to process level-by-level? → Tree BFS
│ ├── Need child results before parent decision? → Tree DFS (post-order)
│ ├── Need sorted order from BST? → Tree DFS (in-order)
│ └── Path query between two nodes? → LCA / Binary Lifting
│
├── Is it a graph?
│ ├── Shortest path in unweighted graph? → Graph BFS
│ ├── Shortest path in weighted graph? → Dijkstra
│ ├── Connected components? → Graph DFS or DSU
│ ├── Cycle detection? → DFS + vis/path or DSU
│ ├── Topological order? → Kahn's / DFS post-order
│ ├── All-pairs shortest? → Floyd-Warshall
│ └── Minimum cost to connect all? → MST (Kruskal/Prim)
│
├── Is it a linked list?
│ ├── Detect cycle / find middle? → Fast & Slow Pointers
│ ├── Reverse / merge / remove? → Dummy Node + Iteration
│ └── Palindrome / reorder? → Slow/Fast + Reverse
│
├── Does it ask for max/min under a constraint?
│ ├── Choose or skip items? → DP or Greedy
│ ├── Can you check feasibility of a candidate? → Binary Search on Answer
│ └── Locally optimal choice works? → Greedy
│
├── Is there optimal substructure with overlapping subproblems?
│ └── ✓ Dynamic Programming (1D → 2D → Tree → etc.)
│
├── Does it involve next/previous greater/smaller?
│ └── ✓ Monotonic Stack
│
├── Sliding window with min/max tracking?
│ └── ✓ Monotonic Queue / Deque
│
├── Top K, median, or merge K sorted?
│ └── ✓ Heap / Priority Queue
│
├── String matching / prefix search?
│ └── ✓ Trie, KMP, Z-Algorithm, Rolling Hash
│
├── Range queries with updates?
│ └── ✓ Segment Tree or Fenwick Tree
│
├── Range queries without updates?
│ └── ✓ Prefix Sum, Difference Array, Sparse Table
│
├── Bit-level operations / subset enumeration?
│ └── ✓ Bit Manipulation, Bitmask DP
│
├── Game with two optimal players?
│ └── ✓ Game Theory / Minimax / Grundy
│
└── None of the above?
└── Could be Simulation, Ad-hoc, Math, or a combination of patternsStart with a Beginner pattern (hash map, two pointers, sliding window). Read the pattern page - understand the mental model, not just the code.
Each pattern has a core template. This is the skeleton. Understand why each line exists, what invariant it maintains, and when the template breaks.
Templates have variants. The core idea stays the same but the details shift - fixed vs dynamic window, opposite vs same-direction pointers. Each variant opens a new class of problems.
Each pattern page lists problems from this repository that fit the template and each variant. Solve them in the recommended order: beginner → intermediate → advanced.
Mark which problems you have solved. The goal is not to solve every problem - it is to internalise the pattern so thoroughly that new problems feel familiar within seconds.
When you get stuck on a new problem, come back to this guide. Find the pattern that matches the shape of your problem. Read the page again. It will make more sense each time.
Build the reflexes. These patterns alone can solve ~40% of interview problems. Focus on recognising the signal phrases for each one.
These are the patterns that separate scripted solutions from genuine problem-solving ability. Trees and graphs appear in ~30% of interviews.
These patterns add the sharpest tools to your belt. DP and Union-Find are common at top-tier companies. Monotonic stacks turn intimidating O(n²) problems into clean O(n) walks.
These are specialist patterns. Not every interview will need them, but when they do, they separate senior engineers. Learn them if you target top companies or competitive programming.
Every pattern page in this guide maps problems from the repository's 38,000+ problem list. The mapping is done incrementally - each pattern article adds its own mappings. The tracking table below shows the current state for every pattern.
| Pattern | Problems | Level | Status | Complexity |
|---|---|---|---|---|
| Sorting-Based Patterns | 4,000 | Beginner | Needs Mapping | O(n log n) sort + O(n) pass |
| Binary Search | 3,709 | Beginner | Ready | O(log n) time, O(1) space |
| Hash Map / Frequency Counting | 3,200 | Beginner | Needs Mapping | O(n) time, O(k) space |
| Two Pointers | 2,500 | Beginner | Ready | O(n) time, O(1) space |
| Prefix Sum | 1,800 | Beginner | Needs Mapping | O(n) precompute, O(1) query |
| Stack | 1,500 | Beginner | Needs Mapping | O(n) time, O(n) space |
| Queue | 800 | Beginner | Needs Mapping | O(n) time, O(n) space |
| Sliding Window | 610 | Beginner | Ready | O(n) time, O(1) or O(k) space |
| Recursion | 3,000 | Intermediate | Needs Mapping | Varies - O(n) to O(2ⁿ) |
| Tree DFS | 2,000 | Intermediate | Needs Mapping | O(n) time, O(h) space |
| Greedy | 2,000 | Intermediate | Ready | O(n log n) typically |
| Graph DFS | 1,200 | Intermediate | Needs Mapping | O(V + E) time, O(V) space |
| Linked List Patterns | 1,135 | Intermediate | Ready | O(n) time, O(1) space |
| Graph BFS | 1,000 | Intermediate | Needs Mapping | O(V + E) time, O(V) space |
| Tree BFS / Level Order | 800 | Intermediate | Needs Mapping | O(n) time, O(w) width |
| Intervals | 600 | Intermediate | Needs Mapping | O(n log n) sort, O(n) pass |
| Heap / Priority Queue | 496 | Intermediate | Ready | O(n log k) or O((V+E) log V) |
| Matrix Traversal | 331 | Intermediate | Ready | O(m×n) time, O(1) or O(m×n) space |
| Backtracking | 325 | Intermediate | Ready | O(n!) or O(2ⁿ) worst case with pruning |
| Math / Number Theory | 9,632 | Advanced | Needs Mapping | Varies - O(√n) to O(log n) |
| Dynamic Programming | 4,313 | Advanced | Ready | Varies - O(n), O(n²), O(n × W), etc. |
| Bit Manipulation | 2,868 | Advanced | Ready | O(1) or O(number of bits) |
| Simulation | 2,000 | Advanced | Needs Mapping | O(n) or O(m×n) as specified |
| Binary Search on Answer | 800 | Advanced | Ready | O(n log M) or O(n log n log M) |
| Knapsack DP | 600 | Advanced | Ready | O(n × W) time |
| Shortest Path | 600 | Advanced | Needs Mapping | O((V+E) log V) Dijkstra, O(VE) Bellman-Ford, O(V³) Floyd |
| Union-Find / DSU | 500 | Advanced | Ready | O(α(n)) amortized per operation |
| Design Problems | 500 | Advanced | Needs Mapping | O(1) or O(log n) per operation |
| Monotonic Stack | 400 | Advanced | Ready | O(n) time, O(n) space |
| Tree DP | 400 | Advanced | Needs Mapping | O(n) with DFS, O(n²) with knapsack |
| Segment Tree | 400 | Advanced | Needs Mapping | O(log n) per query/update, O(n) build |
| String Matching | 400 | Advanced | Needs Mapping | O(n + m) KMP/Z, O(n) average Rabin-Karp |
| Game Theory | 400 | Advanced | Needs Mapping | O(states × moves) typically |
| Topological Sort | 300 | Advanced | Ready | O(V + E) time, O(V) space |
| Interval DP | 300 | Advanced | Ready | O(n²) or O(n³) time |
| Digit DP | 300 | Advanced | Ready | O(digits × states × transition) |
| Fenwick Tree / BIT | 300 | Advanced | Needs Mapping | O(log n) per query/update |
| Geometry | 300 | Advanced | Needs Mapping | O(n log n) for hull, O(n) for area |
| Rolling Hash | 250 | Advanced | Needs Mapping | O(n) precompute, O(1) hash, O(log n) with binary search |
| Monotonic Queue / Deque | 200 | Advanced | Ready | O(n) time, O(k) space |
| Bitmask DP | 200 | Advanced | Ready | O(2ⁿ × n) or O(2ⁿ × n²) |
| Minimum Spanning Tree | 200 | Advanced | Needs Mapping | O(E log E) Kruskal, O(E log V) Prim |
| Trie | 158 | Advanced | Ready | O(L) per operation where L = word length |
Pattern article is written with templates, variants, and problem mappings. Ready to study.
Pattern article structure exists but problem-to-pattern mapping from the repository is not yet done.
Pattern has initial mapping but needs verification. Some problems may be incorrectly assigned.
Pattern is advanced and planned for a later pass. Not a priority for the current phase.
The best place to start is Two Pointers. It is beginner-friendly, builds foundational thinking about indices and invariants, and directly leads into Sliding Window and Fast-Slow Pointer patterns. Every pattern page follows the same structure: mental model → template → variants → problem mappings.
The next pattern article will be written under /pattern/<slug>. Each article one at a time, starting with the pattern you choose above.