The Pattern Playbook

A DSA interview is rarely a test of whether you can invent an algorithm on the spot. It is a test of pattern recognition under time pressure. Strong candidates don’t see “a problem about painting houses”; they see “this is an optimization over a sequence that smells like optimal substructure — probably DP.” The surface story is a costume; underneath, only about a dozen skeletons recur.

For each family you’ll learn the trigger phrases that betray the pattern, the sub-types it splits into, a reusable code skeleton, the complexity profile interviewers expect, and the pitfalls that sink otherwise-correct solutions.

The Recognition Cheat-Sheet

In an interview, your first 60 seconds should map the prompt onto one of these rows.

A 90-Second Complexity Refresher

Interviewers expect you to state time and space complexity (Big-O) unprompted. Anchor every solution to this ladder, fastest to slowest:

Sub-types you will meet

• Interval scheduling / activity selection. Maximize non-overlapping intervals. Key: sort by end time, take the earliest finisher.
• Interval merging & minimum resources. Merge overlaps or count max simultaneous overlap (meeting rooms). Key: sort by start, sweep with a heap of end times.
• Sorting by a ratio / deadline. Job sequencing, fractional knapsack. Key: sort by value/weight or by deadline.
• Greedy on a heap. Repeatedly combine the two best elements (Huffman coding, “connect ropes,” task schedulers).
• Greedy + invariant sweep. Jump Game, Gas Station, Candy — maintain a running “reach” or “tank.”

The reusable skeleton

Greedy almost always collapses to sort, then sweep maintaining one running quantity:

def greedy_template(items):
    # 1) Choose the sort key that makes the best choice obvious.
    items.sort(key=lambda x: x.end)   # earliest finish time

    chosen, frontier = [], float('-inf')  # frontier = end-time of last chosen interval.
    # float('-inf') is "negative infinity": a starting value smaller than any real
    # number, so the very first interval always passes the check below.
    for it in items:
        if it.start >= frontier:    # valid if it starts after the last one ended
            chosen.append(it)        # take it (earliest-finishing = greedy pick)
            frontier = it.end        # advance: next item must start >= here
    return chosen                   # one pass; O(n log n) total (sort dominates)

Worked intuition — Activity Selection

Why sort by end time? Finishing earliest leaves the most room for everything after it. Sorting these intervals by end time picks A → C → E (three activities); grabbing a long interval early would block more of the timeline.

Complexity: dominated by the sort — O(n log n) time, O(1)–O(n) space.

The five-step recipe

Sub-types you will meet

• Linear / 1-D DP. Fibonacci, Climbing Stairs, House Robber, Decode Ways, Maximum Subarray (Kadane), Word Break.
• Knapsack family. 0/1 knapsack, subset-sum, partition equal subset, coin change, target sum. State: dp[i][cap].
• Two-sequence DP. Longest Common Subsequence, Edit Distance, wildcard matching. State: dp[i][j] over two strings.
• Grid DP. Unique Paths, Minimum Path Sum, Dungeon Game.
• Interval DP. Matrix-Chain, Burst Balloons, Palindrome Partitioning II.
• Sequence / LIS. Longest Increasing Subsequence, Russian Doll Envelopes.
• Bitmask DP. Travelling Salesman, “Shortest Path Visiting All Nodes” (n ≤ 20).

Two skeletons: top-down and bottom-up

Each placeholder name below is defined in the comments — that’s the part most beginners get stuck on.

# LEGEND — replace each name with your problem's concrete logic:
#   state          = facts that identify a sub-problem, e.g. (index, capacity_left)
#   is_base(s)     = True when s needs no more recursion (e.g. capacity == 0)
#   base_value(s)  = the answer at a base case (e.g. 0)
#   WORST          = the starting "nothing yet" value: -inf if maximizing, +inf if minimizing
#   choices(s)     = the decisions available now, e.g. [skip item, take item]
#   better(a,b)    = max if maximizing, min if minimizing
#   cost(c)        = the immediate value/penalty of making choice c (e.g. value[i])
#   next_state(s,c)= the SMALLER sub-problem you move to after choosing c

from functools import lru_cache
def solve_topdown(n, data):
    @lru_cache(maxsize=None)              # the cache = memoization
    def dp(state):
        if is_base(state): return base_value(state)
        best = WORST
        for choice in choices(state):
            best = better(best, cost(choice) + dp(next_state(state, choice)))
        return best
    return dp(initial_state)

Worked intuition — 0/1 Knapsack table

dp[i][w] = best value using the first i items with capacity w. Either skip item i, or take it if it fits. Each row depends only on the row above — that’s the hook for the O(W) space optimization. (Items here: weight 2/value 3, weight 3/value 4, weight 2/value 1.)

Complexity: (number of states) × (work per transition). 1-D ≈ O(n); knapsack O(nW) — pseudo-polynomial; two-sequence O(nm); interval DP O(n³); bitmask O(2ⁿ·n).

The Master Theorem in one box

For T(n) = a·T(n/b) + f(n) — where a = number of recursive sub-calls, b = shrink factor, f(n) = divide/combine cost — compare f(n) against n^{log_b a}:

ε is just a small positive number; it means f(n) is polynomially smaller/larger, not merely equal. Examples: merge sort T(n)=2T(n/2)+Θ(n) → Case 2 → Θ(n log n). Binary search T(n)=T(n/2)+Θ(1) → Θ(log n).

The reusable skeleton

# Half-open range convention: the active slice is arr[lo:hi]  (lo inclusive, hi exclusive)
def divide_and_conquer(arr, lo, hi):
    if hi - lo <= 1:                 # 0 or 1 element -> trivially solved
        return solve_trivial(arr, lo, hi)
    mid = (lo + hi) // 2            # split: left=arr[lo:mid], right=arr[mid:hi]
    left  = divide_and_conquer(arr, lo, mid)   # solve halves INDEPENDENTLY
    right = divide_and_conquer(arr, mid, hi)
    # combine reads ACROSS the midpoint (this is where the speedup lives):
    return combine(left, right, arr, lo, mid, hi)

Worked intuition — counting inversions

An inversion is a pair i<j with a_i>a_j (out of order). Brute force is O(n²); D&C counts them in O(n log n) by piggy-backing on merge sort: when merging two sorted halves, every time you pull an element from the right half while elements remain in the left, it forms an inversion with all of them at once.

Complexity: balanced D&C with a linear combine is O(n log n); quickselect is O(n) average; binary search and fast exponentiation are O(log n).

Sub-types you will meet

• Converging two pointers (sorted). Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water, valid palindrome.
• Fast/slow pointers. Linked-list cycle detection (Floyd), find the middle, Happy Number.
• In-place partition. Remove Duplicates, Move Zeroes, Dutch National Flag (sort colors).
• Fixed-size window. Max average subarray of length k.
• Variable-size window. Longest Substring Without Repeating; Minimum Size Subarray Sum; At Most K Distinct; Minimum Window Substring.
• Monotonic-deque window. Sliding Window Maximum; Shortest Subarray with Sum ≥ K.

The variable-size window skeleton

def longest_valid_window(s):
    from collections import defaultdict
    count = defaultdict(int)   # char -> frequency in the window (missing keys default to 0)
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1                 # 1) EXPAND: pull s[right] into the window
        # is_valid(count) is YOUR yes/no test, e.g. "len(count) <= K" for "at most K distinct"
        while not is_valid(count):     # 2) CONTRACT while the window breaks the rule
            count[s[left]] -= 1
            if count[s[left]] == 0: del count[s[left]]  # keep len(count) = # distinct chars
            left += 1
        best = max(best, right - left + 1)   # 3) RECORD (window length = right-left+1)
    return best

Complexity: O(n) for a single pass; O(1) space for pure two-pointer, O(k) for a window backed by a map.

Sub-types you will meet

• Grid / flood fill. Number of Islands, Flood Fill, Rotting Oranges (multi-source BFS), Surrounded Regions.
• Connectivity & components. Connected Components, Accounts Merge, Redundant Connection (Union-Find).
• Topological sort (DAGs). Course Schedule I/II, Alien Dictionary, build-order resolution.
• Shortest path. Word Ladder (BFS), Network Delay Time (Dijkstra), Cheapest Flights (Bellman-Ford).
• Cycle detection. Directed (3-color DFS) vs. undirected (Union-Find or parent-tracking DFS).
• Bipartite / coloring. Is Graph Bipartite, Possible Bipartition.
• MST. Kruskal (Union-Find) or Prim (heap): Min Cost to Connect All Points.

Three skeletons

from collections import deque
# graph = adjacency list: each node maps to a list of neighbors, e.g. {0:[1,2], 1:[0,3]}
def bfs(start, graph):
    q, seen = deque([(start, 0)]), {start}   # pre-add start so it's never re-queued
    while q:
        node, dist = q.popleft()
        if is_goal(node): return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)                # mark on ENQUEUE, not dequeue
                q.append((nxt, dist + 1))
    return -1

class DSU:                              # Union-Find / Disjoint Set Union
    def __init__(self, n):
        self.parent = list(range(n)); self.rank = [0]*n  # rank ~ tree height
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving (flattens tree)
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False          # already connected -> a cycle edge
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra  # union by rank
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

Worked intuition — BFS spreads in rings

BFS visits all nodes at distance 1, then all at distance 2, and so on — so the first time it reaches the goal, it has used the fewest edges.

Complexity: BFS/DFS O(V+E); Dijkstra O((V+E)·log V); Union-Find O(α(n)) ≈ O(1); topological sort O(V+E).

Sub-types you will meet

• Subsets / power set. Include-or-exclude each element. Subsets, Subsets II.
• Combinations. Choose k of n, or all combos summing to a target. Combination Sum I/II/III.
• Permutations. All orderings; with/without duplicates.
• Partitioning. Palindrome Partitioning, Restore IP Addresses.
• Grid / constraint search. Word Search, N-Queens, Sudoku Solver, Generate Parentheses.

The universal skeleton

# choices = the INPUT list (e.g. nums). start = index this call may pick from.
def backtrack(start, path, results, choices):
    if is_complete(path):              # e.g. len(path)==k, or sum(path)==target
        results.append(path[:])        # append a COPY, not the live list!
        return
    for i in range(start, len(choices)):
        if not is_valid(choices[i], path): continue   # prune dead branches early
        if i > start and choices[i] == choices[i-1]: continue  # skip duplicates (sorted)
        path.append(choices[i])                  # 1) CHOOSE
        backtrack(i + 1, path, results, choices) # 2) EXPLORE (i+1 = no reuse; i = reuse)
        path.pop()                               # 3) UNCHOOSE (restore state)
    return results

Complexity: inherently exponential — subsets O(2ⁿ), permutations O(n·n!), combinations O(C(n,k)·k). Pruning lowers the constant, not the class. Acceptable only for small n.

Binary search on the answer — the mental shift

When feasible(x) is monotonic (all F’s then all T’s), binary-search for the boundary — the first T:

The boundary (first T) is your answer. The array itself need not be sorted — only the yes/no test must flip once.

Sub-types you will meet

• Classic binary search. Search Insert Position, Find First/Last Position, Search in Rotated Sorted Array.
• Binary search on answer. Koko Eating Bananas, Capacity to Ship in D Days, Split Array Largest Sum, Median of Two Sorted Arrays.
• Top-K / K-th with a heap. Kth Largest, Top K Frequent, K Closest Points.
• Two heaps. Find Median from Data Stream, Sliding Window Median, IPO.
• BST / tree. Validate BST, Kth Smallest in a BST, Lowest Common Ancestor.

Three skeletons

# LOWER-BOUND BINARY SEARCH: first index where feasible(x) is True.
# Half-open [lo, hi): lo inclusive, hi exclusive. Loop ends when lo == hi.
def binary_search(lo, hi, feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2     # avoids integer overflow in Java/C++
        if feasible(mid): hi = mid       # answer is mid or to the LEFT
        else:             lo = mid + 1   # answer is strictly RIGHT
    return lo

import heapq
# TOP-K LARGEST: keep a MIN-heap of size k. The root is the weakest kept; evict it.
def top_k_largest(nums, k):
    heap = []                         # Python heapq is a min-heap
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k: heapq.heappop(heap)  # drop the current minimum
    return heap                       # the k largest (unordered)

# TWO HEAPS running median: lo = max-heap (store NEGATED), hi = min-heap.
class MedianFinder:
    def __init__(self): self.lo, self.hi = [], []
    def add(self, num):
        heapq.heappush(self.lo, -heapq.heappushpop(self.hi, num))  # route through hi
        if len(self.lo) > len(self.hi):
            heapq.heappush(self.hi, -heapq.heappop(self.lo))        # rebalance
    def median(self):
        if len(self.hi) > len(self.lo): return self.hi[0]
        return (self.hi[0] - self.lo[0]) / 2   # lo[0] is negative, so this ADDS the max of lo

Complexity: binary search O(log n); on-answer O(n log range); heap push/pop O(log n); top-K O(n log k); quickselect O(n) average; BST ops O(log n).

Knowing seven patterns is necessary but not sufficient — you need a routing procedure that maps an unseen prompt to the right pattern in two minutes. Walk these questions top to bottom; the first “yes” is usually right, and the constraint size breaks ties.

How the families relate

The interview communication protocol

Pattern recognition wins the algorithm; communication wins the offer. Narrate these six beats:

• 1 · Clarify & restate. Confirm input ranges, edge cases (empty, single, duplicates, negatives), and exact output. Input sizes drive complexity targets.
• 2 · Brute force first. State the naive solution and its complexity out loud — it shows you understand the problem before optimizing.
• 3 · Identify the pattern. Name it and justify the trigger.
• 4 · Design before coding. Define the state / invariant / pointers, the transition, base cases, and target complexity — then get a nod.
• 5 · Code cleanly, narrate. Write the skeleton, talk through each line, keep names meaningful.
• 6 · Test & analyze. Dry-run a small example and edge cases, then state final time/space complexity.

Constraint → complexity (work backward from n): n ≤ 12 → O(n!); n ≤ 20 → O(2ⁿ) bitmask DP; n ≤ 2000 → O(n²); n ≤ 10⁵ → O(n log n); n ≥ 10⁶ → O(n) or O(log n).

Test yourself → 30-question exam

These are the same definitions that pop up when you hover the dotted terms above. Written for someone new to programming.