15 patterns to make SWE & DSA easier, with a free practice repo
When to reach for each pattern, the shape of the code, and 45 practice problems with tests and solutions.
15 patterns, and now a place to practice them
A while back I posted a list of 15 patterns that make data structures and algorithms easier. People saved it, which is nice, but saving a list is not the same as being able to use it. So this version comes with a practice repo.
Here's the idea behind the list. Memorising hundreds of problems doesn't scale. Recognising about fifteen shapes does. When I read a new problem now, the first question I ask is which pattern it is, not whether I've seen that exact one before. That's also true at work, where nobody hands you a problem with a name on it.
The practice repo: gitlab.com/j.michaelduhart/dsa-patterns. Free, MIT licensed, Python.
All 15 in 42 seconds
How the repo works
Every pattern gets its own folder with four things in it:
- a README with when to use it, the template, the complexity and a worked example
practice.py, three problems as function stubs, where the docstring is the problem- tests, which run against your practice file
solutions/, for when you're properly stuck
The problems are written for the repo. Plenty of them are classic interview questions in plain words, so what you learn carries over. Run the tests and you get a table of what you've solved.
Getting started
git clone https://gitlab.com/j.michaelduhart/dsa-patterns.git
cd dsa-patterns
python3 -m venv .venv && source .venv/bin/activate
pip install -r requirements.txt
pytest # every pattern, all failing until you solve them
pytest patterns/01-two-pointers # one pattern
DSA_IMPL=solutions pytest # the same tests against the answers1. Two Pointers
Use it when: Sorted input and you need a pair. Start at both ends and move the one that helps.
Two indexes, one at each end, walking toward each other. On sorted data every move rules out a whole set of pairs, so a nested O(n^2) loop becomes one O(n) pass. It also covers palindromes and in-place work like removing duplicates.
Cost: O(n) time, O(1) space. Practice it: patterns/01-two-pointers
Two Pointers: the shape
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target: return lo, hi
if s < target: lo += 1
else: hi -= 12. Sliding Window
Use it when: Best contiguous run. Grow the right edge, shrink the left when it breaks.
Keep a window over the array and update it as it slides instead of recomputing every subarray. Add what enters on the right, remove what leaves on the left. Each element goes in once and out once, which is why it's linear even with a loop inside a loop.
Cost: O(n) time. Practice it: patterns/02-sliding-window
Sliding Window: the shape
left = 0
for right, x in enumerate(a):
add(x)
while not valid():
remove(a[left]); left += 1
best = max(best, right - left + 1)3. Binary Search
Use it when: Sorted data, or a yes/no answer that flips once. Halve the space every step.
Everyone knows it for finding a value in a sorted list. The version that gets you hired is searching the answer space: if a speed of 10 works, 11 works too, so binary search the smallest speed that works. I write every binary search as "find the first index where the condition turns true" and most off-by-one bugs go away.
Cost: O(log n) steps. Practice it: patterns/03-binary-search
Brute force against the patterns
Binary Search: the shape
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if ok(mid): hi = mid
else: lo = mid + 1
return lo4. Frequency Counting
Use it when: Anagrams, duplicates, first unique. Count once into a map, then ask.
Count once into a dictionary, then answer from the counts. Anagrams, duplicates, the first unique character, grouping words by their letters. Write the counting loop by hand once so you see it's just a dict, then use collections.Counter forever.
Cost: O(n) time, O(k) space for k distinct items. Practice it: patterns/04-frequency-counting
Frequency Counting: the shape
counts = Counter(items)
for i, x in enumerate(items):
if counts[x] == 1:
return i
return -15. Matrix Traversal
Use it when: Grids. Name your four directions and check the bounds in one place.
Most grid bugs are boundary bugs. Put the four directions in one list and the bounds check in one place, and the rest of the code stops caring about edges. For spirals, keep four walls and pull one in after each side.
Cost: O(rows x cols). Practice it: patterns/05-matrix-traversal
Matrix Traversal: the shape
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
visit(nr, nc)6. Monotonic Stack
Use it when: Next bigger or smaller element. Every pop has just found its answer.
A stack whose values only go one direction. When a new number breaks the order, everything it pops has just found its next bigger element. It looks quadratic because of the inner while, but each index is pushed once and popped once.
Cost: O(n) time. Practice it: patterns/06-monotonic-stack
Monotonic Stack: the shape
stack = []
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
ans[stack.pop()] = x
stack.append(i)7. Prefix Sum
Use it when: Lots of range-sum questions. Build running totals once, then subtract.
Build running totals once and every range sum is one subtraction. Pair it with a hash map and you can count subarrays that add up to k, even with negative numbers, in a single pass. The leading 0 in the array is not decoration. It's what makes ranges that start at index 0 work.
Cost: O(n) build, O(1) per query. Practice it: patterns/07-prefix-sum
Prefix Sum: the shape
pre = [0]
for x in a:
pre.append(pre[-1] + x)
# sum of a[i..j] in O(1)
total = pre[j + 1] - pre[i]8. Overlapping Intervals
Use it when: Meetings, bookings, ranges. Sort by start and only neighbours can overlap.
Meetings, bookings, time windows. Sort by start and overlaps can only happen between neighbours, so one pass merges everything. Add a min-heap of end times and the same idea tells you how many rooms you need.
Cost: O(n log n) for the sort. Practice it: patterns/08-overlapping-intervals
Overlapping Intervals: the shape
out = []
for s, e in sorted(spans):
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])9. Greedy
Use it when: The best choice now never hurts later. Prove it with a swap, or use DP.
Take the best-looking choice at each step. It's the simplest code in this list and the easiest to get wrong. Before you trust a greedy answer, make the swap argument: replacing any other first choice with yours never makes things worse. If you can't, look for a counterexample.
Cost: usually O(n log n). Practice it: patterns/09-greedy
Greedy: the shape
talks.sort(key=lambda t: t[1])
free, count = float("-inf"), 0
for s, e in talks:
if s >= free:
count += 1
free = e10. Top K Elements
Use it when: The k biggest, closest or most frequent. Keep a heap of size k.
For the k biggest, closest or most frequent items, keep a heap that never grows past k. It feels backwards: to keep the largest k you use a min-heap, because the item you want to throw out is the smallest of them.
Cost: O(n log k) time, O(k) space. Practice it: patterns/10-top-k-elements
Top K Elements: the shape
heap = []
for x in a:
heappush(heap, x)
if len(heap) > k:
heappop(heap)
return sorted(heap, reverse=True)11. Backtracking
Use it when: Every subset, order or combination. Choose, explore, un-choose.
When the question says all, every or generate, build a candidate one choice at a time and undo the last choice on the way back up. Choose, explore, un-choose. The bug almost everyone writes once is appending path instead of a copy of it.
Cost: exponential, because the output is. Practice it: patterns/11-backtracking
Backtracking: the shape
def go(path, start):
out.append(path[:])
for i in range(start, len(a)):
path.append(a[i])
go(path, i + 1)
path.pop()12. Binary Tree Traversal
Use it when: Any tree question. Pick the order first: pre, in, post or level.
Every tree question starts with choosing the order you visit nodes. Pre-order copies a tree, in-order reads a search tree in sorted order, post-order is for anything that needs the children's answers first, like height. Validating a search tree is the classic trap: checking only a node's direct children is not enough.
Cost: O(n) time, O(h) stack. Practice it: patterns/12-binary-tree-traversal
Binary Tree Traversal: the shape
def walk(node):
if node is None:
return 0
left = walk(node.left)
right = walk(node.right)
return 1 + max(left, right)13. Depth-First Search
Use it when: Reachable, connected, islands, cycles. Go deep with a stack.
Go as deep as you can, then back up. Use it for reachability, counting islands and finding cycles in dependencies. Python stops at about 1,000 nested calls, so on a big grid I use an explicit stack instead of recursion.
Cost: O(V + E). Practice it: patterns/13-depth-first-search
Depth-First Search: the shape
stack, seen = [start], set()
while stack:
v = stack.pop()
if v in seen: continue
seen.add(v)
stack.extend(graph[v])14. Breadth-First Search
Use it when: Shortest path when every step costs the same. Explore in rings.
Explore in rings: everything one step away, then everything two steps away. The first time you reach the goal is the shortest route, as long as every step costs the same. Use collections.deque. list.pop(0) quietly turns BFS quadratic.
Cost: O(V + E). Practice it: patterns/14-breadth-first-search
Breadth-First Search: the shape
q, seen = deque([(start, 0)]), {start}
while q:
v, d = q.popleft()
if v == goal: return d
for w in graph[v]:
if w not in seen:
seen.add(w); q.append((w, d + 1))15. Dynamic Programming
Use it when: Count the ways or find the best, and subproblems repeat. Store each answer once.
The subproblems repeat, so solve each once and store it. I answer four questions before writing a loop: what does dp[i] mean, how is it built from smaller states, what are the base cases, and in what order do I fill it. Coin change is the classic proof that greedy can fail: with coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1, DP finds 3 + 3.
Cost: states x work per state. Practice it: patterns/15-dynamic-programming
Dynamic Programming: the shape
best = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
best[x] = min(best[x], best[x - c] + 1)The pairs worth studying together
Two pairs trip people up more than any single pattern.
Greedy and dynamic programming. Both answer "what's the best I can do?". Greedy is faster and shorter, and it's only right when you can argue that the local choice never hurts. The moment you find a counterexample, switch to DP. Doing patterns 9 and 15 back to back makes that click.
DFS and BFS. Both visit everything reachable. If the question says shortest and every step costs the same, it's BFS. If you need to go all the way down a path, detect a cycle or just mark what's connected, DFS is simpler.
Knowing when a pattern does NOT fit is most of the skill.
How I'd use this
Read a pattern's README and type the template out by hand once. Don't paste it. Solve the first problem and run its tests. Before the second and third, say out loud what told you this pattern fits. A week later, pick a random problem and write the pattern name before you write any code.
If something in the repo is wrong or unclear, open an issue on GitLab. I'd rather fix it than have someone learn it wrong.
Which of the 15 gives you the most trouble?
More: LinkedIn · Instagram. Portfolio and case studies: designsbyduhart.org.
If any of this saved you an afternoon, Buy me a coffee.