The 15 patterns that cover most interviews

Most coding-interview problems are one of about fifteen shapes wearing a costume. Learn to recognise the shape and you convert a memory problem into a pattern-matching problem.

1. Two pointers

Signal: a sorted array, a pair/triplet with a target, in-place partitioning, palindromes.

python

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target: return [lo, hi]
        if s < target:  lo += 1        # need bigger -> only lo can help
        else:           hi -= 1
    return []

O(n) time, O(1) space, versus O(n log n) for sorting-based approaches or O(n) space for a hash map. Extends to 3Sum (fix one, two-point the rest → O(n²)) and container-with-most-water.

2. Sliding window

Signal: "longest/shortest/max sum contiguous subarray or substring satisfying X".

python

def longest_unique(s: str) -> int:
    last, best, start = {}, 0, 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1          # shrink past the previous occurrence
        last[ch] = i
        best = max(best, i - start + 1)
    return best

function minSubArrayLen(target, nums) {      // shortest window with sum >= target
  let lo = 0, sum = 0, best = Infinity;
  for (let hi = 0; hi < nums.length; hi++) {
    sum += nums[hi];
    while (sum >= target) { best = Math.min(best, hi - lo + 1); sum -= nums[lo++]; }
  }
  return best === Infinity ? 0 : best;
}

Every element enters and leaves the window once → O(n). Note the shrink condition is where the variants differ: fixed size, at-most-K distinct, exactly-K (= atMost(K) − atMost(K−1)).

3. Fast & slow pointers (Floyd)

Signal: linked-list cycles, finding the middle, cycle start, happy numbers.

python

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                       # meeting point inside the cycle
            slow = head
            while slow is not fast:            # both move 1 step -> meet at the entry
                slow, fast = slow.next, fast.next
            return slow
    return None

Be ready to explain why the second phase works: if the tail before the cycle is length a and the meeting point is b into a cycle of length c, then a ≡ (c − b) mod c.

4. Merge intervals

Signal: overlapping ranges, meeting rooms, calendars, "insert an interval".

python

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

O(n log n), dominated by the sort. The related "minimum meeting rooms" is a heap of end times, or a sweep line of +1/−1 events — both worth knowing.

5. Cyclic sort / index-as-hash

Signal: an array containing numbers in the range 1..n; find the missing/duplicate in O(1) space.

python

def find_duplicate(nums):        # values 1..n, one duplicate, do not modify input
    slow = fast = nums[0]        # treat the array as a linked list: i -> nums[i]
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast: slow, fast = nums[slow], nums[fast]
    return slow

That is Floyd's algorithm reused — a nice thing to point out, because it shows you see the structure rather than a memorised trick.

6. Binary search (and binary search on the answer)

Signal: sorted input, or a monotonic predicate — "the smallest capacity such that we finish in D days".

python

def lower_bound(arr, target):            # first index with arr[i] >= target
    lo, hi = 0, len(arr)                 # half-open [lo, hi) avoids most off-by-ones
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target: lo = mid + 1
        else:                 hi = mid
    return lo

def min_capacity(weights, days):         # binary search on the ANSWER
    def feasible(cap):
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap: d, cur = d + 1, 0
            cur += w
        return d <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else:             lo = mid + 1
    return lo

"Binary search on the answer" is the single highest-leverage pattern for medium/hard problems: whenever the answer is a number and feasibility is monotonic, you get O(n log range).

7. Top-K with a heap

Signal: "k largest/smallest/most frequent", streaming data, median maintenance.

python

import heapq
def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts, key=counts.get)        # O(n log k)

class MedianFinder:                 # two heaps: max-heap of the low half, min-heap of the high
    def __init__(self): self.lo, self.hi = [], []           # lo is negated for max-heap
    def add(self, x):
        heapq.heappush(self.lo, -heapq.heappushpop(self.hi, x))
        if len(self.lo) > len(self.hi):
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
    def median(self):
        return self.hi[0] if len(self.hi) > len(self.lo) else (self.hi[0] - self.lo[0]) / 2

Key insight to say out loud: for "k largest" use a min-heap of size k (not a max-heap of everything) — O(n log k) time and O(k) space, which matters for streams.

8. BFS and DFS on graphs and grids

python

from collections import deque
def bfs_grid(grid, start):                       # shortest path in an unweighted grid
    R, C = len(grid), len(grid[0])
    q, seen = deque([(start, 0)]), {start}
    while q:
        (r, c), d = q.popleft()
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#" and (nr,nc) not in seen:
                seen.add((nr, nc))               # mark on ENQUEUE, not on dequeue
                q.append(((nr, nc), d + 1))
    return -1

BFS gives shortest paths in unweighted graphs; DFS suits connectivity, cycle detection and topological order. Marking visited at enqueue time is the classic bug fix — marking at dequeue lets the same node enter the queue many times.

9. Topological sort

Signal: dependencies, course schedules, build order, "is there a cycle in a DAG".

python

def topo(n, edges):
    adj, indeg = defaultdict(list), [0] * n
    for a, b in edges: adj[a].append(b); indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []       # short order -> a cycle exists

10. Union-Find (disjoint set)

Signal: connected components, "are these two in the same group", Kruskal's MST, redundant connections.

python

class DSU:
    def __init__(self, n): self.p, self.r = list(range(n)), [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]        # path compression (halving)
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        self.r[ra] += self.r[ra] == self.r[rb]
        return True

With both optimisations, operations are effectively O(α(n)) — constant for any real n.

11. Backtracking

Signal: permutations, combinations, subsets, N-Queens, sudoku, word search.

python

def subsets(nums):
    out, path = [], []
    def dfs(i):
        if i == len(nums): out.append(path[:]); return   # copy! path is mutated
        dfs(i + 1)                                        # exclude
        path.append(nums[i]); dfs(i + 1); path.pop()      # include, then undo
    dfs(0)
    return out

The template is choose → explore → un-choose. For duplicates, sort first and skip nums[i] == nums[i-1] at the same depth. Complexity is the size of the search tree — O(2^n) for subsets, O(n!) for permutations — and pruning is what makes hard versions tractable.

12. Dynamic programming

Recognise it by overlapping subproblems plus optimal substructure. Method: define the state, write the recurrence, decide the order, then optimise the space.

python

def coin_change(coins, amount):          # unbounded knapsack, min coins
    INF = float("inf")
    dp = [0] + [INF] * amount            # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

def lis(nums):                           # longest increasing subsequence in O(n log n)
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else:               tails[i] = x
    return len(tails)

Know these families: 1-D (house robber, climbing stairs, LIS), 2-D grid (unique paths, edit distance, LCS), knapsack (0/1 vs unbounded — the loop order differs), interval DP, and bitmask DP. Always start with the recursive + memo version, then convert to a table if asked.

13. Prefix sums and difference arrays

python

pre = list(accumulate(nums, initial=0))
range_sum = pre[j + 1] - pre[i]                # O(1) after O(n) preprocessing

def subarray_sum_equals_k(nums, k):            # count subarrays summing to k
    seen, total, run = {0: 1}, 0, 0
    for x in nums:
        run += x
        total += seen.get(run - k, 0)          # how many prefixes make run - prefix == k
        seen[run] = seen.get(run, 0) + 1
    return total

The prefix-sum-plus-hashmap combination solves a whole family of "count subarrays with property X" problems and is worth drilling on its own.

14. Monotonic stack

Signal: "next greater element", largest rectangle in a histogram, daily temperatures, trapping rain water.

python

def daily_temperatures(t):
    res, stack = [0] * len(t), []            # stack holds indices, temps decreasing
    for i, temp in enumerate(t):
        while stack and t[stack[-1]] < temp:
            j = stack.pop(); res[j] = i - j
        stack.append(i)
    return res

Each index is pushed and popped once → O(n), which always surprises people who expect O(n²).

15. Trie

Signal: prefix search, autocomplete, word dictionaries, wildcard matching.

python

class Trie:
    def __init__(self): self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word: node = node.setdefault(ch, {})
        node["$"] = True
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node: return False
            node = node[ch]
        return True

O(L) per operation regardless of dictionary size, at the cost of memory. Mention the alternative — a sorted list plus binary search on prefix — and why a trie wins when you need many prefix queries.