Common Solution Strategies Across 200 Algorithms
Common Solution Strategies Across 200 Algorithms
A cross-cutting reference document that maps algorithmic problem-solving patterns, connects algorithms that share underlying strategies, and provides a practical decision guide for choosing the right approach.
1. Pattern Categories
1.1 Two Pointers
Description: Use two references (indices or nodes) that traverse data simultaneously according to specific rules. Reduces nested iteration from O(n^2) to O(n) in many cases.
Variants:
Opposite-Direction (Converging) Pointers
Start one pointer at the beginning and one at the end, moving them toward each other.
- When to use: Sorted arrays where you need pairs, palindrome checks, or partitioning.
- Algorithms:
- Two Number Sum -- sort then converge from both ends to find a target sum
- Three Number Sum -- fix one element, then use two converging pointers on the remainder
- Smallest Difference -- converge pointers across two sorted arrays to minimize the gap
- Sorted Squared Array -- build result from largest magnitude inward
- Palindrome Check -- compare characters from both ends toward the center
- Valid Starting City -- circular traversal reasoning with pointer logic
- Water Area -- two-pointer approach tracking max heights from left and right
Same-Direction Pointers
Both pointers move in the same direction, typically one leading and one trailing.
- When to use: Partitioning, removing elements in-place, merging sorted structures.
- Algorithms:
- Move Element to End -- swap pointer moves forward while end pointer retreats from target values
- Three Number Sort -- Dutch National Flag with three pointers
- Remove Duplicates from Linked List -- trailing pointer skips duplicate nodes
- Merge Linked Lists -- two pointers walk through sorted lists choosing the smaller
- Sweet and Savory -- pointer-based pair matching on sorted partitions
Fast/Slow (Floyd's Tortoise and Hare)
One pointer moves at double speed; they meet if a cycle exists.
- When to use: Cycle detection, finding midpoints in linked lists.
- Algorithms:
- Find Loop -- detect and locate the start of a cycle in a linked list
- Middle Node -- slow pointer is at midpoint when fast pointer reaches the end
- Linked List Palindrome -- find midpoint, reverse second half, then compare
- Single Cycle Check -- detect whether jumps through an array visit every index exactly once
1.2 Sliding Window
Description: Maintain a window (contiguous subrange) over a sequence, expanding or contracting it to satisfy constraints. Converts brute-force O(n^2) substring/subarray scans into O(n).
Fixed-Size Window
Window length is known in advance; slide it across the input.
- When to use: Aggregations over fixed-length subarrays, rolling statistics.
- Algorithms:
- Maximum Sum Submatrix -- fixed-size submatrix sum using prefix sums with a sliding window
- Calendar Matching -- sliding comparison across time intervals of fixed meeting durations
Variable-Size Window
Expand the right boundary to include elements, shrink the left to restore validity.
- When to use: Longest/shortest substring or subarray subject to a constraint.
- Algorithms:
- Longest Substring Without Duplicates -- expand right, contract left when a duplicate enters
- Smallest Substring Containing -- shrink window once all target characters are captured
- Longest Subarray With Sum -- expand right to grow sum, contract left when sum exceeds target
- Longest Balanced Substring -- track parenthesis balance while sliding
- Underscorify Substring -- track overlapping match intervals via sliding logic
1.3 Divide and Conquer
Description: Split the problem into smaller independent subproblems, solve each recursively, then combine results. Yields O(n log n) for many problems that would otherwise be O(n^2).
- When to use: Sorting, counting inversions, selection, problems with natural recursive decomposition.
- Algorithms:
- Merge Sort -- divide array in half, recursively sort, merge sorted halves
- Quick Sort -- partition around a pivot, recursively sort partitions
- Count Inversions -- modified merge sort that counts cross-partition inversions during merge
- Quickselect -- partition like quick sort but recurse into only one side to find k-th element
- Median of Two Sorted Arrays -- binary search based divide and conquer on two sorted arrays
- Right Smaller Than -- modified merge sort or BST insertion counting smaller elements
1.4 Greedy
Description: Make the locally optimal choice at each step, trusting it leads to the global optimum. Greedy works when the problem has the greedy-choice property and optimal substructure.
- When to use: Scheduling, interval problems, problems where sorting + one pass suffices, minimum spanning trees.
- Algorithms:
- Minimum Waiting Time -- sort ascending, shortest jobs first minimizes total wait
- Class Photos -- sort both rows, greedily assign taller row to the back
- Tandem Bicycle -- pair fastest with slowest (or fastest with fastest) depending on optimization goal
- Task Assignment -- pair longest task with shortest to minimize max parallel time
- Optimal Freelancing -- schedule highest-paying jobs into latest available deadlines
- Valid Starting City -- greedy circular scan tracking fuel surplus
- Non-Constructible Change -- sort coins, greedily extend the range of constructible values
- Best Digits -- greedily remove digits using a stack to maximize remaining number
- Min Rewards -- two-pass greedy ensuring local constraints are met
- Kruskal's Algorithm -- greedily add cheapest edge that does not create a cycle (MST)
- Prim's Algorithm -- greedily grow MST from a starting vertex by adding cheapest crossing edge
- Stable Internships -- Gale-Shapley: each student proposes greedily, companies accept/reject
1.5 Dynamic Programming
Description: Break a problem into overlapping subproblems, solve each once, and store results to avoid recomputation. Two implementation styles exist.
Memoization (Top-Down)
Recurse naturally, caching results in a hash map or array.
- When to use: When the recursive structure is intuitive and not all subproblems are needed.
- Algorithms:
- Interweaving Strings -- memoize on (i, j) indices into two source strings
- Numbers in Pi -- memoize minimum spaces from each index
- Ambiguous Measurements -- memoize whether a target is reachable from current state
- Blackjack Probability -- memoize probability from current hand total
- Number of Binary Tree Topologies -- memoize count for each node count
- Staircase Traversal -- memoize ways to reach each step
- Longest String Chain -- memoize chain length from each string
Tabulation (Bottom-Up)
Fill a table iteratively from base cases to the answer.
- When to use: When all subproblems are needed and you want to avoid recursion overhead.
- Algorithms:
- Max Subset Sum No Adjacent -- 1D table: dp[i] = max(dp[i-1], dp[i-2] + arr[i])
- Kadane's Algorithm -- 1D running max: currentMax = max(arr[i], currentMax + arr[i])
- Min Number of Coins for Change -- 1D table indexed by target amount
- Number of Ways to Make Change -- 1D table: ways to compose each amount
- Min Number of Jumps -- 1D table: minimum jumps to reach each index
- Levenshtein Distance -- 2D table: edit distance between prefixes
- Longest Common Subsequence -- 2D table on two string prefixes
- Longest Increasing Subsequence -- 1D table or patience sorting
- Max Sum Increasing Subsequence -- 1D table tracking sum and predecessors
- Knapsack Problem -- 2D table: items x capacity
- Disk Stacking -- 1D DP after sorting, similar to LIS
- Max Profit with K Transactions -- 2D table: transactions x days
- Palindrome Partitioning Min Cuts -- 2D palindrome table + 1D cuts table
- Number of Ways to Traverse Graph -- 2D table on grid positions
- Maximize Expression -- multi-pass DP tracking best partial expressions
- Dice Throws -- 2D table: number of dice x target sum
- Juice Bottling -- 1D DP on bottle sizes for maximum revenue
- Square of Zeroes -- precomputed prefix sums + DP boundary checks
- Water Area -- precomputed left-max and right-max arrays (DP-style prefix/suffix)
- Maximum Sum Submatrix -- 2D prefix sums with DP submatrix computation
1.6 Backtracking
Description: Explore all candidates by building solutions incrementally, abandoning a path as soon as it violates constraints (pruning). Systematically enumerates possibilities.
- When to use: Constraint satisfaction, generating all valid configurations, puzzles, combinatorial problems.
- Algorithms:
- Solve Sudoku -- place digits, backtrack on constraint violation
- Non-Attacking Queens -- place queens row by row, prune invalid column/diagonal placements
- Permutations -- swap elements into position, recurse, swap back
- Powerset -- include/exclude each element to generate all subsets
- Phone Number Mnemonics -- expand each digit into its letter choices, backtrack through combinations
- Generate Div Tags -- track open/close counts, prune when close > open
- Boggle Board -- DFS with backtracking through adjacent cells matching trie words
- Valid IP Addresses -- try 1-3 digit segments, backtrack on invalid octets
- Reveal Minesweeper -- recursive flood-fill expansion with boundary backtracking
- Pattern Matcher -- try different lengths for pattern symbols, backtrack if the mapping fails
1.7 BFS / DFS
Description: Fundamental traversal strategies for trees and graphs. BFS explores level by level (using a queue); DFS explores as deep as possible first (using a stack or recursion).
BFS (Breadth-First Search)
- When to use: Shortest path in unweighted graphs, level-order traversal, minimum steps problems.
- Algorithms:
- Breadth-First Search -- basic graph BFS
- Minimum Passes of Matrix -- BFS from all positive cells simultaneously (multi-source BFS)
- River Sizes -- BFS/DFS from each unvisited water cell to measure connected components
- Remove Islands -- BFS from border cells to identify non-island regions
- Largest Island -- BFS to measure island sizes, then try flipping each zero
- Youngest Common Ancestor -- BFS-style ascent to equalize depths
- Knight Connection -- BFS to find minimum knight moves between two squares
- Find Nodes Distance K -- BFS from target node after building parent map
- Find Successor -- in-order successor via parent pointers or BFS-level reasoning
- Right Sibling Tree -- level-order BFS to connect siblings
- Two-Colorable -- BFS/DFS coloring to check bipartiteness
DFS (Depth-First Search)
- When to use: Path existence, cycle detection, topological sort, tree properties, exhaustive search.
- Algorithms:
- Depth-First Search -- basic graph DFS
- Cycle in Graph -- DFS with coloring (white/gray/black) to detect back edges
- Branch Sums -- DFS accumulating path sums to each leaf
- Node Depths -- DFS tracking depth at each node
- All Kinds of Node Depths -- DFS computing sum of depths from every node
- Binary Tree Diameter -- DFS returning height, tracking max diameter
- Max Path Sum in Binary Tree -- DFS returning max single-branch sum, tracking global max path
- Height-Balanced Binary Tree -- DFS returning height and balance status
- Compare Leaf Traversal -- DFS iterators on two trees comparing leaf sequences
- Invert Binary Tree -- DFS/BFS swapping children at every node
- Flatten Binary Tree -- in-order DFS rewiring into doubly linked list
- Split Binary Tree -- DFS computing subtree sums
- Symmetrical Tree -- parallel DFS on left and right subtrees
- Evaluate Expression Tree -- post-order DFS evaluating operators
- Two-Edge-Connected Graph -- DFS with discovery/low times for bridge detection
- Airport Connections -- DFS to find strongly connected components + graph analysis
- Detect Arbitrage -- Bellman-Ford (relaxation-based, related to graph traversal)
- Lowest Common Manager -- DFS returning report counts to find LCA
1.8 Union-Find (Disjoint Set Union)
Description: Maintain a partition of elements into disjoint sets. Supports near-O(1) union and find operations with path compression and union by rank.
- When to use: Connected components, cycle detection in undirected graphs, MST algorithms.
- Algorithms:
- Union-Find -- canonical implementation with path compression and union by rank
- Kruskal's Algorithm -- union-find to check if adding an edge creates a cycle during MST construction
- Largest Island -- union-find variant for merging island components
- Remove Islands -- can be solved via union-find connecting border-touching regions
- River Sizes -- union-find alternative to BFS for merging connected water cells
- Single Cycle Check -- conceptually related: verifying all elements belong to one cycle
- Two-Edge-Connected Graph -- union-find can assist in bridge detection
1.9 Monotonic Stack / Queue
Description: A stack (or deque) that maintains elements in sorted order. Elements are popped when they violate the monotonic property, enabling O(n) solutions for "next greater/smaller" patterns.
- When to use: Next greater/smaller element, histogram problems, temperature spans, stock spans.
- Algorithms:
- Next Greater Element -- monotonic decreasing stack; pop and assign when a greater element arrives
- Largest Rectangle Under Skyline -- monotonic increasing stack; compute area when a shorter bar is encountered
- Sunset Views -- monotonic stack tracking visible buildings from one direction
- Colliding Asteroids -- stack-based simulation resolving collisions
- Best Digits -- monotonic stack removing digits to maximize the remaining number
- Longest Park -- stack-based approach for park boundary processing
- Sort Stack -- recursive or iterative stack sorting using auxiliary stack logic
- Water Area -- can be solved with a monotonic stack approach (alternative to two-pointer/DP)
- Min-Max Stack Construction -- stack augmented with running min/max at each level
1.10 Binary Search Variations
Description: Eliminate half the search space at each step. Extends beyond searching a sorted array to searching over an abstract answer space.
Classic Binary Search
- When to use: Finding an element in sorted data.
- Algorithms:
- Binary Search -- standard O(log n) search in a sorted array
- Find Closest Value in BST -- binary search through a BST tracking closest
- Search in Sorted Matrix -- start from a corner, eliminate row or column each step
- Validate BST -- recursive range-checking (binary search property enforcement)
Search for a Range / Boundary
- When to use: Finding the first/last occurrence, or the boundary between valid and invalid.
- Algorithms:
- Search for Range -- two binary searches: one for left boundary, one for right boundary
- Shifted Binary Search -- binary search on a rotated sorted array
- Index Equals Value -- binary search for the fixed point where arr[i] == i
- Optimal Assembly Line -- binary search on the answer (time) to minimize cost
Answer Binary Search
- When to use: The answer itself is searchable -- binary search over possible answers checking feasibility.
- Algorithms:
- Optimal Assembly Line -- binary search on time, check if production target is feasible
- Median of Two Sorted Arrays -- binary search to find the correct partition point
1.11 Topological Sort
Description: Linear ordering of vertices in a DAG such that for every edge (u, v), u comes before v. Detects cycles in directed graphs.
- When to use: Dependency resolution, build systems, course scheduling, any DAG ordering.
- Algorithms:
- Topological Sort -- Kahn's algorithm (BFS with in-degree tracking) or DFS-based ordering
- Airport Connections -- topological reasoning on strongly connected components
- Cycle in Graph -- topological sort fails if graph has a cycle (detection mechanism)
1.12 Heap / Priority Queue
Description: A complete binary tree maintaining the heap property (min or max). Supports O(log n) insert/extract and O(1) peek.
- When to use: k-th largest/smallest, running medians, k-way merge, scheduling by priority.
- Algorithms:
- Min Heap Construction -- build, insert, remove, sift operations
- Continuous Median -- two heaps (max-heap for lower half, min-heap for upper half) tracking running median
- Merge Sorted Arrays -- min-heap for k-way merge of sorted arrays
- Sort K-Sorted Array -- min-heap of size k+1 to sort a nearly sorted array in O(n log k)
- Laptop Rentals -- min-heap tracking end times to count overlapping intervals
- Heap Sort -- build max-heap, repeatedly extract max
- Dijkstra's Algorithm -- min-heap for efficient next-vertex selection
- A Algorithm* -- min-heap (priority queue) ordered by f(n) = g(n) + h(n)
- Prim's Algorithm -- min-heap for selecting cheapest crossing edge
- Find Kth Largest Value in BST -- can use a heap or in-order traversal
1.13 Trie (Prefix Tree)
Description: A tree where each edge represents a character. Shared prefixes share paths. Enables O(L) lookup/insert for strings of length L.
- When to use: Prefix matching, autocomplete, word search in grids, string set membership.
- Algorithms:
- Suffix Trie Construction -- build a trie of all suffixes for substring queries
- Multi-String Search -- build a trie of patterns, search the big string against it
- Boggle Board -- trie of dictionary words guides DFS through the board
- Longest Most Frequent Prefix -- trie traversal tracking frequency at each node
- Shortest Unique Prefixes -- trie with subtree counts to find uniqueness boundaries
- Strings Made Up of Strings -- trie-based decomposition checking if strings can be formed from others
1.14 Linked List Techniques
Description: Specialized pointer manipulation techniques for singly and doubly linked lists.
Runner (Fast/Slow) Technique
- Find Loop -- Floyd's algorithm for cycle detection and start identification
- Middle Node -- fast pointer at 2x speed finds midpoint
- Linked List Palindrome -- find middle, reverse second half, compare
Reversal
- Reverse Linked List -- iterative three-pointer reversal (prev, current, next)
- Linked List Palindrome -- partial reversal for comparison
- Zip Linked List -- reverse second half, then interleave
Merge
- Merge Linked Lists -- merge two sorted lists with a dummy head
- Merging Linked Lists -- find intersection point of two lists
Rearrangement
- Rearrange Linked List -- partition around a value, then connect segments
- Node Swap -- swap adjacent pairs
- Shift Linked List -- rotate list by k positions
- Zip Linked List -- interleave first half with reversed second half
- Remove Kth Node from End -- two-pointer with k-gap to find target
Construction and Design
- Linked List Construction -- doubly linked list with insert, remove, search operations
- LRU Cache -- doubly linked list + hash map for O(1) access and eviction
- Sum of Linked Lists -- digit-by-digit addition with carry
2. Cross-Algorithm Connections
2.1 Monotonic Approaches Unite Different Problem Domains
| Algorithm | Category | Monotonic Technique |
|---|---|---|
| Water Area | Dynamic Programming | Monotonic stack or prefix max arrays |
| Largest Rectangle Under Skyline | Stacks | Monotonic increasing stack |
| Next Greater Element | Stacks | Monotonic decreasing stack |
| Sunset Views | Stacks | Monotonic stack for visibility |
| Best Digits | Stacks | Monotonic stack to maximize digits |
These problems appear in different categories (DP, Stacks, Arrays) yet all rely on maintaining monotonic ordering to efficiently process elements.
2.2 DP Substructure: "Take or Skip" Pattern
Several algorithms share the fundamental recurrence of choosing to include or exclude the current element:
| Algorithm | Recurrence Shape |
|---|---|
| Max Subset Sum No Adjacent | dp[i] = max(dp[i-1], dp[i-2] + val[i]) |
| Kadane's Algorithm | dp[i] = max(val[i], dp[i-1] + val[i]) |
| Knapsack Problem | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) |
| Longest Increasing Subsequence | dp[i] = max(dp[j] + 1) for j < i where a[j] < a[i] |
| Max Sum Increasing Subsequence | Same as LIS but summing values |
| Disk Stacking | LIS variant with 3D constraints |
| Longest String Chain | LIS variant on string containment |
| Staircase Traversal | dp[i] = sum of dp[i-k] for valid step sizes |
| Number of Ways to Make Change | dp[amount] += dp[amount - coin] |
2.3 BFS/DFS as Building Blocks for Graph Algorithms
Many "advanced" graph algorithms are composed of BFS or DFS as a subroutine:
- Topological Sort = DFS + post-order collection (or BFS + in-degree counting)
- Cycle in Graph = DFS + coloring states
- Airport Connections = DFS for SCCs + greedy on condensation graph
- Two-Edge-Connected Graph = DFS + discovery/low-link times
- Dijkstra's Algorithm = BFS generalized with a priority queue
- A Algorithm* = BFS generalized with a priority queue + heuristic
- Kruskal's Algorithm = sort edges + union-find (not BFS/DFS, but graph traversal adjacent)
- Two-Colorable = BFS/DFS with 2-color assignment
- River Sizes, Remove Islands, Largest Island = flood-fill BFS/DFS on a grid
- Reveal Minesweeper = flood-fill DFS with adjacency counting
2.4 Sorting as a Preprocessing Step
Sorting the input first enables simpler or more efficient algorithms in a different category:
| Algorithm | How Sorting Helps |
|---|---|
| Three Number Sum | Enables two-pointer convergence |
| Smallest Difference | Enables two-pointer convergence across two arrays |
| Class Photos | Enables greedy row assignment by height |
| Tandem Bicycle | Enables greedy optimal pairing |
| Task Assignment | Enables greedy shortest+longest pairing |
| Merge Overlapping Intervals | Sort by start time, then merge in one pass |
| Non-Constructible Change | Sort coins to greedily extend range |
| Disk Stacking | Sort by one dimension to apply LIS-like DP |
| Laptop Rentals | Sort by start time for heap-based processing |
| Sweet and Savory | Sort to enable two-pointer pairing |
| Calendar Matching | Sort availability windows for interval merging |
| Min Rewards | Sort-based reasoning for local minima/maxima |
2.5 Hash Map as the Unifying Accelerator
Hash maps provide O(1) lookup and appear as the key optimization in many algorithms across categories:
- Two Number Sum -- store complements for O(n) lookup
- Four Number Sum -- store pair sums for O(n^2) instead of O(n^3)
- First Duplicate Value -- track seen values
- Zero Sum Subarray -- store prefix sums to detect zero-sum ranges
- Largest Range -- mark visited values for O(n) range expansion
- Tournament Winner -- count wins per team
- Group Anagrams -- sorted-string keys to group anagrams
- First Non-Repeating Character -- character frequency map
- LRU Cache -- hash map for O(1) node access in the linked list
- Longest Substring Without Duplicates -- track last occurrence of each character
2.6 Tree Recursion Patterns
Many binary tree algorithms share the same DFS skeleton: recurse on left and right subtrees, combine results, optionally track a global variable:
"Return info upward" pattern:
- Binary Tree Diameter -- return height, update global max diameter
- Max Path Sum -- return max branch sum, update global max path
- Height-Balanced Binary Tree -- return (height, isBalanced)
- Split Binary Tree -- return subtree sum, check if half equals total/2
- Sum BSTs -- return (min, max, sum, isBST) upward
"Pass info downward" pattern:
- Branch Sums -- pass running sum down, collect at leaves
- Node Depths -- pass current depth down, accumulate
- Validate BST -- pass valid range (min, max) downward
2.7 Prefix Sum Connections
Several algorithms rely on precomputing prefix sums or prefix aggregates:
- Zero Sum Subarray -- prefix sum in a set; duplicate means zero-sum subrange
- Water Area -- prefix max from left, suffix max from right
- Maximum Sum Submatrix -- 2D prefix sums for O(1) submatrix sum queries
- Square of Zeroes -- prefix counts of consecutive zeroes in each direction
- Subarray Sort -- prefix/suffix reasoning about out-of-order boundaries
2.8 Interval and Scheduling Problems
These algorithms deal with intervals, ranges, or time windows:
- Merge Overlapping Intervals -- sort by start, merge touching intervals
- Laptop Rentals -- count max overlapping intervals (min-heap of end times)
- Calendar Matching -- merge availability windows, find common free slots
- Optimal Freelancing -- deadline scheduling for maximum profit
- Task Assignment -- pair tasks to minimize total parallel time
3. When to Use Which Pattern -- Decision Guide
By Input Type
INPUT IS AN ARRAY:
|
|-- Is it sorted?
| |-- Yes --> Binary Search, Two Pointers
| |-- No --> Consider sorting first, or use Hash Map
|
|-- Looking for subarrays/substrings?
| |-- Contiguous? --> Sliding Window, Prefix Sum, Kadane's
| |-- Non-contiguous? --> DP (subsequence), Backtracking
|
|-- Looking for pairs/triplets?
| |-- Sort + Two Pointers, or Hash Map
|
|-- Next greater/smaller element?
|-- Monotonic Stack
INPUT IS A STRING:
|
|-- Substring search? --> Sliding Window, KMP, Trie
|-- Prefix matching? --> Trie
|-- Edit distance / comparison? --> 2D DP
|-- Generate all arrangements? --> Backtracking
|-- Palindrome? --> Two Pointers, DP (expansion or table)
INPUT IS A TREE:
|
|-- Need to visit all nodes? --> DFS (usually simpler) or BFS
|-- Level-order needed? --> BFS with queue
|-- Need info from subtrees? --> Post-order DFS returning values up
|-- Need info from root? --> Pre-order DFS passing values down
|-- BST property? --> Binary Search logic (go left or right)
INPUT IS A GRAPH:
|
|-- Shortest path (unweighted)? --> BFS
|-- Shortest path (weighted, no negatives)? --> Dijkstra's
|-- Shortest path (weighted, with negatives)? --> Bellman-Ford
|-- Connected components? --> BFS/DFS or Union-Find
|-- Cycle detection (directed)? --> DFS with coloring
|-- Cycle detection (undirected)? --> Union-Find or DFS
|-- Dependency ordering? --> Topological Sort
|-- Minimum spanning tree? --> Kruskal's (Union-Find) or Prim's (Heap)
|-- Grid-based? --> BFS/DFS treating cells as nodes
INPUT IS A MATRIX/GRID:
|
|-- Flood fill / connected regions? --> BFS/DFS
|-- Sorted rows and columns? --> Search in Sorted Matrix (staircase)
|-- Path counting? --> 2D DP
|-- Submatrix queries? --> 2D Prefix Sums
By What Is Being Asked
FIND OPTIMAL VALUE (min/max):
--> DP if overlapping subproblems exist
--> Greedy if local optimum = global optimum
--> Binary Search on answer if feasibility is checkable
COUNT number of ways:
--> DP (ways to make change, ways to traverse graph, staircase)
--> Backtracking if enumeration is needed and n is small
FIND ALL valid configurations:
--> Backtracking (permutations, sudoku, n-queens, powerset)
FIND EXISTENCE (does a path/solution exist):
--> BFS/DFS for reachability
--> Union-Find for connectivity
--> DP for feasibility
VALIDATE a structure:
--> DFS/BFS with constraint checking (validate BST, balanced tree)
--> Two Pointers (palindrome check, validate subsequence)
DETECT a cycle:
--> Floyd's (linked list)
--> DFS with coloring (directed graph)
--> Union-Find (undirected graph)
By Constraints
n <= 20-25:
--> Backtracking, bitmask DP, brute force are feasible (2^n solutions)
--> Non-Attacking Queens, Solve Sudoku
n <= 10^3 to 10^4:
--> O(n^2) DP is feasible
--> Levenshtein Distance, Longest Common Subsequence, Knapsack
n <= 10^5 to 10^6:
--> Need O(n log n) or O(n) algorithms
--> Sorting + Two Pointers, Sliding Window, Monotonic Stack, Heap
Sorted input given:
--> Binary Search variants
--> Two Pointers from both ends
--> Merge operations
Need all solutions:
--> Backtracking (exponential is unavoidable)
Need one optimal solution:
--> DP (with backtracking through DP table for reconstruction)
--> Greedy (if applicable)
4. Complexity Trade-off Patterns
4.1 Hash Map: O(1) Lookup vs O(n) Space
| Without Hash Map | With Hash Map | Algorithms |
|---|---|---|
| O(n^2) nested scan | O(n) single pass | Two Number Sum, First Duplicate Value, Zero Sum Subarray |
| O(n^3) triple loop | O(n^2) with pair sums | Four Number Sum |
| O(n * m) repeated search | O(n + m) | Tournament Winner, Generate Document |
| O(n log n) sorted search | O(n) average | Largest Range, Group Anagrams |
Trade-off: Every hash map solution trades O(n) additional space for a reduction of one factor of n in time complexity. This is almost always worthwhile unless memory is severely constrained.
4.2 Sorting Preprocessing: O(n log n) Upfront, Faster Operations After
| Unsorted Approach | Sorted Approach | Net Gain |
|---|---|---|
| O(n^2) pair finding | O(n log n) sort + O(n) two-pointer | O(n^2) -> O(n log n) |
| O(n^2) merge intervals | O(n log n) sort + O(n) merge | O(n^2) -> O(n log n) |
| O(n) per query in unsorted | O(log n) per query via binary search | Amortized gains with many queries |
Algorithms that benefit: Three Number Sum, Smallest Difference, Merge Overlapping Intervals, Class Photos, Tandem Bicycle, Laptop Rentals, Disk Stacking, Sweet and Savory.
Trade-off: Sorting costs O(n log n) and may discard original ordering. If original order matters, use an index array or copy.
4.3 DP Table vs Recursive + Memoization
| Tabulation (Bottom-Up) | Memoization (Top-Down) |
|---|---|
| No recursion overhead | Natural recursive structure |
| Iterative, cache-friendly | May skip unneeded subproblems |
| Explicit iteration order | Implicit via call stack |
| Fixed space pattern | Stack space proportional to depth |
| Easier to optimize space | Harder to reduce space |
Space optimization in tabulation: Many 2D DP problems only depend on the previous row, allowing reduction from O(n*m) to O(min(n,m)):
- Levenshtein Distance -- only needs previous row -> O(min(n,m)) space
- Longest Common Subsequence -- only needs previous row
- Number of Ways to Traverse Graph -- only needs previous row
- Knapsack Problem -- can use 1D array with reverse iteration
Space optimization in 1D DP: Some 1D problems only need the last 2 values:
- Max Subset Sum No Adjacent -- O(1) space with two variables
- Nth Fibonacci -- O(1) space with two variables
- Kadane's Algorithm -- O(1) space with running max
4.4 Iterative vs Recursive Space
| Recursive | Iterative | Trade-off |
|---|---|---|
| O(n) or O(h) call stack | O(1) extra space | Stack overflow risk vs complexity |
| Cleaner code for trees | Explicit stack management | Readability vs safety |
Algorithms with both options:
- BST Traversal -- recursive is natural; iterative avoids O(h) stack for in-order
- Iterative In-Order Traversal -- uses O(1) space with parent pointers (Morris traversal)
- DFS -- recursive or explicit stack
- Reverse Linked List -- both are O(1) space iteratively, but recursive uses O(n) stack
- Node Depths -- recursive DFS or iterative BFS, same time, different stack usage
4.5 In-Place vs Extra Space Algorithms
| Extra Space | In-Place | Algorithms |
|---|---|---|
| O(n) output array | O(1) swaps | Move Element to End (in-place swap), Three Number Sort (Dutch flag) |
| O(n) visited set | Mark in input | First Duplicate Value (negate values), Reveal Minesweeper (modify grid) |
| O(n) result array | O(1) pointer manipulation | Reverse Linked List, Rearrange Linked List, Flatten Binary Tree |
| O(n) sorted copy | O(1) in-place sort | Insertion Sort, Selection Sort, Bubble Sort, Heap Sort, Quick Sort |
Trade-off: In-place algorithms save memory but often mutate the input, which may not be acceptable. They can also be harder to implement correctly.
4.6 Adjacency Matrix vs Adjacency List
| Matrix O(V^2) space | List O(V+E) space | When to Choose |
|---|---|---|
| O(1) edge lookup | O(degree) edge lookup | Dense graph -> matrix; sparse -> list |
| Simple implementation | Memory efficient | Most real graphs are sparse |
Algorithms: Most graph algorithms in this collection (BFS, DFS, Dijkstra's, Topological Sort, Kruskal's, Prim's, A*) use adjacency lists. Detect Arbitrage uses a matrix representation since it runs Bellman-Ford over all edges.
4.7 The Preprocessing Investment Pattern
Some algorithms invest O(n) or O(n^2) in preprocessing to answer subsequent queries or simplify the main logic:
| Preprocessing | Main Benefit | Algorithms |
|---|---|---|
| Build suffix trie O(n^2) | O(m) substring search | Suffix Trie Construction |
| Build trie O(sum of lengths) | O(L) per lookup | Multi-String Search, Boggle Board |
| Compute prefix sums O(n) | O(1) range sums | Zero Sum Subarray, Maximum Sum Submatrix |
| Compute left/right max O(n) | O(1) water level per bar | Water Area |
| Build parent map O(n) | O(k) BFS from target | Find Nodes Distance K |
| Compute palindrome table O(n^2) | O(n) min cuts | Palindrome Partitioning Min Cuts |
| Build KMP failure function O(m) | O(n) string matching | Knuth-Morris-Pratt Algorithm |
Quick Reference: Algorithm to Primary Strategy Mapping
| Algorithm | Primary Strategy | Secondary Strategy |
|---|---|---|
| Two Number Sum | Hash Map | Two Pointers |
| Validate Subsequence | Two Pointers | -- |
| Sorted Squared Array | Two Pointers | -- |
| Tournament Winner | Hash Map | -- |
| Non-Constructible Change | Greedy (sort) | -- |
| Three Number Sum | Two Pointers | Sorting |
| Smallest Difference | Two Pointers | Sorting |
| Move Element to End | Two Pointers | -- |
| Monotonic Array | Linear Scan | -- |
| Spiral Traverse | Simulation | -- |
| Longest Peak | Linear Scan | -- |
| Array of Products | Prefix/Suffix | -- |
| First Duplicate Value | Hash Map / In-place | -- |
| Merge Overlapping Intervals | Sorting + Greedy | -- |
| Four Number Sum | Hash Map | -- |
| Subarray Sort | Linear Scan | -- |
| Largest Range | Hash Map | -- |
| Min Rewards | Greedy (two-pass) | -- |
| Zigzag Traverse | Simulation | -- |
| Apartment Hunting | Prefix/Suffix DP | -- |
| Calendar Matching | Interval Merge | Sorting |
| Waterfall Streams | Simulation | -- |
| Minimum Area Rectangle | Hash Map | -- |
| Line Through Points | Hash Map | Math |
| Best Seat | Linear Scan | -- |
| Zero Sum Subarray | Prefix Sum + Hash | -- |
| Missing Numbers | Math / Hash | -- |
| Majority Element | Boyer-Moore | -- |
| Sweet and Savory | Two Pointers | Sorting |
| Longest Subarray With Sum | Sliding Window | -- |
| Count Squares | Math + DP | -- |
| Transpose Matrix | Simulation | -- |
| Knight Connection | BFS | -- |
| BST Construction | BST | -- |
| Validate BST | DFS + Ranges | -- |
| BST Traversal | DFS | -- |
| Min Height BST | Divide and Conquer | -- |
| Find Closest Value in BST | Binary Search | -- |
| Find Kth Largest in BST | In-order DFS | -- |
| Reconstruct BST | Preorder + Ranges | -- |
| Same BSTs | Recursive comparison | -- |
| Validate Three Nodes | BST traversal | -- |
| Right Smaller Than | BST / Merge Sort | -- |
| Repair BST | In-order DFS | -- |
| Sum BSTs | Post-order DFS | -- |
| Branch Sums | DFS | -- |
| Node Depths | DFS | -- |
| Invert Binary Tree | DFS/BFS | -- |
| Binary Tree Diameter | DFS | -- |
| Find Successor | In-order / Parent | -- |
| Height-Balanced Binary Tree | DFS | -- |
| Max Path Sum | DFS | -- |
| Find Nodes Distance K | BFS + Parent Map | -- |
| Iterative In-Order Traversal | Stack / Morris | -- |
| Flatten Binary Tree | In-order DFS | -- |
| Right Sibling Tree | BFS (level-order) | -- |
| All Kinds of Node Depths | DFS | Math |
| Compare Leaf Traversal | DFS Iterators | -- |
| Merge Binary Trees | DFS | -- |
| Symmetrical Tree | DFS | -- |
| Split Binary Tree | DFS (subtree sums) | -- |
| Evaluate Expression Tree | Post-order DFS | -- |
| Max Subset Sum No Adjacent | 1D DP | -- |
| Number of Ways to Make Change | 1D DP | -- |
| Min Number of Coins for Change | 1D DP | -- |
| Levenshtein Distance | 2D DP | -- |
| Number of Ways to Traverse Graph | 2D DP | -- |
| Max Sum Increasing Subsequence | 1D DP (LIS variant) | -- |
| Longest Common Subsequence | 2D DP | -- |
| Longest Increasing Subsequence | 1D DP | Binary Search |
| Water Area | DP (prefix/suffix) | Monotonic Stack |
| Knapsack Problem | 2D DP | -- |
| Disk Stacking | 1D DP (LIS variant) | Sorting |
| Min Number of Jumps | 1D DP / Greedy | -- |
| Numbers in Pi | Memoization | Trie |
| Max Profit with K Transactions | 2D DP | -- |
| Palindrome Partitioning Min Cuts | DP | Precomputed palindrome table |
| Longest String Chain | Memoization | Hash Map |
| Square of Zeroes | DP + Prefix Sums | -- |
| Maximize Expression | Multi-pass DP | -- |
| Dice Throws | 2D DP | -- |
| Juice Bottling | 1D DP | -- |
| Maximum Sum Submatrix | 2D Prefix Sums | -- |
| Kadane's Algorithm | 1D DP (O(1) space) | -- |
| Dijkstra's Algorithm | BFS + Heap | -- |
| Topological Sort | DFS / BFS | -- |
| Knuth-Morris-Pratt | Preprocessing (failure fn) | -- |
| A* Algorithm | BFS + Heap + Heuristic | -- |
| Prim's Algorithm | Greedy + Heap | -- |
| Kruskal's Algorithm | Greedy + Union-Find | Sorting |
| Stable Internships | Greedy (Gale-Shapley) | -- |
| Union-Find | Union-Find | -- |
| BFS | BFS | -- |
| DFS | DFS | -- |
| Cycle in Graph | DFS + Coloring | -- |
| River Sizes | BFS/DFS (flood fill) | -- |
| Remove Islands | BFS/DFS (border) | -- |
| Youngest Common Ancestor | DFS / Ascent | -- |
| Single Cycle Check | Traversal | -- |
| Minimum Passes of Matrix | Multi-source BFS | -- |
| Boggle Board | DFS + Trie | Backtracking |
| Rectangle Mania | Hash Map | -- |
| Two-Colorable | BFS/DFS | -- |
| Airport Connections | DFS (SCCs) | Greedy |
| Detect Arbitrage | Bellman-Ford | -- |
| Two-Edge-Connected Graph | DFS + Low-link | -- |
| Largest Island | BFS/DFS + Union-Find | -- |
| Minimum Waiting Time | Greedy | Sorting |
| Class Photos | Greedy | Sorting |
| Tandem Bicycle | Greedy | Sorting |
| Task Assignment | Greedy | Sorting |
| Optimal Freelancing | Greedy | Sorting |
| Valid Starting City | Greedy / Math | -- |
| Min Heap Construction | Heap | -- |
| Continuous Median | Two Heaps | -- |
| Sort K-Sorted Array | Heap | -- |
| Laptop Rentals | Heap | Sorting |
| Merge Sorted Arrays | Heap (k-way merge) | -- |
| Remove Duplicates from LL | Linear Scan | -- |
| Linked List Construction | Linked List | -- |
| Middle Node | Fast/Slow Pointers | -- |
| Reverse Linked List | Pointer Reversal | -- |
| Merge Linked Lists | Two Pointers | -- |
| Find Loop | Fast/Slow Pointers | -- |
| Remove Kth Node from End | Two Pointers (k-gap) | -- |
| Sum of Linked Lists | Simulation | -- |
| Linked List Palindrome | Fast/Slow + Reversal | -- |
| Rearrange Linked List | Partitioning | -- |
| Zip Linked List | Reversal + Merge | -- |
| Node Swap | Pointer Manipulation | -- |
| Shift Linked List | Length + Pointer | -- |
| Merging Linked Lists | Two Pointers | -- |
| LRU Cache | Hash Map + Linked List | -- |
| Nth Fibonacci | DP (O(1) space) | -- |
| Product Sum | DFS / Recursion | -- |
| Permutations | Backtracking | -- |
| Powerset | Backtracking | -- |
| Phone Number Mnemonics | Backtracking | -- |
| Staircase Traversal | DP / Memoization | Sliding Window |
| Lowest Common Manager | DFS | -- |
| Interweaving Strings | 2D DP / Memoization | -- |
| Solve Sudoku | Backtracking | -- |
| Ambiguous Measurements | Memoization | -- |
| Generate Div Tags | Backtracking | -- |
| Non-Attacking Queens | Backtracking | -- |
| Number of Binary Tree Topologies | Memoization | -- |
| Blackjack Probability | Memoization | -- |
| Reveal Minesweeper | DFS (flood fill) | -- |
| Binary Search | Binary Search | -- |
| Find Three Largest Numbers | Linear Scan | -- |
| Search in Sorted Matrix | Binary Search (staircase) | -- |
| Shifted Binary Search | Binary Search | -- |
| Search for Range | Binary Search | -- |
| Quickselect | Divide and Conquer | -- |
| Index Equals Value | Binary Search | -- |
| Median of Two Sorted Arrays | Binary Search | -- |
| Optimal Assembly Line | Answer Binary Search | -- |
| Bubble Sort | Comparison Sort | -- |
| Insertion Sort | Comparison Sort | -- |
| Selection Sort | Comparison Sort | -- |
| Quick Sort | Divide and Conquer | -- |
| Merge Sort | Divide and Conquer | -- |
| Heap Sort | Heap | -- |
| Radix Sort | Non-comparison Sort | -- |
| Three Number Sort | Dutch National Flag | -- |
| Count Inversions | Divide and Conquer | Merge Sort |
| Balanced Brackets | Stack | -- |
| Sunset Views | Monotonic Stack | -- |
| Next Greater Element | Monotonic Stack | -- |
| Sort Stack | Stack (recursive) | -- |
| Min-Max Stack Construction | Stack (augmented) | -- |
| Shorten Path | Stack | String Processing |
| Largest Rectangle Under Skyline | Monotonic Stack | -- |
| Reverse Polish Notation | Stack | -- |
| Best Digits | Monotonic Stack | Greedy |
| Colliding Asteroids | Stack | -- |
| Longest Park | Stack | -- |
| Palindrome Check | Two Pointers | -- |
| Caesar Cipher Encryptor | Math / Modular | -- |
| Run-Length Encoding | Linear Scan | -- |
| Common Characters | Hash Map | -- |
| Generate Document | Hash Map | -- |
| First Non-Repeating Character | Hash Map | -- |
| Longest Substring Without Duplicates | Sliding Window | Hash Map |
| Group Anagrams | Hash Map | Sorting |
| Valid IP Addresses | Backtracking | -- |
| Reverse Words in String | Two Pointers | -- |
| Minimum Characters for Words | Hash Map | -- |
| Longest Palindromic Substring | Expand from Center | DP |
| Longest Balanced Substring | Stack / DP | -- |
| Smallest Substring Containing | Sliding Window | Hash Map |
| Pattern Matcher | Backtracking / Math | -- |
| One Edit | Linear Scan | -- |
| Semordnilap | Hash Map | -- |
| Underscorify Substring | Interval Merge | String Search |
| Suffix Trie Construction | Trie | -- |
| Multi-String Search | Trie | -- |
| Longest Most Frequent Prefix | Trie | -- |
| Shortest Unique Prefixes | Trie | -- |
| Strings Made Up of Strings | Trie + DP | -- |