TL;DR: Ten templates cover most questions asked in coding interviews. This page is all ten, with the words in a question that point to each one, the code, the complexity, and the single bug that breaks it most often. It is a reference card, not a lesson. Keep it open while you practice, and follow the deep-dive link when a template stops making sense.
Every other page on this site explains a pattern. This one does not explain anything. It is the page to keep open in a second tab while you solve problems, so you can check a template in ten seconds instead of rereading an article.
The code is Python because it is the shortest to read. The structure is the same in any language, and there is a Java version of every template if you interview in Java.
Which template does this question need?
Find the phrase closest to the question you are looking at.
| The question says | Use |
|---|---|
| sorted array, pair, triplet, sum to a target | Two Pointers |
| longest or shortest substring, contiguous, window | Sliding Window |
| linked list, cycle, middle node, no extra memory | Fast and Slow Pointers |
| sorted, or "smallest value that works" | Binary Search |
| shortest path, level by level, nearest | BFS |
| all combinations, all permutations, every valid board | Backtracking |
| top K, K largest, K most frequent, median so far | Heap |
| intervals, meetings, overlap, merge | Merge Intervals |
| next greater, next smaller, largest rectangle | Monotonic Stack |
| count the ways, minimum cost, maximum value | Dynamic Programming |
If nothing matches, read the last section of this page before guessing.
1. Two Pointers
Use it when: the array is sorted and you are looking for a pair, a triplet, or a sum that hits a target.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need more, move the small end up
else:
right -= 1 # need less, move the big end down
return []
Complexity: O(n) time, O(1) extra space.
The one bug: using left <= right instead of left < right, which lets one element pair with itself.
2. Sliding Window
Use it when: the question asks for the longest or shortest run of adjacent elements that satisfies a rule.
def longest_valid_window(s):
counts = {}
left = 0
best = 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
while not is_valid(counts): # shrink until valid again
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1) # record only while valid
return best
Complexity: O(n) time, because each index enters and leaves the window once.
The one bug: recording the answer before the shrink loop runs. Measure the window only after it is valid again.
If the window has a fixed size, drop the while loop and remove s[right - k] on every step instead.
3. Fast and Slow Pointers
Use it when: the input is a linked list or a sequence that repeats, and you may not use extra memory.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow stops at the middle
Complexity: O(n) time, O(1) space.
The one bug: checking fast.next without checking fast first, which raises an error on a list of even length.
4. Binary Search
Use it when: the data is sorted, or the answer is a number and you can test whether a given value works.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids overflow in fixed-width languages
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def smallest_valid(low, high, works): # binary search on the answer
while low < high:
mid = low + (high - low) // 2
if works(mid):
high = mid # mid might be the answer, keep it
else:
low = mid + 1
return low
Complexity: O(log n), or O(log range × cost of works) for the second form.
The one bug: mixing the two forms. The first uses lo <= hi and moves both ends past mid. The second uses low < high and keeps mid on the valid side. Pick one and do not blend them.
5. Breadth-First Search
Use it when: you need the shortest path in an unweighted graph, or you must process a tree level by level.
from collections import deque
def bfs_levels(root):
if not root:
return []
queue = deque([root])
levels = []
while queue:
size = len(queue) # freeze the level before adding to it
level = []
for _ in range(size):
node = queue.popleft()
level.append(node.val)
for child in (node.left, node.right):
if child:
queue.append(child)
levels.append(level)
return levels
Complexity: O(n) time, O(width) space.
The one bug: reading len(queue) inside the inner loop instead of before it, which merges every level into one.
On a graph, add a visited set and mark a node when you add it to the queue, not when you remove it.
6. Depth-First Search and Backtracking
Use it when: the question asks for all of something. All subsets, all permutations, every valid arrangement.
def backtrack(state, choices, results):
if is_complete(state):
results.append(list(state)) # copy, the original keeps changing
return
for choice in choices:
if not is_valid(state, choice):
continue
state.append(choice) # choose
backtrack(state, choices, results)
state.pop() # undo
Complexity: O(number of valid states × cost to build one). Exponential by nature, which is expected here.
The one bug: appending state instead of list(state). Every stored answer then points at the same list, and all of them end up empty.
7. Top K with a Heap
Use it when: the question wants the K largest, K smallest, K most frequent, or a running median.
import heapq
def top_k_largest(nums, k):
heap = [] # a MIN heap, holding the k largest
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest of the k+1
return heap
Complexity: O(n log k) time, O(k) space. Better than sorting when k is much smaller than n.
The one bug: using a max heap for the K largest. It is inverted on purpose: a min heap of size k keeps the smallest of your winners at the top, which is exactly the one to remove next.
Python's heapq is a min heap only. For a max heap, push -value.
8. Merge Intervals
Use it when: the input is a list of ranges and the question mentions overlap, merging, or meeting rooms.
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start, always
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps the last one
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
Complexity: O(n log n), which is the sort. The pass itself is O(n).
The one bug: writing merged[-1][1] = end instead of taking the max. One interval fully inside another then shortens the result.
9. Monotonic Stack
Use it when: the question asks for the next greater element, the previous smaller element, or the largest rectangle.
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # holds indexes, values decreasing
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num # num is the answer for that index
stack.append(i)
return result
Complexity: O(n) time, because each index is pushed once and popped once.
The one bug: storing values instead of indexes. You then cannot write the answer back to the right position.
10. Dynamic Programming, top down
Use it when: the question asks to count the ways, or for a minimum cost or maximum value, and the same subproblem appears more than once.
from functools import cache
def solve(nums):
@cache
def best(i, remaining):
if i == len(nums) or remaining == 0:
return 0 # base case first
skip = best(i + 1, remaining)
take = 0
if nums[i] <= remaining:
take = nums[i] + best(i + 1, remaining - nums[i])
return max(skip, take)
return best(0, target)
Complexity: O(number of distinct states × work per state).
The one bug: putting a list or a dict in the arguments of a cached function. The cache needs values it can hash, so pass an index or a tuple instead.
Write this form in the interview first. Convert to a table only if you are asked to cut memory.
Want these taught in order, with problems attached? Grokking the Coding Interview builds all 42 patterns from the recognition signal through the template to 300 or so sequenced problems, in six languages.
When none of the ten fit
This happens, and guessing is the wrong response. Three checks, in order.
Is the question two patterns stacked? Many hard questions are one template feeding another. Sort the intervals, then run a heap. Build a graph, then run a topological sort. Say which two you see.
Is the input hinting at a structure you have not built yet? Prefix sums, a trie, and union-find are not templates so much as structures you set up first. If the question asks for many range sums, or many prefix lookups, or many "are these two connected" checks, build the structure and the rest becomes simple.
Can you state the brute force? Say it out loud with its complexity, then ask which part is repeated work. Nearly every optimization on this page is the answer to that one question.
The takeaway
Ten templates, roughly forty lines of code each, cover most of what coding interviews ask. The work is not memorizing them. It is reading a question and knowing within thirty seconds which one applies, which is why every block above starts with the words that point to it rather than with the code.
Use this page while you practice. When a template stops making sense, follow its deep-dive link, then come back. The complete map of all 42 patterns shows where these ten sit among the rest, and how many problems you actually need explains why ten templates beat five hundred solved problems.
Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common and 10 advanced) for a one-time $79 with lifetime access. Short on time? Grokking 75 covers the essential problems in a six-week plan.
Frequently asked questions
Is memorizing templates enough to pass a coding interview? No, and it is not what templates are for. A template removes the mechanical part so your time goes to recognizing the pattern and handling edge cases. An interviewer will change one condition, and only understanding why the template works lets you adjust it.
How many templates do I actually need? These ten cover most questions asked at the medium level, which is where most interviews sit. There are 42 patterns in total, but the remainder are either variations on these ten or advanced patterns that appear rarely.
Should I write the template from memory or derive it each time? Derive it during practice and write it from memory during the interview. If you can only reproduce it and cannot explain why each line is there, you will not be able to adjust it when one condition changes.
What is the fastest way to learn which template a question needs? Practice recognition separately from solving. Read twenty question statements and name the pattern for each without writing any code. That takes fifteen minutes and trains the exact skill the first two minutes of an interview needs.
Do these templates work in Java and C++? Yes. The structure does not change, only the syntax and the library names. The Java version of every template and the Python version with language traps cover the differences that cost people points.