15 Coding Interview Patterns That Solve Most Problems

15 Coding Interview Patterns That Solve Most Problems

Most coding interview problems are not new problems. They are one of roughly fifteen patterns wearing different wording.

Learning patterns is what makes preparation scale. Grinding three hundred individual problems teaches you three hundred solutions; learning fifteen patterns teaches you how to attack the three hundred and first.

This sheet gives each pattern the recognition signal, a minimal skeleton, and the problem types it solves.

Updated for 2026. Skeletons in Python for brevity; the logic is language-agnostic.

How to Recognise the Pattern in 2 Minutes

Read the problem for structure, not topic. The wording usually leaks the template it was written from.

1. Two Pointers

What it is: two indices scanning a sorted array from opposite ends, moving inward based on a comparison.

The signal: the input is sorted (or you can sort it) and you need a pair, triplet, or comparison between two elements.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target: return [left, right]
        if total < target: left += 1     # need bigger
        else: right -= 1                 # need smaller
    return []

Because the array is sorted, a sum that is too small can only be fixed by moving the left pointer right. That single fact eliminates the inner loop and turns O(n²) into O(n).

Solves: pair with target sum, three-sum, remove duplicates in place, valid palindrome, container with most water.

2. Sliding Window

What it is: a contiguous range defined by two indices, expanded on the right and shrunk on the left to maintain a constraint.

The signal: the words "contiguous", "subarray", or "substring", plus "longest", "shortest", or "maximum".

def longest_unique(s):
    seen, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1          # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Each character enters the window once and leaves once, so despite the nested feel this is O(n). The window never moves backwards — that is the invariant that makes the pattern work.

Solves: longest substring without repeating characters, minimum window substring, maximum sum subarray of size K, longest substring with K distinct characters.

What people get wrong: using a window on a problem where the answer need not be contiguous. If elements can be skipped, this is not a window problem.

3. Fast & Slow Pointers

What it is: two pointers moving at different speeds through a sequence, usually one step versus two.

The signal: a linked list plus the words "cycle", "middle", "nth from end", or a constant-space requirement.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False

If a cycle exists, the fast pointer eventually laps the slow one and they meet. If not, the fast pointer reaches the end. No extra memory, no hash set.

Solves: linked list cycle detection, find cycle start, middle of a linked list, happy number, palindromic linked list.

4. Merge Intervals

What it is: sort intervals by start, then walk through merging any that overlap the current one.

The signal: ranges, bookings, meetings, schedules, or explicitly "overlapping intervals".

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:                 # overlaps
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

Sorting by start time is what makes a single pass sufficient: once sorted, any interval that overlaps the current one must overlap its end.

Solves: merge intervals, insert interval, meeting rooms, minimum meeting rooms required, employee free time.

5. Cyclic Sort

What it is: placing each number at the index equal to its value, in place, in one pass.

The signal: the input is stated to contain numbers in the range 1 to n, or 0 to n, and asks for a missing or duplicated value.

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        target = nums[i] - 1                    # value v belongs at index v-1
        if nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    return nums

After the pass, any index whose value is wrong points directly at the missing or duplicated number. Time is O(n) and space is O(1) — this is why the pattern exists rather than just using a hash set.

Solves: find the missing number, find all missing numbers, find the duplicate, find the corrupt pair, first missing positive.

6. In-Place Linked List Reversal

What it is: relinking next pointers as you walk, using three references.

The signal: reverse a linked list or a sublist, with O(1) extra space required.

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev      # flip
        prev, curr = curr, nxt
    return prev               # new head

Save the next node before you overwrite the pointer — that one line is the entire pattern, and forgetting it is the most common bug in the entire subject.

Solves: reverse a linked list, reverse a sublist, reverse in groups of K, rotate a list, palindrome check on a list.

7. BFS (Breadth-First Search)

What it is: a queue-driven traversal that visits nodes in order of distance from the start.

The signal: "shortest path", "minimum number of steps", "level by level", or an unweighted grid or graph.

from collections import deque

def bfs(start, neighbours):
    queue, seen, depth = deque([start]), {start}, 0
    while queue:
        for _ in range(len(queue)):        # one full level
            node = queue.popleft()
            for nxt in neighbours(node):
                if nxt not in seen:
                    seen.add(nxt); queue.append(nxt)
        depth += 1
    return depth

The inner for _ in range(len(queue)) loop is what separates levels — without it you cannot answer "how many steps". That line is the difference between a traversal and a shortest-path algorithm.

Solves: binary tree level order traversal, minimum depth, shortest path in a grid, word ladder, rotting oranges.

8. DFS (Depth-First Search)

What it is: recursion (or an explicit stack) that follows one path to its end before backtracking.

The signal: "all paths", "connected components", "islands", cycle detection, or any question about a complete route.

def dfs(node, path, results):
    if not node: return
    path.append(node.val)
    if not node.left and not node.right:
        results.append(list(path))         # copy — path is mutated
    dfs(node.left,  path, results)
    dfs(node.right, path, results)
    path.pop()                             # backtrack

The path.pop() is the backtracking step. Omitting it, or appending path instead of a copy, produces the two bugs that account for most failed DFS answers.

Solves: all root-to-leaf paths, path sum, number of islands, clone graph, cycle detection in a directed graph.

9. Two Heaps

What it is: a max-heap holding the smaller half of the data and a min-heap holding the larger half, kept balanced in size.

The signal: "median" of a stream, or any problem needing the middle of continuously arriving data.

import heapq
small, large = [], []                       # small is a max-heap (negated)

def add(num):
    heapq.heappush(small, -heapq.heappushpop(large, num))
    if len(small) > len(large):
        heapq.heappush(large, -heapq.heappop(small))

def median():
    return large[0] if len(large) > len(small) else (large[0] - small[0]) / 2

The median is always at one of the two heap tops, so retrieval is O(1) while insertion stays O(log n). Sorting after every insertion would be O(n log n) each time.

Solves: find median from a data stream, sliding window median, IPO / maximise capital, next interval.

10. Subsets and Combinations

What it is: building every combination by, at each element, choosing to include it or not.

The signal: "all subsets", "all permutations", "all combinations", "generate every".

def subsets(nums):
    out = [[]]
    for n in nums:
        out += [curr + [n] for curr in out]   # include n in every existing subset
    return out

Each new element doubles the result set, which is why the output is 2ⁿ and why these problems always have small constraints. If n is large, the intended answer is not enumeration.

Solves: all subsets, subsets with duplicates, permutations, letter combinations of a phone number, generate parentheses, N-queens.

11. Modified Binary Search

What it is: binary search where the comparison decides which half to keep, adapted to non-obvious orderings.

The signal: sorted or rotated input, "find the first/last occurrence", or a required O(log n).

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target: return mid
        if nums[lo] <= nums[mid]:                    # left half sorted
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                        # right half sorted
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

In a rotated array one half is always properly sorted. Determining which half that is, then checking whether the target lies inside it, is the whole trick.

Solves: search in rotated sorted array, find the minimum in a rotated array, first and last position of an element, search in a matrix, find peak element.

12. Top-K Elements

What it is: a heap of size exactly K, holding the best K seen so far.

The signal: "top K", "K largest", "K most frequent", "K closest".

import heapq

def top_k(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k: heapq.heappop(heap)   # drop the smallest
    return heap

Capping the heap at K is the point. Time becomes O(n log k) rather than the O(n log n) of sorting, and memory is O(k) rather than O(n) — which matters when the input is a stream you cannot hold.

Solves: K largest numbers, K closest points to the origin, top K frequent elements, K closest numbers, reorganise string.

13. K-Way Merge

What it is: a min-heap holding the current head of each of K sorted sequences.

The signal: multiple sorted lists, arrays, or streams that must be combined in order.

import heapq

def merge_k(lists):
    heap = [(l[0], i, 0) for i, l in enumerate(lists) if l]
    heapq.heapify(heap)
    out = []
    while heap:
        val, li, idx = heapq.heappop(heap)
        out.append(val)
        if idx + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][idx + 1], li, idx + 1))
    return out

The heap always holds at most K items — one candidate per list — so the smallest remaining element globally is always at the top. Total cost is O(N log k) for N elements across k lists.

Solves: merge K sorted lists, K pairs with smallest sums, smallest number range covering K lists, Kth smallest in a sorted matrix.

14. Dynamic Programming (0/1 Knapsack)

What it is: solving overlapping subproblems once and caching the result, keyed on the recursion's parameters.

The signal: "minimum", "maximum", "longest", or "number of ways", combined with choices that reuse the same subproblems.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for c in range(capacity, weights[i] - 1, -1):   # backwards = each item once
            dp[c] = max(dp[c], values[i] + dp[c - weights[i]])
    return dp[capacity]

The backwards inner loop is what makes this 0/1 knapsack rather than unbounded knapsack. Iterating forwards would let the same item be picked repeatedly.

The interview method: write the brute-force recursion first, note its parameters, then memoise on those parameters. Converting to a bottom-up table is an optimisation, not a prerequisite.

Solves: subset sum, partition equal subset sum, coin change, longest common subsequence, edit distance, house robber.

15. Topological Sort

What it is: ordering the nodes of a directed acyclic graph so every edge points forward, by repeatedly removing nodes with no remaining prerequisites.

The signal: "dependencies", "prerequisites", "build order", "course schedule", "compile order".

from collections import deque

def topo_sort(n, edges):
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for a, b in edges:                    # a must come before b
        adj[a].append(b); indeg[b] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        node = queue.popleft(); order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0: queue.append(nxt)
    return order if len(order) == n else []   # short = cycle exists

The length check at the end is free cycle detection. If fewer than n nodes came out, some group of nodes depends on each other and no valid order exists.

Solves: course schedule, alien dictionary, task scheduling with dependencies, minimum height trees, build systems.

The Five Mistakes

1. Pattern-matching on topic instead of structure. "It mentions a tree, so DFS" is guessing. "It asks for minimum steps, so BFS" is reasoning. The question being asked determines the pattern, not the data type.

2. Reaching for dynamic programming too early. Many problems that look like DP are greedy, and greedy is far shorter. Only commit to DP once you can name the overlapping subproblem.

3. Using a sliding window on non-contiguous problems. If elements may be skipped, the answer is not a window. This is the single most common misapplication of the most popular pattern.

4. Sorting when a heap of size K would do. Sorting for a top-K question is O(n log n) and O(n) memory. The heap is O(n log k) and O(k). Interviewers ask top-K specifically to see whether you notice.

5. Coding before naming the pattern out loud. Saying "this looks like a sliding window because we need a contiguous substring" costs eight seconds and lets the interviewer redirect you before you burn ten minutes. Silence is the expensive option.

Print This Section

SIGNAL → PATTERN
  sorted array, pair/triplet ....... two pointers
  contiguous subarray/substring .... sliding window
  linked list cycle / middle ....... fast & slow pointers
  overlapping ranges ............... merge intervals (sort by start)
  numbers 1..n, missing/dup ........ cyclic sort
  reverse list, O(1) space ......... in-place reversal
  shortest path / level by level ... BFS (queue)
  all paths / components / cycle ... DFS (recursion + backtrack)
  running median ................... two heaps
  all subsets / permutations ....... backtracking
  sorted or rotated, find target ... modified binary search
  top K / K most frequent .......... heap of size K
  K sorted lists ................... K-way merge (min-heap)
  min/max/count-ways + reuse ....... dynamic programming
  prerequisites / build order ...... topological sort (indegree)

TRAPS
  window only works if the answer is contiguous
  top-K → heap of size k, not a full sort
  DFS backtrack: path.pop() and copy the path
  BFS level count: for _ in range(len(queue))
  topo sort: order shorter than n means a cycle

Patterns are a compression of the problem space. Once you can name the pattern in the first two minutes, the remaining forty are about clean code and clear reasoning — which is what the interview was measuring all along.

🔗 Next in this collection: Data Structures and Big-O Cheat Sheet for Coding Interviews, or return to The Complete Developer Cheat Sheet Collection.