Blog

Introduction to Algorithm Design Patterns (with Python Examples)

Algorithm design patterns are reusable problem-solving strategies: ways of structuring a solution that work across many different problems. Not to be confused with the object-oriented design patterns (Singleton, Observer and so on) from software architecture, they are about how you get from a problem statement to an efficient procedure. This page covers the six you meet most in interviews and coursework, each with a short tested Python example, the signal that tells you to use it, and its main pitfall.

The six patterns at a glance

Pattern Core idea Typical signal Classic example
Divide and conquer Split into independent subproblems, solve, combine Problem halves cleanly; combining is cheap Merge sort, binary search
Dynamic programming Cache answers to overlapping subproblems “Number of ways”, “min/max cost”, brute force repeats work Fibonacci, coin change, knapsack
Greedy Take the best local choice, never reconsider A sorted order or exchange argument exists Interval scheduling
Backtracking Build candidates step by step, undo when stuck “All” solutions, constraints prune early Subsets, N-Queens, Sudoku
Two pointers Two indices move through the data Sorted input, pairs, in-place edits Pair sum in a sorted array
Sliding window A range that grows and shrinks as you scan Contiguous subarray or substring Max sum of k consecutive items

1. Divide and conquer

Split the input, solve each part recursively, then combine. It works when the parts do not depend on each other. Merge sort sorts each half and merges two sorted lists in linear time, giving O(n log n) overall.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

print(merge_sort([5, 2, 9, 1, 5, 6]))  # [1, 2, 5, 5, 6, 9]

Using <= when comparing keeps equal elements in their original order (a stable sort). Pitfall: copying slices costs extra memory; in-place variants like quicksort avoid it at the price of a worse worst case. Practise with the Merge Sort lesson.

2. Dynamic programming

If a recursive solution calls the same subproblem many times, store the results. The naive recursive Fibonacci is exponential because fib(2) is recomputed over and over; with a cache it takes O(n).

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025

That is top-down (memoization). Bottom-up (tabulation) fills a table from the smallest case up and avoids recursion depth limits. Python’s default recursion limit is about 1000, so a very deep memoized recursion can fail where a loop would not. Pitfall: defining the state wrongly. Before writing code, say in one sentence what dp[i] means. See our post on tabulation and memoization.

3. Greedy algorithms

A greedy algorithm makes the locally best choice at every step and never revisits it. It is fast and simple, but only correct when the problem has a structure that justifies it, and that needs an argument, not a hunch.

The coin change problem shows both sides. With US coins, taking the largest coin first is optimal. With other denominations it is not, and dynamic programming gives the right answer:

def coins_greedy(coins, amount):
    n = 0
    for c in sorted(coins, reverse=True):
        n += amount // c
        amount %= c
    return n if amount == 0 else -1

def coins_dp(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] < INF else -1

print(coins_greedy([1, 5, 10, 25], 63), coins_dp([1, 5, 10, 25], 63))  # 6 6
print(coins_greedy([1, 3, 4], 6), coins_dp([1, 3, 4], 6))              # 3 2

For coins 1, 3, 4 and amount 6, greedy picks 4 + 1 + 1 (three coins) while the optimum is 3 + 3 (two). Pitfall: assuming greedy works because it passes the examples. Problems where it is provably correct include scheduling the maximum number of non-overlapping intervals by earliest end time (try Non Overlapping Intervals) and Huffman coding.

4. Backtracking

Backtracking builds a solution one choice at a time and undoes the last choice when it hits a dead end or finishes a candidate. It is depth-first search over a tree of decisions. Generating all subsets is the simplest case: for each element, either skip it or include it.

def subsets(nums):
    res = []
    def go(i, cur):
        if i == len(nums):
            res.append(cur[:])      # copy, because cur keeps changing
            return
        go(i + 1, cur)              # skip nums[i]
        cur.append(nums[i])         # choose nums[i]
        go(i + 1, cur)
        cur.pop()                   # undo
    go(0, [])
    return res

print(subsets([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Two details matter: append a copy of cur, not cur itself, and undo every change you make. The runtime is exponential (2n subsets here), so the power of the pattern comes from pruning: abandoning a branch as soon as it cannot lead to a valid answer, as N-Queens does when two queens attack each other. Practise with Generate Parentheses.

5. Two pointers

Two indices walk through the data, usually from both ends toward the middle or one behind the other. In a sorted array, finding a pair with a given sum takes O(n) instead of O(n²): if the current sum is too small, move the left pointer right; too large, move the right pointer left.

def two_sum_sorted(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return []

print(two_sum_sorted([1, 2, 4, 7, 11, 15], 15))  # [2, 4]

Here 4 + 11 = 15, at indices 2 and 4. Pitfall: the pattern needs the order that justifies moving a pointer; on unsorted data use a hash table instead.

6. Sliding window

A sliding window is two pointers marking a contiguous range, where you update a running value as the range moves instead of recomputing it. For the maximum sum of k consecutive elements, add the new element and subtract the one that left:

def max_window(a, k):
    cur = sum(a[:k])
    best = cur
    for i in range(k, len(a)):
        cur += a[i] - a[i - k]
        best = max(best, cur)
    return best

print(max_window([2, 1, 5, 1, 3, 2], 3))  # 9

The best window is [5, 1, 3]. This is O(n) rather than O(nk). Windows whose size varies (longest substring without repeating characters, for instance) grow the right edge and shrink the left edge while a condition is violated. Pitfall: it assumes that shrinking the window can only help restore the condition, which breaks if the array has negative numbers and you are looking for a sum limit. The Sliding Window Technique lesson walks through it.

How to choose a pattern

  1. Write down the brute force and its complexity. The wasted work usually names the pattern: repeated subproblems mean DP; repeated scanning of a range means sliding window; a nested loop over a sorted array means two pointers.
  2. Read the constraints. Small n (up to about 20) allows backtracking. Large n needs O(n log n) or better.
  3. Ask whether the problem asks for one best answer, a count, or all answers. All answers means backtracking; a count or best value often means DP or greedy.
  4. If you suspect greedy, try to break it with a small counterexample before committing.
  5. State the invariant in a sentence: what is true at every step of your loop or recursion.

Real programs mix these. Dijkstra’s shortest-path algorithm is greedy with a heap; a DP over subsets is backtracking with caching. Learn the patterns separately, then notice how they combine. Practise each pattern on its own first, then on mixed problem sets.

A lesson in AlgoCademy: the step to write, the line typed in the editor and checked, Step 3 passed; then a typo, the error pointing at its line, the fix, and Step 4 passed.

Before you go

Start thinking like a software engineer.

Learn to code and solve interview problems, one small, checked step at a time.

Try Two Sum free

No account needed. You write real code in your browser.