DSA Problem-Solving Patterns Cheat Sheet
Arrays (5 Patterns)
- Two Pointers – pair sum, sort colors, trap water
- Sliding Window – longest substring, max subarray, distinct elements
- Prefix Sum / Difference Array – subarray sum, range update, equilibrium index
- Sorting & Searching – binary search variations
- Kadane’s Algorithm – max subarray, circular subarray, product subarray
Strings (4 Patterns)
- Hashing / Rolling Hash – anagrams, substring search, string matching
- Dynamic Programming – LCS, edit distance, palindrome subsequence
- Sliding Window – longest substring without repeat, anagrams in string
- Trie / Suffix Structures – prefix search, word dictionary
Linked Lists (3 Patterns)
- Fast & Slow Pointers – cycle detection, middle node, palindrome check
- Reversal Patterns – reverse whole list, reverse k-group, reverse between nodes
- Merging & Sorting – merge k sorted lists, sort list, add two numbers
Stacks & Queues (3 Patterns)
- Monotonic Stack/Queue – next greater element, stock span, sliding window max
- Parsing with Stack – valid parentheses, expression evaluation
- Queue/BFS Usage – level order traversal, rotten oranges
Trees (6 Patterns)
- Traversals – DFS, BFS (level order, zigzag)
- Lowest Common Ancestor (LCA)
- BST Patterns – insert/delete, kth smallest/largest
- Path/Diameter Problems – max path sum, diameter
- Subtree / Structure Matching – subtree check, serialize/deserialize
- Advanced Tree Structures – segment tree, Fenwick tree
Graphs (7 Patterns)
- BFS/DFS Traversal – connected components, islands
- Topological Sort – course schedule
- Shortest Path – Dijkstra, Bellman-Ford, Floyd-Warshall
- Minimum Spanning Tree – Prim’s, Kruskal’s
- Union-Find – cycle detection, accounts merge
- Strongly Connected Components – Kosaraju, Tarjan
- Graph Coloring / Bipartite Checks
Heaps (2 Patterns)
- Top-K Problems – k largest, kth smallest/largest, heap sort
- Custom Priority / Scheduling – meeting rooms, task scheduler
Intervals (2 Patterns)
- Sorting & Merging – merge intervals, meeting rooms
- Sweep Line / Event Sorting – maximum overlap, skyline problem
Backtracking (3 Patterns)
- Subsets & Combinations – subsets, combination sum
- Permutations – generate permutations
- Constraint Satisfaction – N-Queens, Sudoku
Dynamic Programming (8 Patterns)
- 1D DP – Fibonacci, climbing stairs
- 2D Grid DP – unique paths, min path sum
- Knapsack Variants – 0/1, unbounded, coin change
- Subset / Partition DP – subset sum, partition equal subset
- String DP – LCS, edit distance, palindrome subsequence
- Interval DP – matrix chain multiplication, burst balloons
- Bitmask DP – traveling salesman, assignment problems
- State Compression DP – DP on subsets/graphs
