DSA Patterns Cheat Sheet: Quick Reference for Every Coding Interview

The ten minutes before an interview are not for learning. They're for remembering.

You've done the work. You've solved the problems. You've stared at enough sliding window explanations that they haunt your dreams. What you need now is a fast scan that fires up the right pattern when you see a problem, not a tutorial that explains what a tree is.

This is that scan. One table, every pattern, the gotcha that bites people who definitely knew better. Not a beginner guide. Assumes you've done the reps.

The Master Pattern Table

If a problem matches a signal in this table and you're reaching for something else, stop and reconsider.

Pattern	Recognition Signal	Time	Space
Two Pointers (converging)	sorted array, pairs, triplets, palindrome	O(n)	O(1)
Two Pointers (fast/slow)	linked list cycle, middle of list	O(n)	O(1)
Sliding Window	subarray/substring + constraint	O(n)	O(1) to O(k)
Binary Search	sorted input, or "minimize the maximum"	O(log n)	O(1)
Binary Search on Answer	minimize max, maximize min, feasibility	O(n log n)	O(1)
Prefix Sum	range sum queries, subarray sums	O(n) build, O(1) query	O(n)
Hash Map / Set	frequency, two sum, anagram, seen-before	O(n)	O(n)
Tree DFS	path sum, subtree, root-to-leaf	O(n)	O(h)
Tree BFS	level order, shortest path in tree	O(n)	O(w)
Graph BFS	shortest path (unweighted), multi-source	O(V+E)	O(V)
Graph DFS	flood fill, cycle detection, components	O(V+E)	O(V)
Topological Sort	dependencies, course schedule, DAG ordering	O(V+E)	O(V)
Union Find	dynamic connectivity, undirected cycle	O(α(n)) per op	O(n)
Heap / Top-K	k largest, k closest, median stream	O(n log k)	O(k)
Monotonic Stack	next greater/smaller, histogram, temperatures	O(n)	O(n)
Backtracking	all combinations, permutations, valid configs	O(2^n) or O(n!)	O(n)
1D DP	min/max/count, single sequence	O(n)	O(n) → O(1)
2D DP	two strings, grids, knapsack	O(m×n)	O(m×n) → O(n)
Intervals	meetings, overlapping ranges, scheduling	O(n log n)	O(n)

Pattern recognition decision flow, start at the top, first matching branch picks your pattern

When nothing's clicking: follow the branches. Sorted input and pairs? Two pointers. Subarray with a constraint? Sliding window. Frequency or lookup? Hash map. The brute force is always the first step.

Two Pointers

Sorted array plus a target condition almost always resolves with two pointers, not a nested loop. Every O(n²) pair-finding loop you ever wrote was a two-pointer problem in disguise.

Two modes:

Converging pointers start at opposite ends and move inward. Use for pair/triplet problems, palindrome checks, Container with Most Water.

left, right = 0, len(nums) - 1
while left < right:
    if condition_met(nums[left], nums[right]):
        result.append(...)
        left += 1
        right -= 1
    elif too_small:
        left += 1
    else:
        right -= 1

Fast/slow pointers both start at head. Fast moves two steps, slow moves one. Use for cycle detection, finding the middle, and removing the nth node from end.

Gotcha for 3Sum: sort first. After fixing the first element, use converging pointers for the pair. Skip duplicates explicitly: while left < right and nums[left] == nums[left-1]: left += 1. Miss this and you submit a solution that fails on [-2, 0, 0, 2, 2] and feels genuinely personal.

Sliding Window

Subarray or substring problems with a constraint on the window's contents resolve in O(n), not O(n²). The nested loop is always the wrong answer here.

Fixed window: advance both pointers together. Variable window: expand right freely, shrink left when the constraint breaks.

left = 0
window = {}
result = 0
for right in range(len(s)):
    window[s[right]] = window.get(s[right], 0) + 1
    while constraint_violated(window):
        window[s[left]] -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        left += 1
    result = max(result, right - left + 1)

Gotcha: "exactly k distinct characters" does not work with a direct window. The constraint isn't monotonic, so the shrink logic breaks. Use at_most(k) - at_most(k-1). Yes, it feels like a trick. It is a trick.

See Sliding Window in depth.

Binary Search

Use the overflow-safe midpoint in every language. Java's binary search had this bug in production for nine years before Joshua Bloch wrote a blog post about it in 2006 and everyone realized they'd been running broken code in silence.

left, right = 0, len(nums) - 1
while left <= right:
    mid = left + (right - left) // 2   # safe in all languages
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
return -1

Variants:

Leftmost target: when nums[mid] == target, set right = mid - 1 and keep going.
Rightmost target: when nums[mid] == target, set left = mid + 1.
Binary search on answer: define feasible(mid), binary search over the answer space. Pattern: "minimize the maximum X" or "maximize the minimum X." Wikipedia's binary search article covers the formal invariant.

Trees

DFS runs in O(n) time and O(h) stack space. For balanced trees h is O(log n). For a skewed linked-list tree, h is O(n). The interviewer asking you "what's the space complexity?" is usually fishing for whether you know this distinction.

Three traversal orders:

Order	Visit Pattern	Classic Use
Preorder	root → left → right	serialize, copy
Inorder	left → root → right	sorted output from BST
Postorder	left → right → root	delete tree, evaluate from leaves

Recursive DFS template:

def dfs(node):
    if not node:
        return base_value
    left = dfs(node.left)
    right = dfs(node.right)
    return combine(node.val, left, right)

BFS template (level order):

from collections import deque
queue = deque([root])
while queue:
    for _ in range(len(queue)):   # process one level at a time
        node = queue.popleft()
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

Gotcha: BST validation requires passing a valid range down, not just comparing to the parent node. A subtree can satisfy the local parent constraint while violating a grandparent bound. This catches about 40% of people who think they've solved it correctly.

Graphs

BFS for shortest paths in unweighted graphs. DFS for everything else. Both are O(V+E). The choice between them is almost never about speed, it's about what the problem actually needs.

Graph BFS:

from collections import deque
visited = {start}
queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

Topological sort with Kahn's algorithm:

in_degree = {n: 0 for n in range(num_nodes)}
for u, v in edges:
    in_degree[v] += 1
queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
if len(order) != num_nodes:
    return []  # cycle detected

See BFS vs DFS decision guide.

Dynamic Programming

DP applies when the problem has overlapping subproblems and a recurrence you can write down. Start with the recursive definition. Cache it. That's the whole algorithm.

Recognition signals from the DP framework:

"minimum number of," "maximum value," "number of ways"
Each decision narrows the future state space
Brute force has exponential calls and many of them repeat

Five-step setup:

Define the state (what parameters uniquely describe a subproblem).
Write the recurrence.
Identify base cases.
Choose top-down (memo dict) or bottom-up (table).
Optimize space if only a fixed look-back is used.

Common patterns:

Problem	Recurrence shape
0/1 Knapsack	`dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)`
Unbounded Knapsack	`dp[w] = max(dp[w-ci] + vi)` (scan forward)
LCS	`dp[i-1][j-1]+1` if chars match, else `max(dp[i-1][j], dp[i][j-1])`
LIS	`max(dp[j]+1 for j<i if nums[j] < nums[i])`
Coin Change	`min(dp[i-c]+1 for c in coins if c <= i)`

Space optimization: scan backward through the weight dimension for 0/1 knapsack (prevents using the same item twice in a single pass). Scanning forward gives unbounded knapsack. Mixing these up is the classic knapsack bug.

Heaps

Python's heapq is a min-heap. Negate values to get max-heap behavior. This is the kind of thing that costs you five minutes in an interview while you're staring at the wrong output wondering if you have a logic error.

import heapq
heap = []
heapq.heappush(heap, val)
smallest = heapq.heappop(heap)

# max-heap
heapq.heappush(heap, -val)
largest = -heapq.heappop(heap)

For k-th largest: maintain a min-heap of size k. Every new element replaces the heap min if it's larger. The heap root is the k-th largest when done.

Running median: two heaps. A max-heap holds the lower half, a min-heap holds the upper half. Rebalance after each insert so sizes differ by at most one.

Union Find

Dynamic connectivity in nearly O(1) per operation. With path compression and union by rank, it's practically free.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component (cycle in undirected graph)
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

The amortized cost with both optimizations is O(α(n)), where α is the inverse Ackermann function. It's at most 4 for any input you'll encounter in any interview, on any planet, before the heat death of the universe. Treat it as O(1).

Backtracking

Always copy the current state when appending to results. Adding the reference adds an object that will be emptied by later undos. This is the single most common backtracking bug and it's satisfying to debug exactly once.

result = []
def backtrack(start, current):
    if is_complete(current):
        result.append(current[:])  # copy, not reference
        return
    for i in range(start, len(candidates)):
        if should_prune(i, current):
            continue
        current.append(candidates[i])
        backtrack(next_start(i), current)
        current.pop()

Three complexity classes you must be able to state without thinking:

Output type	Time complexity
All subsets	O(n · 2^n)
All permutations	O(n · n!)
k-size combinations	O(k · C(n,k))

These are the costs to generate all outputs. They're also the floor you cannot beat for problems that require complete enumeration. If someone asks you to "optimize" a permutation generator past O(n · n!), they're confused about what they're asking.

Monotonic Stack

Every element is pushed once and popped once, so the total work is O(n) regardless of the nested while loop. The while loop looks scary but it's amortized. Interviewers love watching candidates convince themselves it's O(n²).

stack = []   # stores indices
result = [-1] * len(nums)
for i, val in enumerate(nums):
    while stack and nums[stack[-1]] < val:
        idx = stack.pop()
        result[idx] = val   # val is the next greater element for idx
    stack.append(i)

Use a monotonically decreasing stack (each new element pops anything smaller) for "next greater element." Flip the comparison for "next smaller element." Pair with a deque to get the sliding window maximum pattern in O(n).

Intervals

Sort by start time. Two intervals overlap when the later start time is less than or equal to the earlier end time.

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

For minimum removals to make intervals non-overlapping: sort by end time instead. Greedily take each interval that starts at or after the last accepted end. Count what you skip. Sorting by start time for this variant is a trap that produces wrong answers.

The Complexity Floor Rules

These are the minimum costs for problem types. If your approach is worse, there's a better algorithm. If your approach matches the floor, you're done optimizing.

Situation	Floor
Must examine every element	O(n)
Must consider every pair	O(n²) unless you use a hash or sorted structure
Must produce all orderings	O(n!)
Must produce all subsets	O(2^n)
Sorting is required	O(n log n)
Search in sorted space	O(log n)

If a problem says "return all," your output size is the floor. You cannot output n! permutations faster than O(n!). This sounds obvious until someone asks you to "optimize" a combinations generator and you need to explain calmly that the output itself is O(k · C(n,k)).

Quick Reference

Pattern recognition is the whole skill at the medium level. Implementation follows.
"Sorted array" means two pointers or binary search.
"Subarray/substring with constraint" means sliding window.
"All valid combinations/permutations" means backtracking.
"Connected components or cycle detection" means BFS/DFS or Union-Find.
"k-th largest/smallest" means a heap of size k.
"Minimize/maximize over choices with dependencies" means DP.
When stuck: state the brute force complexity, then ask what structure removes redundant work.

Recognition is fastest when you've practiced naming patterns out loud under pressure, not just solved problems quietly in a browser tab. SpaceComplexity runs voice-based mock interviews with rubric feedback so you can train that recognition in real interview conditions, not discover the gap when it counts.