DSA Patterns & Templates

What you'll learn

• Dynamic Programming

• Identification

  DP applies when a problem has: 1. Choices — at each step you must decide (include/exclude, split here/there) 2. Overlapping subproblems — same subproblem computed multiple times (typically 2+ recursive calls) 3. Optimal substructure — op…

• DP Families

  ---

• 1. 0-1 Knapsack

  Problem: Given weights and values of N items, put items in a knapsack of capacity W to maximize total value. Each item can only be used once. Three variants: - 0-1 Knapsack: Include or exclude (no repeats) - Unbounded Knapsack: Same item…

• 2. Unbounded Knapsack

  The ONLY difference from 0-1: when including an item, DON'T reduce n. Problems: | Problem | Key Insight | |---------|-------------| | Rod Cutting | lengths = weights, prices = values, rod length = W | | Coin Change (min coins) | coin val…

• 3. Longest Common Subsequence (LCS)

  Intuition: Printing LCS: Start from dp[m][n], trace back: - If characters match → add to result, move diagonally (i-1, j-1) - Else → move toward max(dp[i-1][j], dp[i][j-1]) 15 LCS-family problems: | Problem | Variation | |---------|-----…

• 4. Matrix Chain Multiplication (MCM)

  Identification: Input is a string/array that needs to be partitioned for optimization. Pattern: Problems: | Problem | Partition Logic | |---------|----------------| | MCM (minimum multiplications) | Cost = arr[i-1] arr[k] arr[j] | | Pa…

• 5. DP on Trees

  Pattern: At each node, compute two values: 1. Value passing through this node (answer including this as root) → update global result 2. Value to return to parent (this node contributes to parent's path) → return to caller Problems: | Pro…

• Sliding Window

• Identification

  - Problem involves array or string - Asks for subarray or substring (contiguous) - Window size is either given (fixed) or to be found (variable)

• Fixed-Size Window

  Problems: - Maximum sum subarray of size k - First negative in every window of size k (use deque of negatives) - Count anagram occurrences (use frequency map as window state) - Maximum of all subarrays of size k (use monotonic deque)

• Variable-Size Window

  Problems: | Problem | Window Condition | |---------|-----------------| | Longest subarray with sum k | currentsum == k | | Longest substring with k distinct chars | len(freqmap) = target | currentsum >= target (minimize) |

• Key Difference: Expand vs Shrink

  ---

• Binary Search (Beyond Sorted Arrays)

• Identification

  Binary search applies whenever the search space is monotonic — not just sorted arrays but any scenario where: - If condition is true at mid, it's true for all values on one side - If condition is false at mid, it's false for all values o…

• Template Variants

• Binary Search on Answer

  When the array isn't sorted but the ANSWER space is monotonic: Problems: | Problem | Search Space | Feasibility Check | |---------|-------------|-------------------| | Koko eating bananas | Speed 1..max(piles) | Can finish in h hours at…

• Problems

  | Problem | Heap Type | Logic | |---------|-----------|-------| | Kth smallest element | Max-heap of size k | Top of heap = answer | | Kth largest element | Min-heap of size k | Top of heap = answer | | Sort nearly sorted array | Min-hea…

• Two-Heap Pattern (Running Median)

  ---

• Union-Find (Disjoint Set)

• When to Use

  - Graph connectivity (are two nodes connected?) - Count connected components - Detect cycles in undirected graph - Dynamic connectivity (edges added over time) - Kruskal's MST algorithm

• Implementation with Path Compression + Union by Rank

  Complexity: Nearly O(1) amortized for both find and union (inverse Ackermann). Problems: | Problem | Key Insight | |---------|-------------| | Number of connected components | Initialize n components; each union reduces by 1 | | Redundan…

• Backtracking

• Identification

  - Problem asks for all combinations/permutations - Constraint size is small (n

• Problems

  | Problem | Choices | Constraint | |---------|---------|-----------| | Permutations | All unused elements | Each element used once | | Combinations (n choose k) | Elements from current index onward | Exactly k elements | | Subsets | Incl…

• Key Distinction

  ---

• Graph Algorithms

• Representation

• BFS (Shortest Path in Unweighted Graphs)

• DFS (Connected Components, Cycle Detection)

• Dijkstra (Shortest Path in Weighted Graphs)

• Topological Sort (DAGs only)

• Key Algorithm Selection

  | Problem Type | Algorithm | Time | |-------------|-----------|------| | Shortest path (unweighted) | BFS | O(V+E) | | Shortest path (weighted, no negative) | Dijkstra | O((V+E) log V) | | Shortest path (negative weights) | Bellman-Ford…

• Stack Patterns

• Monotonic Stack (Next Greater/Smaller Element)

  Four variants (all use same template, different traversal direction): | Variant | Traversal | Stack Maintains | |---------|-----------|-----------------| | Next Greater to Right | Left → Right | Decreasing from bottom | | Next Greater to…

• Key Complexities

  | Pattern | Time | Space | |---------|------|-------| | 0-1 Knapsack (bottom-up) | O(n W) | O(n W), optimizable to O(W) | | LCS | O(m n) | O(m n), optimizable to O(min(m,n)) | | Sliding Window | O(n) | O(1) to O(k) | | Binary Search…