Complete DSA Pattern Guide¶

How to use this guide: this is the intuition + when-to-use + decision layer. Full, runnable implementations live in the linked .py files - open those to study or run the code (python <file>). For instant keyword → pattern lookup, see DSA Quick Lookup. For the visual thinking layer (decision flowcharts, the mental web, constraints→complexity), see DSA Mental Models.

Table of Contents¶

Array - Two Pointers, Sliding Window, Prefix/Suffix, Kadane's
Dynamic Programming - 1D, 2D, Knapsack, Partition, String DP, LIS
Hash Table - O(1) Lookup, Frequency, Complement Search
DFS - Recursive/Iterative, Tree Traversals, Matrix, Cycle Detection, Topological Sort
BFS - Level Order, Shortest Path, Multi-Source
Graph - Dijkstra, Bellman-Ford, Topological Sort, Union-Find, MST
String - Pattern Matching (overview)
Tree - Traversals, common recursive patterns
Binary Search - Standard, On Answer, Rotated Array
Sorting - QuickSort, MergeSort, QuickSelect
Stack - Monotonic Stack, Monotonic Deque
Greedy - Intervals, Jump Game
Linked List - Reverse, Cycle Detection, Merge
Backtracking - Permutations, Combinations, Subsets, N-Queens
Heap / Priority Queue - Top K, Running Median
Bit Manipulation - XOR Tricks, Subset Generation 16.5. Matrix / Grid - Islands, Spiral, Rotate, Sorted-Matrix Search 16.6. Design a Data Structure - LRU, Min Stack, MedianFinder, Trie
Advanced / Rarely Asked - Segment Tree, Bitmask DP, Manacher's, SCC, string-matching

CORE PATTERNS¶

1. Array¶

When to use which technique: - Two Pointers - sorted-array pair/triplet sum, palindrome, partition. Opposite ends converge, or fast/slow. - Sliding Window - longest/shortest contiguous subarray/substring with a constraint. Expand right, contract left. Trick: exactly K = at_most(k) - at_most(k-1). - Prefix/Suffix Arrays - repeated range-sum queries (O(1) after O(n) prep), product-except-self. - In-place - mark visited via sign/modulo, swap instead of allocating. - Kadane's - maximum subarray sum in O(n); track max_ending_here, max_so_far.

Files: Two Pointers · Sliding Window · Prefix Sum · Kadane's · k-Sum

Sample Problems: Two Sum, 3Sum, Container With Most Water, Product of Array Except Self, Maximum Subarray, Subarrays with K Distinct.

2. Dynamic Programming¶

Mental model: "If I solve smaller inputs, can I combine those solutions?" DP = optimal substructure + overlapping subproblems.

Decision framework: 1. Can I break it into subproblems? (optimal substructure) 2. Do subproblems overlap? (memoize) 3. What defines a state? (indices, remaining capacity, flags) 4. What's the recurrence? (how states combine) 5. What are the base cases?

Categories & the state they track: - 1D DP - dp[i] = answer for first i elements (Climbing Stairs, House Robber, Decode Ways). - 2D DP - dp[i][j] = answer for first i of A, j of B (LCS, Edit Distance, Unique Paths). - Knapsack - 0/1 (each item once, iterate capacity right→left), unbounded (reuse, left→right), subset-sum, partition. - Partition/Interval DP - try all split points k in [i, j) (MCM, Burst Balloons, Palindrome Partitioning). - String DP - LCS, Edit Distance, Longest Palindromic Subsequence, wildcard matching. - LIS - O(n log n) via patience sorting: keep tails[] (smallest tail per length), binary-search the insert point. - DP on Trees - max path sum, diameter, House Robber III (bottom-up return values).

Common mistakes: wrong iteration order (compute dependencies first), missing base cases, forgetting the "don't take" option, not optimizing space when only the previous row is needed.

Files: DP Patterns · Climbing Stairs · House Robber · Coin Change · Knapsack · LCS · Edit Distance · Unique Paths · LIS

3. Hash Table¶

Mental model: trade space for time. O(1) average lookup.

When to use: fast existence check, frequency counting, duplicate detection, grouping by property, complement search (Two Sum pattern).

Hash table vs array: use a list when keys are 0..n (char/number frequency in range); use a dict when keys are arbitrary or a large/sparse range.

Sample Problems: Two Sum, Subarray Sum Equals K, Group Anagrams, Longest Substring Without Repeating Characters.

4. DFS¶

Mental model: go deep first; recursion or an explicit stack. Mark visited to avoid cycles.

Use for: tree/graph traversal, all-paths, cycle detection, topological sort, connected components, backtracking.

Key variants: - Recursive vs iterative (stack). Recursion is cleaner; use an explicit stack if depth risks the recursion limit. - Tree traversals - inorder (sorted for BST), preorder (serialize), postorder (delete/height). - Matrix DFS - 4-directional flood fill; always bounds-check and mark visited before recursing. - Directed cycle detection - 3-color (white/gray/black); a gray→gray edge is a back edge = cycle. - Topological sort (DFS) - push nodes in postorder, then reverse.

Complexity: O(V + E) for graphs, O(n) for trees; O(h) recursion-stack space.

Files: DFS · DFS Patterns · Directed Cycle Detection · Topological Sort · Tree Patterns

5. BFS¶

Mental model: process level by level with a queue. Gives shortest path in an unweighted graph.

Use for: shortest path (unweighted), level-order traversal, minimum steps/distance, "is it reachable".

Key variants: - Level-order - snapshot len(queue) at the start of each level. - Matrix shortest path - enqueue (row, col, dist); mark visited on enqueue, not dequeue. - Multi-source BFS - seed the queue with all sources at once (Rotting Oranges, nearest-exit). - State BFS - the visited key includes extra state (e.g. (row, col, remaining_eliminations)).

Complexity: O(V + E) time, O(V) space. Use collections.deque (not list.pop(0)).

Files: BFS · BFS Patterns

6. Graph¶

Representations: adjacency list (most common, sparse), adjacency matrix (dense / O(1) edge lookup / Floyd-Warshall), edge list (MST, Union-Find).

Algorithm selection (memorize this table):

Problem	Algorithm	Time
Shortest path, unweighted	BFS	O(V+E)
Shortest path, non-negative weights	Dijkstra	O((V+E) log V)
Shortest path, negative weights / neg-cycle detect	Bellman-Ford	O(VE)
Shortest path with a state constraint (e.g. ≤ K stops)	Dijkstra/BFS with state in the heap/queue	-
Cycle detection	DFS (3-color for directed) / Union-Find	O(V+E)
Topological ordering (DAG)	DFS postorder / Kahn's BFS (indegrees)	O(V+E)
Minimum spanning tree	Kruskal (Union-Find) / Prim (heap)	O(E log E)
Connected components	DFS / BFS / Union-Find	O(V+E)

Dijkstra-with-state is a high-value variant (common across MAANG): when the answer depends on more than distance (stops used, fuel left), add that dimension to the heap entry - see Cheapest Flights within K Stops in dijkstra.

Files: Dijkstra · Bellman-Ford · Topological Sort · Union-Find · Kruskal's · Prim's · Bipartite · Undirected Cycle

7. String¶

When to reach for what: - Frequency/hashing - anagrams, "contains all chars"; a Counter or fixed-size array is usually enough. - Sliding window - longest substring problems (see Array §1). - Two pointers - palindrome checks, reversal.

Advanced pattern-matching algorithms (KMP, Rabin-Karp, suffix structures, Manacher's) are rarely required - see §17 Advanced.

Sample Problems: Longest Substring Without Repeating Characters, Group Anagrams, Valid Palindrome II.

8. Tree¶

Mental model: recursive by nature - solve subtrees, combine at the root. Base case: a null node returns a neutral value (0, -inf, None, True).

Common patterns (all bottom-up unless noted): max depth, invert, diameter (path through node = left height + right height), lowest common ancestor, path sum, max path sum (clamp negative child paths to 0), serialize/deserialize (preorder with null markers), right-side view (BFS, take last of each level).

Complexity: O(n) time; O(h) recursion-stack space (O(n) worst case for a skewed tree).

Files: Tree Patterns (depth, diameter, LCA, path sum, serialize/deserialize, right-side view) · BST · Trie (incl. Word Search II)

9. Binary Search¶

Mental model: halve the search space each step; works on sorted data or any monotonic predicate.

Templates: - Standard - find an element; while left <= right. - Boundary - first/last occurrence; while left < right, don't return early. - On answer - binary-search the result value when you can test feasibility monotonically (Ship Packages in D Days, Aggressive Cows, Split Array Largest Sum). - Rotated array - determine which half is sorted, then decide which side to keep.

Common mistakes: wrong loop condition (<= vs <), wrong pointer update (mid vs mid±1), wrong feasibility predicate for on-answer.

Files: Binary Search patterns (peak, kth-missing, ship-in-D-days, matrix median, median of two sorted arrays)

10. Sorting¶

What to know: QuickSort (O(n log n) avg, in-place, unstable), MergeSort (O(n log n) worst, stable, O(n) space), QuickSelect (O(n) avg for Kth element without full sort).

When to sort first: Two Sum (→ two pointers), intervals (→ sort by start/end, then merge/select), anagrams (→ sort chars to group), find duplicates (→ sort, linear scan).

Files: QuickSort · MergeSort (incl. count-smaller-after-self, sort-list) · QuickSelect (incl. K closest points)

11. Stack¶

Use for: matching parentheses, expression evaluation, undo, iterative DFS.

Monotonic Stack - next/previous greater/smaller element, stock span, largest rectangle in histogram. Maintain a monotonic (in/de)creasing stack of indices; pop on violation and that's where the popped element's "answer" is.

Monotonic Deque ⭐ - sliding window min/max in O(n) (each element enters/leaves once). Strong top-tech favorite; know it cold.

Files: Monotonic Stack · Monotonic Queue

12. Greedy¶

Mental model: make the locally optimal choice - but only when you can argue the greedy-choice property holds.

Common patterns: intervals (sort by end for selection/non-overlap; by start for merge), Jump Game (track max reach), activity selection, Gas Station (track running surplus, reset start on deficit), Task Scheduler.

Files: Greedy · Intervals

13. Linked List¶

Core operations: reverse (prev/curr/next), cycle detection (Floyd's fast/slow), find middle (fast moves 2×), merge two sorted (dummy head), remove Nth from end (two pointers n apart), palindrome (find mid → reverse half → compare).

Tip: use a dummy head node for merge/remove problems to avoid null-edge bugs.

Files: Linked List

14. Backtracking¶

Framework: choose → explore (recurse) → un-choose. Base case captures a complete solution (append a copy of the path).

Common problems: subsets, permutations, combinations, combination sum, N-Queens, Sudoku, palindrome partitioning, Word Search.

Optimization: prune early (check validity before recursing), sort input to skip duplicates, use a visited set.

Files: Backtracking

15. Heap / Priority Queue¶

Use for: Top K / Kth largest-smallest, merge K sorted lists, running median (two heaps), scheduling, Dijkstra.

Key idioms: - Top K largest → min-heap of size k (evict the smallest). Top K smallest → max-heap of size k. (Counterintuitive but correct.) - Running median → max-heap (lower half) + min-heap (upper half), kept balanced. - Python's heapq is a min-heap; negate values for a max-heap.

Files: Heap Patterns · MinHeap · MaxHeap · PriorityQueue

16. Bit Manipulation¶

Core operations: check bit num & (1 << i), set num | (1 << i), clear num & ~(1 << i), toggle num ^ (1 << i), clear lowest set bit num & (num-1), lowest set bit num & -num.

XOR properties: a ^ a = 0, a ^ 0 = a → find the single number, detect missing number.

Patterns: single number (XOR all), power of two (n & (n-1) == 0), subset generation (iterate 0 .. 2^n - 1), counting bits.

Files: Bit Manipulation

16.5 Matrix / Grid¶

Mental model: a grid is an implicit graph - each cell connects to its neighbors (usually 4-directional). Most grid problems are DFS/BFS + a visited marker, or in-place index manipulation.

Core patterns: - Flood fill / connected components - DFS or BFS from each unvisited target cell (Number of Islands, Max Area of Island). Mark visited (or sink the cell) before recursing; always bounds-check. - Shortest path on a grid - BFS (unweighted); enqueue (row, col, dist), mark visited on enqueue. Add state to the visited key when relevant (e.g. remaining obstacle-eliminations). - Spiral order - track top/bottom/left/right boundaries, shrink after each edge; re-check top<=bottom && left<=right. - Rotate image 90° - transpose in place, then reverse each row. - Search a sorted matrix - staircase from the top-right: move left if too big, down if too small (O(m+n)). - Set matrix zeroes - use the first row/column as marker storage for O(1) extra space.

Watch: bounds checks before indexing; mark visited before enqueuing (BFS) to avoid duplicates; pick the right direction set (4- vs 8-directional).

Files: Matrix Patterns

16.6 Design a Data Structure¶

A common interview round: "design/implement X" - combine primitives to hit the required time complexity.

LRU Cache - hash map + doubly linked list for O(1) get/put (evict from the tail). See LRU Cache.
Min Stack - push (value, running_min) (or a parallel min-stack) so get_min() is O(1). See stack.
Median from Data Stream (MedianFinder) - two heaps: a max-heap for the lower half, a min-heap for the upper half, kept balanced; median from the tops. See Heap Patterns.
Trie / prefix tree - insert/search/startsWith in O(word length); backs autocomplete and Word Search II. See Trie.
Others to know: Hit Counter (queue/ring buffer of timestamps), Insert/Delete/GetRandom O(1) (array + index map), Design Twitter (hash maps + heap merge for the feed).

Key move: state the target complexity first, then pick the primitive combo that achieves it (hash map for O(1) lookup, DLL for O(1) reorder, heap for ordered access, trie for prefixes).

17. Advanced / Rarely Asked¶

These are included for completeness and appear in some interviews, but are low-yield for a typical coding round - mostly competitive-programming territory. Learn the idea and what problem each solves; only go deep if a specific role or the must-knows are already solid. Don't let these crowd out the core patterns above.

Segment Tree / Fenwick (BIT) - range query + point/range update in O(log n). Reach for it only when a problem needs both range queries and updates. Fenwick is the simpler cousin for prefix sums. See Segment Tree and Fenwick Tree.
Bitmask DP / TSP - dp[mask][i] = best result having visited the set mask, ending at i. State compression for small n (≤ ~20).
Manacher's Algorithm - longest palindromic substring in O(n). In an interview, center-expansion (O(n²)) is almost always the accepted answer.
Suffix Trie / Suffix Array + LCP - count distinct substrings, longest repeated substring. See Suffix Trie.
KMP / Rabin-Karp / Z-Algorithm - substring search in O(n+m). Know that they exist; the failure-function / rolling-hash derivations are seldom required. See KMP, Rabin-Karp.
Kosaraju's / Tarjan's SCC - strongly connected components. Uncommon. See Kosaraju, Tarjan.
Floyd-Warshall - all-pairs shortest path, O(V³). Simple to state; rarely the expected answer. See Floyd-Warshall.
Rerooting DP - recompute a tree DP for every root in O(n). Niche.

Files (reference only): Segment Tree · Suffix Trie · KMP · Rabin-Karp · Kosaraju · Tarjan · Floyd-Warshall