Interview pattern guide

DSA Patterns Cheat Sheet: 29 coding interview patterns

Most coding interview questions are one of a small number of patterns in disguise. Once you can name the pattern from the problem statement, the solution is usually a template plus a few details. For every pattern below you get the signals that give it away, the core idea, its complexity, the mistake that costs people the most time, and the problems from our Blind 75, LeetCode 150 and DSA sheet that use it (285 problems in total).

How to use this guide

  1. Read one pattern: the signals and the core idea, and try to write the template from memory.
  2. Solve two or three of its problems, starting with the Blind 75 ones listed first.
  3. On a sheet, filter by that pattern and keep going until a new problem in it takes under 25 minutes.
  4. Then mix patterns with the sheet's Random picker, because in an interview nobody tells you the pattern.

Prefer guided lessons? The free DSA Patterns course teaches 16 of these patterns with runnable Python, exercises and quizzes.

All patterns at a glance

Stacks and linked lists

Trees

Ordering and choosing

Search and dynamic programming

Bits, maths and design

Arrays and strings

Most interview problems start here. These patterns replace a nested loop with one pass.

Hash Map / Set

When to use it: Trade memory for O(1) lookups: count, deduplicate, or remember what you have already seen.

Signals in the problem

  • "Find a pair / duplicate / complement"
  • "Group items that are equivalent" (anagrams, same key)
  • A brute force that compares every pair

Core idea

Walk the input once and store what you have seen in a hash map or set, keyed by whatever you will need to look up later (the value, its complement, a sorted signature, a count). Each lookup is O(1) on average, so a pairwise O(n²) check becomes O(n).

Template (Python)

seen = {}
for i, x in enumerate(nums):
    if target - x in seen:
        return [seen[target - x], i]
    seen[x] = i
Complexity
O(n) time, O(n) extra space.
Common mistake
Inserting before checking. In Two Sum, look up target - x first and insert x after, or an element can pair with itself.

Practice problems (17)

5 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “Hash Map / Set”).

Two Pointers

When to use it: Move two indices toward each other (or outward from a centre) over sorted or symmetric input to drop a nested loop.

Signals in the problem

  • Input is sorted, or you are allowed to sort it
  • "Pair / triplet with sum", "palindrome", "reverse in place"
  • You need O(1) extra space

Core idea

Put one pointer at each end (or both at the start for in-place compaction) and move the pointer whose move can still improve the answer. Sorting first lets every comparison safely discard one candidate, so the search is linear.

Template (Python)

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
Complexity
O(n) after an O(n log n) sort if one is needed; O(1) extra space.
Common mistake
Skipping duplicates incorrectly in 3Sum: skip equal values only after recording an answer, and only on the pointer you just moved.

Practice problems (17)

5 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “Two Pointers”).

Sliding Window

When to use it: Grow the right edge, shrink the left edge while the window breaks a rule; best for contiguous subarrays and substrings.

Signals in the problem

  • "Longest / shortest / count of contiguous subarray or substring"
  • A constraint on the window: at most k distinct, sum ≥ target, no repeats
  • Fixed-size windows: "every window of size k"

Core idea

Extend the right edge one step at a time and update the window state (counts, sum). While the window breaks the rule, shrink from the left. Each index enters and leaves once, so the whole scan is linear even though there is an inner loop.

Template (Python)

left = 0
for right, x in enumerate(s):
    add(x)
    while window_invalid():
        remove(s[left]); left += 1
    best = max(best, right - left + 1)
Complexity
O(n) time; O(k) or O(alphabet) space for the window state.
Common mistake
Using a sliding window when values can be negative and the condition is a sum: shrinking no longer helps monotonically. Switch to prefix sums plus a hash map.

Prefix / Suffix

When to use it: Precompute running sums or products from each side so every query becomes O(1).

Signals in the problem

  • "Sum of a range" asked many times
  • "Subarray sum equals k" (with negatives)
  • "Product of array except self"

Core idea

Precompute running totals so any range sum is prefix[r + 1] - prefix[l]. Combine with a hash map of earlier prefix values to count subarrays with a given sum in one pass. Products and suffix passes work the same way.

Template (Python)

count, run, seen = 0, 0, {0: 1}
for x in nums:
    run += x
    count += seen.get(run - k, 0)
    seen[run] = seen.get(run, 0) + 1
Complexity
O(n) to build, O(1) per query; O(n) space (often O(1) with two passes).
Common mistake
Forgetting to seed the map with prefix 0 → count 1, which misses subarrays that start at index 0.

Practice problems (2)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Prefix / Suffix”).

Matrix Traversal

When to use it: Walk a 2D grid layer by layer or in place; track boundaries carefully and reuse the grid for markers.

Signals in the problem

  • 2D grid with a traversal order (spiral, diagonal, layer)
  • "Rotate / transpose in place"
  • "Set rows and columns to zero"

Core idea

Track the four boundaries (top, bottom, left, right) and shrink them as you finish each side, or express the transform as two simpler ones (rotate = transpose + reverse rows). Reuse the first row/column as marker storage to get O(1) space.

Complexity
O(m·n) time, O(1) extra space for in-place variants.
Common mistake
Off-by-one on the last row or column in spiral order when the matrix is not square; re-check bounds after each side.

Practice problems (5)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Matrix Traversal”).

String / Array Simulation

When to use it: Follow the rules exactly as stated; careful index bookkeeping and edge cases are the whole problem.

Signals in the problem

  • The statement describes exact step-by-step rules
  • String formatting, parsing or encoding
  • No obvious algorithmic shortcut

Core idea

Implement the rules literally with careful index bookkeeping. Write out the edge cases (empty input, single element, trailing spaces, overflow) before coding; most of the difficulty is there.

Complexity
Usually O(n) in the size of the input or output.
Common mistake
Building strings by repeated concatenation in a loop; collect parts in a list and join once.

Stacks and linked lists

Pointer and ordering tricks: what was seen most recently, and how to rewire nodes safely.

Stack

When to use it: Last-in-first-out matching: brackets, nested structure, or the most recent unresolved item.

Signals in the problem

  • Matching brackets or tags
  • Nested structure: "decode string", "evaluate expression"
  • "Undo the most recent…"

Core idea

Push items while they are unresolved and pop when the matching closer arrives. For nested encodings push the context (current string, multiplier) when entering a level and combine on exit.

Complexity
O(n) time, O(n) space.
Common mistake
Not checking for an empty stack before popping, and not checking the stack is empty at the end.

Practice problems (7)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Stack”).

Monotonic Stack / Deque

When to use it: Keep a stack (or deque) in increasing or decreasing order so each element finds its next greater/smaller neighbour, or each window its max, in amortised O(1).

Signals in the problem

  • "Next greater / smaller element"
  • "Daily temperatures", "largest rectangle in histogram"
  • "Maximum of every window of size k" (deque version)

Core idea

Keep indices on a stack in increasing (or decreasing) value order. When a new value breaks the order, pop: the new value is the answer for every index you pop. A deque does the same for sliding-window maximum, also evicting indices that leave the window.

Template (Python)

stack = []  # indices, values decreasing
for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        j = stack.pop(); next_greater[j] = i
    stack.append(i)
Complexity
O(n) amortised, since each index is pushed and popped once; O(n) space.
Common mistake
Storing values instead of indices; you usually need the index to compute a distance or a width.

Practice problems (5)

Track your progress on DSA Sheet (filter by “Monotonic Stack / Deque”).

Linked List

When to use it: Rewire next pointers with a dummy head and a prev/curr pair; draw it before you code it.

Signals in the problem

  • "Reverse", "merge", "reorder" a list
  • Insert or delete nodes in place

Core idea

Use a dummy head so the first node is not a special case, and keep prev / curr / next pointers. Save next before you overwrite curr.next.

Template (Python)

prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev, curr = curr, nxt
return prev
Complexity
O(n) time, O(1) extra space.
Common mistake
Losing the rest of the list by reassigning curr.next before saving it. Draw three boxes before you code.

Fast & Slow Pointers

When to use it: Two pointers at different speeds find cycles, midpoints, or the k-th node from the end in one pass.

Signals in the problem

  • "Detect a cycle" in a list or a function sequence
  • "Middle of the list"
  • "k-th node from the end"

Core idea

Move one pointer twice as fast as the other (or start it k steps ahead). They meet inside a cycle, the slow one stops at the middle, or the trailing one lands k from the end. Floyd also finds the cycle entry by restarting one pointer from the head.

Complexity
O(n) time, O(1) space.
Common mistake
Checking fast.next without first checking fast, which crashes on even-length lists.

Practice problems (7)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Fast & Slow Pointers”).

Trees

Decide what each recursive call returns, or walk level by level with a queue.

Tree DFS

When to use it: Recurse on left and right subtrees and combine their answers; decide what each call returns.

Signals in the problem

  • Depth, diameter, path sum, balanced, same tree
  • "Lowest common ancestor"
  • Anything that combines answers from left and right subtrees

Core idea

Decide exactly what one recursive call returns for its subtree (a height, a best path ending here, a boolean), combine the two child results, and update a global answer when the answer can pass through the node.

Complexity
O(n) time, O(h) stack space where h is the height.
Common mistake
Returning the global answer instead of the value the parent needs (for example, in Maximum Path Sum the parent can only extend one branch).

Tree BFS

When to use it: Process a tree level by level with a queue; snapshot the queue size to separate levels.

Signals in the problem

  • "Level order", "right side view", "zigzag"
  • "Minimum depth" or anything per level

Core idea

Use a queue. At the start of each level, read the queue length and process exactly that many nodes, so levels never mix.

Template (Python)

q = deque([root])
while q:
    level = []
    for _ in range(len(q)):
        node = q.popleft(); level.append(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
Complexity
O(n) time, O(width) space.
Common mistake
Iterating over the queue while appending to it without snapshotting the level size first.

Binary Search Tree

When to use it: Use the ordering invariant: in-order traversal is sorted and each node bounds its subtree.

Signals in the problem

  • The tree is a binary search tree
  • "k-th smallest", "validate", "insert / delete"

Core idea

Use the ordering: an in-order traversal is sorted, and every node bounds the values allowed in its subtrees. Pass (low, high) bounds down when validating, and walk one branch when searching.

Complexity
O(h) per search or insert; O(n) for a full traversal.
Common mistake
Validating a BST by only comparing a node to its direct children; a deep descendant can still break the rule.

Trie

When to use it: A prefix tree for word lookups, prefix queries and searching many words at once.

Signals in the problem

  • "Starts with / prefix"
  • Search many words in a grid or a stream
  • Autocomplete or dictionary with wildcards

Core idea

Store words character by character in nested child maps with an end-of-word flag. Searching many words at once (Word Search II) walks the board and the trie together, pruning as soon as no word has the current prefix.

Complexity
O(length) per insert or lookup; space proportional to total characters.
Common mistake
Not pruning found words or dead branches in Word Search II, which makes it time out.

Graphs

Grids, dependencies and networks. Model the nodes and edges first; the algorithm usually follows.

Graph BFS / DFS

When to use it: Explore neighbours with a visited set; grids are graphs too.

Signals in the problem

  • Grids of cells ("islands", "rotting oranges")
  • "Connected", "reachable", "clone a graph"
  • Fewest steps on an unweighted graph (BFS)

Core idea

Build adjacency (or use grid neighbours), keep a visited set, and run DFS to explore components or BFS when you need the shortest number of steps. Multi-source BFS starts with every source in the queue at once.

Template (Python)

q = deque(sources); seen = set(sources); steps = 0
while q:
    for _ in range(len(q)):
        u = q.popleft()
        for v in neighbours(u):
            if v not in seen:
                seen.add(v); q.append(v)
    steps += 1
Complexity
O(V + E) time and space.
Common mistake
Marking a node visited when you pop it instead of when you push it, which adds duplicates to the queue.

Practice problems (15)

3 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “Graph BFS / DFS”).

Shortest Path

When to use it: Weighted edges: Dijkstra with a min-heap for non-negative weights, Bellman-Ford for at most k edges or negative weights, Floyd-Warshall for all pairs on small graphs.

Signals in the problem

  • Weighted edges: cost, time, price
  • "Cheapest flight within k stops"
  • "Network delay time"

Core idea

Dijkstra with a min-heap for non-negative weights; Bellman-Ford (k rounds of relaxation) when the number of edges is limited or weights can be negative; Floyd-Warshall for all pairs on small graphs.

Complexity
Dijkstra O(E log V); Bellman-Ford O(k·E); Floyd-Warshall O(V³).
Common mistake
Using plain BFS on weighted edges, or relaxing in place during a Bellman-Ford round (copy the distances per round when stops are limited).

Topological Sort

When to use it: Order nodes so every edge points forward (Kahn in-degree queue or DFS); a leftover node means a cycle.

Signals in the problem

  • Prerequisites, build order, task dependencies
  • "Is it possible to finish?" (cycle detection)
  • Order letters from a sorted alien dictionary

Core idea

Kahn: count in-degrees, queue every node with in-degree 0, and as you pop a node decrement its neighbours. If fewer than all nodes come out, there is a cycle.

Template (Python)

q = deque(n for n in nodes if indeg[n] == 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)
has_cycle = len(order) < len(nodes)
Complexity
O(V + E).
Common mistake
Building edges in the wrong direction (course → prerequisite instead of prerequisite → course).

Practice problems (3)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Topological Sort”).

Union-Find

When to use it: Merge components with path compression and union by rank to count groups or detect cycles.

Signals in the problem

  • "Number of connected components"
  • "Redundant connection", "accounts merge"
  • Edges arrive one at a time and you ask "already connected?"

Core idea

Give every node a parent pointer. find() follows parents to the root (compressing the path), union() links two roots (by rank or size). Two nodes are connected when they share a root.

Template (Python)

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]; x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    parent[ra] = rb; return True
Complexity
Almost O(1) amortised per operation (inverse Ackermann).
Common mistake
Forgetting path compression or union by rank, which degrades to O(n) per find on adversarial input.

Ordering and choosing

Problems about the best next item, overlapping ranges, or a choice you never need to undo.

Heap / Priority Queue

When to use it: Keep the k best items, or the next smallest across many sorted streams, in O(log n) per step.

Signals in the problem

  • "k largest / smallest / most frequent"
  • "Merge k sorted lists"
  • "Median of a data stream"

Core idea

Keep a min-heap of size k to retain the k largest items (or a max-heap for the k smallest). For many sorted streams, keep one head per stream in a heap. Two heaps balanced around the middle give a running median.

Complexity
O(n log k) for top-k; O(log n) per push or pop.
Common mistake
Sorting everything (O(n log n)) when k is small, or using the wrong heap direction for "top k".

Intervals

When to use it: Sort by start (or end), then sweep and merge or count overlaps.

Signals in the problem

  • Start/end pairs: meetings, ranges, bookings
  • "Merge", "insert", "minimum rooms", "non-overlapping"

Core idea

Sort by start time and sweep, merging when the next start is not after the current end. For "how many at once" sort starts and ends separately (or use a min-heap of end times). For "remove the fewest", sort by end and keep greedily.

Complexity
O(n log n) for the sort, then O(n).
Common mistake
Treating touching intervals ([1,2] and [2,3]) inconsistently; read whether the problem counts them as overlapping.

Practice problems (7)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Intervals”).

Greedy

When to use it: Make the locally best choice and prove you never need to undo it.

Signals in the problem

  • "Minimum number of jumps / coins / arrows"
  • A locally best choice seems obviously safe
  • Sorting by one key makes the answer fall out

Core idea

Make the choice that looks best right now and argue (exchange argument) that an optimal solution can always be rearranged to include it. If you cannot argue it, try DP instead.

Complexity
Usually O(n) or O(n log n) with a sort.
Common mistake
Trusting a greedy that works on the examples without a proof; coin change with arbitrary denominations is the classic counterexample.

Practice problems (11)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Greedy”).

Search and dynamic programming

Try every option (backtracking) or remember the answers to overlapping subproblems (DP).

Backtracking

When to use it: Build candidates step by step, recurse, and undo the choice; prune branches that cannot succeed.

Signals in the problem

  • "All subsets / permutations / combinations"
  • "N-Queens", "word search", "sudoku"
  • Input size is small (n ≤ 20 or so)

Core idea

Build a candidate one choice at a time, recurse, then undo the choice. Prune early: stop when the partial candidate already breaks a rule or cannot reach the target.

Template (Python)

def bt(start, path):
    res.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        bt(i + 1, path)
        path.pop()
Complexity
Exponential in the worst case (2ⁿ subsets, n! permutations); pruning is what makes it pass.
Common mistake
Appending the mutable path list itself to the results instead of a copy.

Practice problems (11)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Backtracking”).

1D Dynamic Programming

When to use it: Define dp[i] from a few earlier states; often reducible to O(1) extra space.

Signals in the problem

  • "Number of ways", "minimum cost", "maximum value" along a sequence
  • The choice at i depends only on a few earlier positions
  • House Robber, Climbing Stairs, Coin Change, LIS

Core idea

Define dp[i] in one sentence ("the best answer using the first i items"), write the recurrence from earlier states, set the base cases, and fill left to right. If dp[i] only reads dp[i-1] and dp[i-2], keep two variables.

Template (Python)

dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
    dp[i] = best(dp[i - 1] + ..., dp[i - 2] + ...)
return dp[n]
Complexity
O(n) or O(n·k) time; O(n) space, often O(1).
Common mistake
Starting to code before the state definition is precise; most wrong DP comes from an ambiguous dp[i].

Practice problems (22)

10 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “1D Dynamic Programming”).

2D Dynamic Programming

When to use it: dp[i][j] over two indices (two strings or a grid), filled row by row.

Signals in the problem

  • Two strings (edit distance, LCS) or a grid (unique paths)
  • "Interleaving", "distinct subsequences", "regex / wildcard matching"
  • Knapsack-style: items × capacity

Core idea

dp[i][j] describes prefixes of both inputs (or a grid cell). Fill row by row so every dependency is ready, and compress to one row when a cell only reads the previous row.

Complexity
O(m·n) time; O(m·n) space, often O(n).
Common mistake
Off-by-one between string indices and dp indices; using dp sized (m + 1) × (n + 1) with an empty-prefix row avoids most of it.

Practice problems (18)

6 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “2D Dynamic Programming”).

Bitmask DP

When to use it: When n is small (about 20 or less), let a bitmask stand for the set of used items and memoise dp[mask] over subsets.

Signals in the problem

  • n is tiny (≤ 20) but you must choose subsets or orders
  • "Visit every node" (travelling salesman)
  • "Partition into k equal subsets"

Core idea

Represent the set of used items as the bits of an integer and memoise dp[mask] (or dp[mask][last]). Transitions add one unused item by setting its bit.

Complexity
O(2ⁿ · n) or O(2ⁿ · n²).
Common mistake
Applying it when n is 30 or more; 2³⁰ states will not fit in time or memory.

Bits, maths and design

Smaller families that still show up in every interview loop.

Bit Manipulation

When to use it: XOR cancels pairs, n & (n - 1) drops the lowest set bit, shifts walk the bits.

Signals in the problem

  • "Single number" (every other element appears twice)
  • "Count bits", "reverse bits", "power of two"
  • Add without + or -

Core idea

XOR cancels equal pairs, x & (x - 1) clears the lowest set bit, x & -x isolates it, and shifts walk the bits. Think about one bit position at a time.

Complexity
O(n) or O(number of bits).
Common mistake
Language integer width: Python integers are unbounded, so mask with 0xFFFFFFFF when a problem assumes 32-bit overflow.

Practice problems (9)

Track your progress on Blind 75, LeetCode 150 (filter by “Bit Manipulation”).

Math

When to use it: Look for the arithmetic shortcut: digit-by-digit carries, fast exponentiation, or counting factors instead of brute force.

Signals in the problem

  • Digits, carries, powers, primes, gcd
  • "Pow(x, n)", "sqrt(x)", "factorial trailing zeroes"

Core idea

Look for the arithmetic identity that removes the brute force: fast exponentiation by squaring, counting factors of 5, digit-by-digit addition with a carry, or binary search on the answer for roots.

Complexity
Often O(log n).
Common mistake
Overflow and negative edge cases (n = INT_MIN in Pow(x, n)).

Design

When to use it: Pick a representation and its invariants first, then implement each operation against them.

Signals in the problem

  • "Implement a class with these operations"
  • Each operation has a required time bound (LRU cache: O(1) get and put)

Core idea

Write down the invariants first, then pick structures that make every operation meet its bound together. LRU cache is a hash map for lookup plus a doubly linked list for recency.

Complexity
Whatever each operation requires, usually O(1) or O(log n).
Common mistake
Optimising one operation and quietly making another O(n).

Practice problems (4)

Track your progress on Blind 75, LeetCode 150, DSA Sheet (filter by “Design”).

Frequently asked questions

How many DSA patterns do I need for coding interviews?

Around 15 patterns cover most interview questions: hashing, two pointers, sliding window, prefix sums, binary search, stacks, linked lists, tree DFS and BFS, graph BFS/DFS, topological sort, union-find, heaps, intervals, backtracking and 1D/2D dynamic programming. This guide lists 29 so that less common ones (monotonic stack, trie, bitmask DP, shortest path) are covered too.

In what order should I learn the patterns?

Follow the sections on this page from top to bottom: arrays and strings first, then stacks and linked lists, trees, graphs, heaps and intervals, and finally backtracking and dynamic programming. Each section builds on the previous one, and DP is easiest once recursion on trees feels natural.

What is the difference between sliding window and two pointers?

Both use two indices. Two pointers usually start at opposite ends of a sorted array and move toward each other to find a pair. A sliding window keeps both indices moving in the same direction and maintains state about the contiguous range between them, such as character counts or a running sum.

Is Blind 75 or LeetCode 150 enough to learn the patterns?

Blind 75 touches almost every core pattern once or twice, which is enough to recognise them. LeetCode 150 gives more repetitions per pattern. Use the pattern filter on either sheet to practise one pattern at a time until you can recognise it from the problem statement alone.

Practise the patterns

Every problem on these sheets is tagged with its pattern, with a filter, hints and free progress tracking.