Common Algorithm Patterns Cheat Sheet
Master these 15 patterns to solve 90% of coding interview questions
Why Learn Patterns?
Instead of memorizing 500 problems, learn 15 patterns that apply across hundreds of problems. Pattern recognition is key to interview success.
Pattern 1: Sliding Window
Use When: Contiguous subarray/substring problems
Approach:
- Expand window by moving right pointer
- Shrink window when condition violated (move left pointer)
- Track best result seen so far
Time: O(n) | Space: O(1) or O(k) for hash map
Classic Problems:
- Longest Substring Without Repeating Characters — grow the window and, on a repeat, jump the left edge past the last index of that character; keep a hash map of last-seen positions and track the max length.
- Minimum Window Substring — expand until the window covers every target character, then shrink from the left to find the smallest valid one. Interviewers often follow up with how you handle duplicate characters in the target.
- Maximum Sum Subarray of Size K — the fixed-window template: add the entering element, drop the leaving one, keep the running max in O(n).
- Longest Substring with K Distinct Characters — a variable window with a character-count map; shrink from the left the moment you exceed K distinct.
Template:
left = 0
for right in range(len(arr)):
# Expand window
add arr[right] to window
while window_condition_violated:
# Shrink window
remove arr[left] from window
left += 1
# Update result
result = max(result, right - left + 1)
Pattern 2: Two Pointers
Use When: Sorted array, find pairs/triplets, reverse/palindrome
Approach:
- Two pointers start at different positions
- Move pointers based on condition
- Often used with sorted arrays
Time: O(n) | Space: O(1)
Classic Problems:
- Two Sum (sorted array) — move left inward when the sum is too small and right inward when it is too big; the sorted order gives O(n) with no hash map.
- Remove Duplicates from Sorted Array — a slow write pointer marks the next unique slot while a fast pointer scans ahead, editing in place.
- Valid Palindrome — compare from both ends inward, skipping non-alphanumeric characters; a common follow-up allows one deletion.
- Container With Most Water — always move the pointer at the shorter wall, since that is the only move that can grow the area.
- 3Sum, 4Sum — sort, fix one or two elements, then two-pointer the rest; interviewers watch closely for how you skip duplicates to avoid repeated triplets.
Template:
left, right = 0, len(arr) - 1
while left < right:
if condition_met:
process_result()
left += 1
right -= 1
elif sum < target:
left += 1
else:
right -= 1
Pattern 3: Fast & Slow Pointers
Use When: Detect cycles, find middle, find kth from end
Approach:
- Fast pointer moves 2 steps
- Slow pointer moves 1 step
- When fast reaches end, slow is at middle
Time: O(n) | Space: O(1)
Classic Problems:
- Detect Cycle in Linked List — if fast and slow ever land on the same node there is a cycle; if fast reaches null there is not.
- Find Middle of Linked List — when fast hits the end, slow sits at the midpoint, which is the first step for sorting or splitting a list.
- Linked List Cycle II (find cycle start) — after the two meet, reset one pointer to the head and advance both one step at a time; they meet at the cycle’s start (Floyd’s algorithm).
- Happy Number — treat the chain of digit-square sums as a linked list and detect the cycle to prove it never reaches 1.
- Palindrome Linked List — find the middle, reverse the second half, then compare the halves; be ready to restore the list afterward.
Pattern 4: Binary Search
Use When: Sorted data, search space can be halved
Approach:
- Define search space [left, right]
- Check middle element
- Eliminate half based on comparison
Time: O(log n) | Space: O(1)
Classic Problems:
- Binary Search — the baseline; the detail interviewers probe is the loop condition and mid calculation that avoid infinite loops and overflow.
- First Bad Version — binary search for the boundary between good and bad versions, minimizing the number of API calls.
- Search in Rotated Sorted Array — figure out which half is sorted, then check whether the target falls inside that half.
- Find Peak Element — step toward the higher neighbor; a peak is guaranteed in O(log n) even though the array is not fully sorted.
- Search a 2D Matrix — treat the grid as one sorted array with index math, or walk in from the top-right corner.
Pattern 5: Merge Intervals
Use When: Overlapping intervals, scheduling
Approach:
- Sort intervals by start time
- Iterate and merge overlapping
Time: O(n log n) | Space: O(n)
Classic Problems:
- Merge Intervals — sort by start, then extend the current interval whenever the next one begins before it ends.
- Insert Interval — the input is already sorted, so merge the new interval in a single pass instead of re-sorting.
- Meeting Rooms I & II — I asks whether any two meetings overlap; II asks for the minimum rooms, solved with a min-heap of end times or a sweep line.
- Non-overlapping Intervals — greedily keep the interval that ends earliest so you remove the fewest to make the rest disjoint.
Pattern 6: Breadth-First Search (BFS)
Use When: Level-order traversal, shortest path in unweighted graph
Approach:
- Use queue (FIFO)
- Process level by level
- Mark visited to avoid cycles
Time: O(V + E) | Space: O(V)
Classic Problems:
- Binary Tree Level Order Traversal — record the queue size at the start of each iteration to process exactly one level at a time.
- Minimum Depth of Binary Tree — BFS returns at the first leaf it reaches, which is why it beats DFS on this one.
- Number of Islands (alternative to DFS) — flood-fill each unvisited land cell with BFS, counting one island per starting cell.
- Word Ladder — make each word a node and one-letter changes the edges; BFS gives the shortest transformation length.
- Rotting Oranges — multi-source BFS from every rotten orange at once, where the answer is the number of levels processed.
Pattern 7: Depth-First Search (DFS)
Use When: Explore all paths, backtracking, tree/graph traversal
Approach:
- Use recursion or stack
- Go deep before going wide
- Backtrack when needed
Time: O(V + E) | Space: O(V) for recursion stack
Classic Problems:
- Number of Islands — recurse into connected land cells and mark them visited; the DFS counterpart to the BFS version above.
- Clone Graph — DFS while keeping a map from each original node to its copy so cycles do not cause infinite recursion.
- Path Sum in Binary Tree — carry the running total down each branch and check it at the leaf against the target.
- Course Schedule (cycle detection) — DFS with three states (unvisited, visiting, visited); an edge back to a “visiting” node means a cycle.
- Word Search in Grid — backtracking DFS that marks the current cell as used and unmarks it when the branch returns.
Pattern 8: Backtracking
Use When: Generate all combinations/permutations, constraint satisfaction
Approach:
- Make a choice
- Explore with that choice
- Undo choice (backtrack)
- Try next choice
Time: O(2^n) or O(n!) typically | Space: O(n)
Classic Problems:
- Permutations — use a swap or a used[] flag so each recursion level places one unused element into one position.
- Combinations — pass a start index so you never reuse earlier elements or produce the same set twice.
- Subsets — at each index choose to include or skip the element, which builds all 2^n subsets.
- N-Queens — place one queen per row and prune with column and diagonal sets before recursing deeper.
- Generate Parentheses — add “(” only while open brackets remain and “)” only while the string stays balanced.
- Palindrome Partitioning — cut at every position where the prefix is a palindrome, then recurse on the remainder.
Template:
def backtrack(state, choices):
if is_solution(state):
add_to_results(state)
return
for choice in choices:
make_choice(choice)
backtrack(new_state, remaining_choices)
undo_choice(choice) # Backtrack!
Pattern 9: Dynamic Programming
Use When: Optimal substructure + overlapping subproblems
Approach:
- Define state
- Find recurrence relation
- Memoize (top-down) or tabulate (bottom-up)
Time: O(n²) typically | Space: O(n) or O(n²)
Classic Problems:
- Fibonacci, Climbing Stairs — the entry point to DP; each state depends on the previous two, so O(1) space is enough.
- Coin Change — an unbounded-knapsack setup where dp[amount] holds the fewest coins, iterating coins over amounts.
- Longest Common Subsequence — a 2D table over the two strings and the base pattern behind file-diff tools.
- 0/1 Knapsack — each item is take-or-leave; interviewers extend the capacity-versus-value table into many variations.
- Edit Distance — 2D DP over insert, delete, and replace, and a frequent hard-tier question.
- Longest Increasing Subsequence — O(n²) with straight DP, or O(n log n) using a patience-sorting binary search.
Pattern 10: Greedy
Use When: Local optimal choices lead to global optimal
Approach:
- Make best choice at each step
- Don’t reconsider past choices
- Prove greedy choice is safe
Time: Varies | Space: Usually O(1)
Classic Problems:
- Jump Game — track the farthest index reachable so far; you succeed if that reach ever covers the last index.
- Gas Station — if total gas is at least total cost, the answer is the station right after the largest running deficit.
- Meeting Rooms II — sort start and end times, then sweep to count how many meetings run at once.
- Minimum Platforms — the train-station twin of Meeting Rooms II, counting the peak number of simultaneous trains.
- Fractional Knapsack — sort by value-per-weight and take greedily; unlike 0/1, allowing fractions makes greedy provably optimal.
Pattern 11: Topological Sort
Use When: Dependency resolution, task scheduling
Approach:
- Kahn’s Algorithm (BFS with in-degree)
- DFS with post-order traversal
- Detect cycles (impossible to sort if cycle exists)
Time: O(V + E) | Space: O(V + E)
Classic Problems:
- Course Schedule I & II — I checks whether the prerequisite graph is acyclic; II returns an actual valid ordering.
- Alien Dictionary — derive letter-ordering edges from adjacent words in the list, then topologically sort the alphabet.
- Sequence Reconstruction — verify the topological order is unique, meaning the queue never holds more than one node at a time.
- Minimum Height Trees — trim leaf nodes layer by layer until only the one or two center nodes are left.
Pattern 12: Union-Find (Disjoint Set)
Use When: Connectivity, grouping, cycle detection
Approach:
- Union: Connect two elements
- Find: Determine which set element belongs to
- Use path compression + union by rank
Time: O(α(n)) ≈ O(1) with optimizations | Space: O(n)
Classic Problems:
- Number of Connected Components — union every edge, then count the distinct roots that remain.
- Graph Valid Tree — a valid tree has exactly n-1 edges and no union that joins two already-connected nodes.
- Accounts Merge — union accounts that share an email, then group the results by root.
- Redundant Connection — the edge that connects two already-joined nodes is the one closing the cycle, so remove it.
- Number of Islands II — process land additions online, unioning with existing neighbors and updating the island count as you go.
Pattern 13: Top K Elements
Use When: Finding k largest/smallest, k closest, k frequent
Approach:
- Use min/max heap of size k
- For k largest: use min heap
- For k smallest: use max heap
Time: O(n log k) | Space: O(k)
Classic Problems:
- Kth Largest Element — a size-k min-heap keeps the k largest values, or quickselect gets it in O(n) average time.
- Top K Frequent Elements — count with a hash map, then pull the top k with a heap or a bucket sort by frequency.
- K Closest Points to Origin — a max-heap of size k keyed on squared distance, so you never compute a square root.
- Find K Pairs with Smallest Sums — push promising pairs into a min-heap and pop k times to build the answer.
- Reorganize String — repeatedly place the most frequent remaining character using a max-heap so no two neighbors match.
Pattern 14: Modified Binary Search
Use When: Sorted but rotated/modified, find boundary
Approach:
- Identify which half is sorted
- Check if target in sorted half
- Search appropriate half
Time: O(log n) | Space: O(1)
Classic Problems:
- Search in Rotated Sorted Array — find the sorted half at each step, then decide which side can contain the target.
- Find Minimum in Rotated Sorted Array — compare mid against the right end to learn which side holds the rotation point.
- Find First and Last Position — run binary search twice, biased left then right, to pin down both boundaries.
- Single Element in Sorted Array — use the index parity of pairs to binary-search the one unpaired element in O(log n).
Pattern 15: Monotonic Stack/Queue
Use When: Next greater/smaller element, sliding window max/min
Approach:
- Maintain increasing or decreasing order in stack/deque
- Remove elements that violate monotonic property
- Each element added and removed once → O(n)
Time: O(n) | Space: O(n)
Classic Problems:
- Next Greater Element — keep a decreasing stack; when a bigger value arrives, every element it pops has found its next greater.
- Daily Temperatures — the index version of Next Greater, storing indices so you can compute the gap in days.
- Sliding Window Maximum — a monotonic deque holds candidate maxima and drops indices that slide out of the window.
- Largest Rectangle in Histogram — a stack finds, for each bar, how far it stretches left and right at its own height.
- Trapping Rain Water — a stack or two pointers bound the water above each position by the shorter surrounding wall.
How to Identify the Pattern
| Keyword/Clue | Pattern |
|---|---|
| Contiguous subarray/substring | Sliding Window |
| Find pairs, sorted array | Two Pointers |
| Cycle detection, find middle | Fast & Slow Pointers |
| Sorted array, O(log n) | Binary Search |
| Overlapping intervals | Merge Intervals |
| Shortest path, level order | BFS |
| All paths, graph/tree traversal | DFS |
| Generate all combinations | Backtracking |
| Optimal substructure | Dynamic Programming |
| Local optimum → global | Greedy |
| Dependencies, prerequisites | Topological Sort |
| Connectivity, grouping | Union-Find |
| K largest/smallest/frequent | Top K Elements (Heap) |
| Next greater/smaller | Monotonic Stack |
Study Strategy
- Learn one pattern at a time (1-2 patterns per week)
- Solve 5-10 problems using that pattern
- Understand why the pattern works, don’t just memorize
- Mix patterns after learning all 15
- Practice identifying which pattern to use
Master these 15 patterns and you’ll be prepared for 90% of coding interviews!
