20 Problem-Solving Patterns
Recognize useful structures in a problem, check their assumptions, and choose an approach you can explain.
On This Page
💡 How to Use This Page
Each pattern has signal words that appear in problem descriptions, a "How to Recognize" guide, and a concrete mini-example showing the pattern in action. Practice 3-4 problems per pattern, and you'll start seeing them everywhere.
Pattern Decision Tree
Read the problem statement. Ask these questions in order. The first match is your starting point (not a guaranteed answer — you still need to think).
Is the input sorted, or would sorting help?
→ Need to find a pair/triplet with some sum?
Two Pointers
→ Need to find a target or boundary?
Binary Search
→ Need to merge/find overlaps in intervals?
Intervals (Sort by Start/End)
Does it involve a contiguous subarray or substring?
→ Fixed or variable-length window with a constraint?
Sliding Window
→ Running sum equals a target?
Prefix Sum + Hash Map
Is it a tree or graph?
→ Need an unweighted shortest path or level-by-level traversal?
BFS
→ Need shortest paths with nonnegative edge weights?
→ Can edge weights be negative?
Bellman-Ford; check reachable negative cycles
→ Need to explore all paths or check connectivity?
DFS / Backtracking
→ Need to group nodes into components?
Union-Find or BFS/DFS
→ Need dependency ordering?
Topological Sort
Does it ask for "minimum/maximum cost" or "number of ways"?
→ Can you break it into overlapping subproblems?
Dynamic Programming
→ Can you prove a greedy choice is always safe?
Greedy
Does it ask for "all combinations/permutations/subsets"?
Backtracking
Does it involve "next greater/smaller" or "largest rectangle"?
Monotonic Stack
Does it involve "top K" or streaming data?
Heap / Priority Queue
Does it involve string prefixes or dictionary matching?
Trie
None of the above? Need O(1) lookups?
Hash Map
The 20 Patterns
Pattern 1
Two Pointers
Use when you have a sorted array/list and need to find pairs, triplets, or subarrays satisfying some condition.
Signals: "sorted array", "find pair with sum", "remove duplicates", "container with most water"
🔍 How to Recognize: The input is sorted (or sorting it first is acceptable), and you need to find elements that satisfy a relationship. If brute force would be O(n²) with nested loops, two pointers often gives you O(n).
Mini-Example: Find pair summing to target in sorted array
Python
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target: return [left, right]
elif s < target: left += 1 # need bigger sum
else: right -= 1 # need smaller sum
return []
# [1, 3, 5, 7, 11], target=10 → left=1(3), right=3(7) → [1,3]Pattern 2
Sliding Window
Use when you need to find a contiguous subarray/substring that satisfies some constraint (length, sum, unique characters).
Signals: "subarray", "substring", "window of size k", "contiguous", "maximum/minimum sum of subarray"
🔍 How to Recognize: The problem says "contiguous" and asks for a max/min/count. You're maintaining a window that expands and shrinks. Fixed window = easy. Variable window = track when to shrink.
Mini-Example: Longest substring with at most k distinct characters
Python
def longest_k_distinct(s, k):
counts = {}
left = best = 0
for right in range(len(s)):
counts[s[right]] = counts.get(s[right], 0) + 1
while len(counts) > k: # too many distinct chars
counts[s[left]] -= 1
if counts[s[left]] == 0: del counts[s[left]]
left += 1 # shrink window
best = max(best, right - left + 1)
return best
# "araaci", k=2 → "araa" → 4Pattern 3
Fast & Slow Pointers (Floyd's)
Use for cycle detection in linked lists or arrays, or finding the middle element in one pass.
Signals: "cycle", "circular", "find middle", "palindrome linked list", "happy number"
🔍 How to Recognize: Something circular or cyclic. You need to detect a loop, find where it starts, or find the midpoint of a sequence without knowing the length. Two pointers at different speeds — if they meet, there's a cycle.
Mini-Example: Detect cycle in linked list
Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow == fast: # they met → cycle!
return True
return False # fast hit end → no cyclePattern 4
Binary Search
Use when the search space is sorted or monotonic and you can eliminate half of it with each step.
Signals: "sorted", "find minimum/maximum that satisfies", "search in rotated", "O(log n) required"
🔍 How to Recognize: Two flavors: (1) Search in a sorted array — straightforward. (2) "Binary search on the answer" — the answer itself is monotonic. If answer=5 works, does answer=6 also work? If yes, binary search the answer space. This is the more interesting pattern.
Mini-Example: Binary search on answer — Koko eating bananas
Python
def min_eating_speed(piles, h):
# Can Koko eat all bananas at speed `k` within `h` hours?
def can_finish(k):
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if can_finish(mid): hi = mid # try slower
else: lo = mid + 1 # need faster
return lo
# piles=[3,6,7,11], h=8 → speed=4Pattern 5
BFS / Level-Order
Use for shortest path in unweighted graphs, level-order tree traversal, or anything where you need to explore all nodes at distance k before k+1.
Signals: "shortest path", "level by level", "minimum steps", "nearest", "layer by layer"
🔍 How to Recognize: "Minimum number of steps/moves" in an unweighted graph. Matrix problems where you move in 4 directions. Tree problems asking for level-order output. Anything where "closest" matters.
Mini-Example: Minimum steps in a grid
Python
from collections import deque
def shortest_path(grid):
rows, cols = len(grid), len(grid[0])
q = deque([(0, 0, 0)]) # row, col, distance
seen = {(0, 0)}
while q:
r, c, dist = q.popleft()
if r == rows-1 and c == cols-1: return dist
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0<=nr
Practice:
Number of Islands
Rotting Oranges
Pattern 6
DFS / Backtracking
Use when you need to explore all possible paths/combinations/permutations, or when the problem has a recursive structure.
Signals: "all combinations", "all permutations", "all subsets", "generate all", "maze solving", "word search"
🔍 How to Recognize: The problem says "generate all" or "find all." You're building a solution choice by choice, and some choices lead to dead ends you need to undo. The output is typically a list of lists. If n ≤ 20, backtracking is almost certainly intended.
Mini-Example: Generate all subsets
Python
def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:]) # snapshot
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1, current) # explore
current.pop() # un-choose
backtrack(0, [])
return result
# [1,2,3] → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Pattern 7
Dynamic Programming
Use when the problem has overlapping subproblems and optimal substructure — meaning the answer builds on answers to smaller versions of the same problem.
Signals: "minimum/maximum cost", "number of ways", "can you reach", "longest/shortest subsequence", "partition"
🔍 How to Recognize: Three giveaways: (1) The problem asks for an optimum (min/max/count). (2) You make a sequence of decisions. (3) A greedy approach doesn't work because early decisions affect later options. If you can write a recursive solution that recomputes the same subproblems, it's DP.
Mini-Example: Coin Change — minimum coins to make amount
Python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base: 0 coins to make $0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# coins=[1,3,4], amount=6 → dp[6]=2 (3+3)Pattern 8
Greedy
Use when making the locally optimal choice at each step leads to the globally optimal solution. Often involves sorting first.
Signals: "schedule", "interval", "minimum number of", "maximum number of", "earliest deadline"
🔍 How to Recognize: Can you prove that the locally best choice never hurts you later? Common proof: exchange argument ("if we didn't pick the greedy option, we can swap it in without making things worse"). When in doubt, try greedy first — if you find a counterexample, switch to DP.
Mini-Example: Maximum meetings in one room
Python
def max_meetings(intervals):
intervals.sort(key=lambda x: x[1]) # sort by END time
count = 0
last_end = -1
for start, end in intervals:
if start >= last_end: # no overlap
count += 1
last_end = end # greedily pick earliest-ending
return count
# [(0,3),(1,2),(3,5),(4,6)] → sorted by end: [(1,2),(0,3),(3,5),(4,6)] → pick 3
Practice:
Jump Game
Remove Overlapping Reservations
Pattern 9
Hash Map / Counting
Use when you need O(1) lookups, frequency counting, or finding complements/pairs.
Signals: "find if exists", "count frequency", "group by", "anagram", "two sum in O(n)"
🔍 How to Recognize: You're looking for a complement ("have I seen target - current before?"), counting occurrences, or grouping things. If you find yourself writing a nested loop to check "is X in the array," a hash set makes it O(1). This is the most versatile pattern — it shows up inside almost every other pattern.
Mini-Example: Two Sum — find indices of pair summing to target
Python
def two_sum(nums, target):
seen = {} # value → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
# [2,7,11,15], target=9 → seen={2:0}, then 9-7=2 found → [0,1]Pattern 10
Monotonic Stack
Use when you need to find the next/previous greater/smaller element for each position, or anything involving "looking back" at a decreasing/increasing sequence.
Signals: "next greater", "previous smaller", "largest rectangle", "stock span", "temperatures"
🔍 How to Recognize: For each element, you need to look left or right for the first element that's bigger/smaller. Brute force would be O(n²). A stack that maintains monotonic order lets each element get pushed and popped at most once → O(n) total.
Mini-Example: Next warmer day for each day
Python
def daily_temperatures(temps):
result = [0] * len(temps)
stack = [] # indices of days waiting for warmer
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
prev = stack.pop()
result[prev] = i - prev # days until warmer
stack.append(i)
return result
# [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]Pattern 11
Top-K / Heap
Use when you need the k largest/smallest/most frequent elements, or when you need to maintain a running median or sorted order in a stream.
Signals: "top k", "kth largest", "k closest", "median from stream", "merge k sorted"
🔍 How to Recognize: The problem has "k" in it and asks for extreme values. For "kth largest," use a min-heap of size k — the top is your answer. For "kth smallest," use a max-heap of size k. For "median," use two heaps (max-heap for lower half, min-heap for upper half).
Mini-Example: Kth largest element
Python
import heapq
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap) # min-heap of size k
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num) # push+pop
return heap[0] # smallest of the k largest
# [3,2,1,5,6,4], k=2 → heap maintains [5,6] → return 5Pattern 12
Union-Find
Use when you need to group/merge elements and quickly check if two elements are in the same group. Think connected components.
Signals: "connected components", "redundant connection", "accounts merge", "similar groups"
🔍 How to Recognize: You're processing edges or relationships one at a time, and need to answer "are A and B connected?" efficiently. BFS/DFS works too, but Union-Find is better when edges arrive incrementally (online) rather than all at once.
Mini-Example: Find redundant edge in a graph
Python
def find_redundant(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv: return [u, v] # already connected → redundant!
parent[pu] = pv # unionPattern 13
Trie (Prefix Tree)
Use when dealing with string prefixes, autocomplete, or when you need efficient prefix matching across many strings.
Signals: "prefix", "autocomplete", "word search in grid with dictionary", "longest common prefix"
🔍 How to Recognize: Multiple strings share prefixes, and you're querying by prefix. Or: you're searching a grid for words from a dictionary — a trie lets you prune entire branches when no word starts with the current path. If you're calling
startswith() in a loop, you probably want a trie.
Mini-Example: Implement prefix search
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True # all prefix chars foundPattern 14
Intervals
Use when the input is a list of intervals/ranges and you need to merge, insert, or find overlaps.
Signals: "intervals", "merge", "overlapping", "meeting rooms", "insert interval"
🔍 How to Recognize: Each item has a [start, end]. Sort by start time. Walk through them. If current.start ≤ prev.end, they overlap — merge or count. If they ask "how many rooms needed?" that's maximum concurrent overlaps — use a min-heap or sweep line.
Mini-Example: Merge overlapping intervals
Python
def merge_intervals(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]Pattern 15
Topological Sort
Use when you have dependencies between tasks and need to find a valid ordering, or detect if ordering is impossible (cycle).
Signals: "course schedule", "prerequisites", "build order", "dependency", "DAG"
🔍 How to Recognize: "Task B requires task A to be done first." You're building a directed graph of dependencies and need a valid execution order. If no valid order exists, there's a cycle. Use Kahn's algorithm (BFS with in-degree tracking) — it's more intuitive than the DFS approach.
Mini-Example: Course schedule — can you finish all courses?
Python
from collections import deque, defaultdict
def can_finish(num_courses, prereqs):
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, pre in prereqs:
graph[pre].append(course)
in_degree[course] += 1
q = deque(i for i in range(num_courses) if in_degree[i] == 0)
taken = 0
while q:
node = q.popleft()
taken += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return taken == num_courses # took all courses?Pattern 16
Prefix Sum
Use when you need to compute range sums quickly or find subarrays with a specific sum.
Signals: "subarray sum equals k", "range sum query", "cumulative", "contiguous sum"
🔍 How to Recognize: You need sum(arr[i:j]) repeatedly. Computing it each time is O(n). With a prefix sum array where prefix[i] = sum of first i elements, any range sum is prefix[j] - prefix[i] in O(1). Combine with a hash map for "subarray sum equals K" → store prefix sums seen so far.
Mini-Example: Count subarrays summing to k
Python
def subarray_sum(nums, k):
prefix_counts = {0: 1} # empty prefix has sum 0
running_sum = count = 0
for num in nums:
running_sum += num
# If (running_sum - k) was a previous prefix sum,
# the subarray between them sums to k
count += prefix_counts.get(running_sum - k, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
return count
# [1,1,1], k=2 → subarrays [1,1] at index 0-1 and 1-2 → 2
Practice:
Subarray Sum Equals K
Product Puzzle
Pattern 17
Bit Manipulation
Use when you need to work with binary representations, find unique elements, or when O(1) space is required for set-like operations.
Signals: "single number", "power of two", "number of 1 bits", "XOR", "without extra space"
🔍 How to Recognize: XOR is the star here.
a ^ a = 0 and a ^ 0 = a. If every element appears twice except one, XOR them all — the duplicates cancel out. Also: n & (n-1) removes the lowest set bit (useful for counting bits, power-of-two checks).
Mini-Example: Find the single number (all others appear twice)
Python
def single_number(nums):
result = 0
for num in nums:
result ^= num # duplicates cancel: a ^ a = 0
return result
# [4, 1, 2, 1, 2] → 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4Pattern 18
Monotonic Queue / Deque
Use when you need to find the maximum or minimum in a sliding window efficiently.
Signals: "maximum in sliding window", "minimum in subarray of size k", "deque"
🔍 How to Recognize: You're sliding a window across an array and need the max/min within the window at each position. A naive approach checks all k elements each time → O(nk). A monotonic deque keeps candidates in order → O(n) total. The front is always the answer; elements that can never be the answer get popped from the back.
Mini-Example: Max in each sliding window of size k
Python
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices, front = max
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop() # remove smaller — they'll never be max
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # remove if outside window
if i >= k - 1:
result.append(nums[dq[0]]) # front = window max
return result
# [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]
Practice:
Sliding Window Maximum
Pattern 19
Graph Coloring / Bipartite Check
Use when you need to partition nodes into two groups where no two adjacent nodes share a group, or detect if such partitioning is possible.
Signals: "bipartite", "two-colorable", "odd cycle", "possible bipartition", "divide into two groups"
🔍 How to Recognize: Can you split nodes into two sets with no edges within a set? BFS and alternate colors. If you find a neighbor with the same color, it's not bipartite. Comes up in interview problems about grouping people, scheduling on two machines, or checking graph structure.
Mini-Example: Is graph bipartite?
Python
from collections import deque
def is_bipartite(graph):
color = {}
for start in range(len(graph)):
if start in color: continue
q = deque([start])
color[start] = 0
while q:
node = q.popleft()
for neighbor in graph[node]:
if neighbor not in color:
color[neighbor] = 1 - color[node] # opposite color
q.append(neighbor)
elif color[neighbor] == color[node]:
return False # same color = not bipartite
return TruePattern 20
Matrix Traversal
Use when the input is a 2D grid and you need to explore regions, find paths, or count connected areas.
Signals: "grid", "matrix", "island", "flood fill", "surrounded regions", "pacific atlantic"
🔍 How to Recognize: You have an m×n grid. You move up/down/left/right. You need to explore or count regions. This is just BFS/DFS on a graph where each cell has up to 4 neighbors. The key pattern: iterate all cells, when you find an unvisited target cell, BFS/DFS from it to explore the entire region.
Mini-Example: Count islands in a grid
Python
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols: return
if grid[r][c] != '1': return
grid[r][c] = '0' # mark visited
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c) # sink the island
return countPattern Recognition Cheat Sheet
⚠️ Don't Memorize — Understand
These mappings are starting points, not rules. Many problems can be solved with multiple patterns. The goal is to quickly generate 2-3 possible approaches, then pick the best one.
| When You See... | Think... | Complexity |
|---|---|---|
| "Sorted array" + "find pair" | Two Pointers | O(n) |
| "Contiguous subarray" + monotone window constraint | Sliding Window | O(n) when each pointer moves forward |
| "Linked list" + "cycle" or "middle" | Fast & Slow Pointers | O(n) |
| "Sorted" + "search" + "O(log n)" | Binary Search | O(log n) |
| "Shortest path" (unweighted) | BFS | O(V+E) |
| "All combinations/permutations" | DFS / Backtracking | O(2ⁿ or n!) |
| "Minimum cost" + "number of ways" | Dynamic Programming | varies |
| "Schedule" + "intervals" | Greedy (sort by end time) | O(n log n) |
| "Frequency" + "O(1) lookup" | Hash Map | O(n) |
| "Next greater element" | Monotonic Stack | O(n) |
| "K largest" + "stream" | Heap | O(n log k) |
| "Connected components" | Union-Find or BFS/DFS | O(V+E) |
| "Prefix matching" + "dictionary" | Trie | O(word len) |
| "Merge overlapping" | Intervals (sort by start) | O(n log n) |
| "Order dependencies" | Topological Sort | O(V+E) |
| "Subarray sum equals K" | Prefix Sum + Hash Map | O(n) |
| "Single number" + "XOR" | Bit Manipulation | O(n) |
| "Max in sliding window" | Monotonic Deque | O(n) |
| "Two groups" + "no adjacent conflict" | Bipartite / Graph Coloring | O(V+E) |
| "Grid/matrix" + "explore regions" | Matrix BFS/DFS | O(m·n) |
🎯 The Meta-Strategy
After solving a problem, identify the pattern, explain why its assumptions hold, and try a variant where they do not. Use those comparisons to learn when an approach applies.
Practice a pattern
Choose a related problem in CodeArena, implement it, and test its edge cases. The library currently has 211 questions across algorithms and system design.