DSA Patterns Cheat Sheet: Recognise the Problem Type

Quick Answer

Most interview problems are variations on around a dozen patterns: two pointers, sliding window, fast and slow pointers, binary search, BFS and DFS, backtracking, dynamic programming, heaps for top-K, prefix sums, and hash maps for lookup. Each has a recognisable signal in the problem statement. Learning to identify the pattern from the wording is more valuable than solving many problems without noticing the repetition.

Array and String Patterns

Two pointers. Signal: a sorted array, or a problem about pairs, or reversing in place.
Use when: moving a pointer lets you safely discard possibilities.
Complexity: O(n) time, O(1) space.
Problems: two sum on sorted input, valid palindrome, container with most water, three sum, remove duplicates in place.

Sliding window. Signal: the words contiguous, consecutive, subarray or substring, combined with a longest, shortest, maximum or minimum.
Use when: the property can be updated incrementally as elements enter and leave.
Complexity: O(n) time.
Problems: maximum sum subarray of size k, longest substring without repeating characters, minimum window substring.
Trap: the sum version breaks with negative numbers — use prefix sums plus a hash map instead.

Prefix sums. Signal: many range-sum queries on an unchanging array.
Use when: you would otherwise re-sum the same ranges repeatedly.
Complexity: O(n) to build, O(1) per query.
Problems: subarray sum equals k, range sum query, product of array except self.

Hash map for lookup. Signal: "have I seen this before?", counting, or finding pairs in unsorted data.
Use when: you want to trade O(n) space for O(n) time instead of O(n squared).
Problems: two sum unsorted, group anagrams, first non-repeating character, longest consecutive sequence.

Searching and Linked List Patterns

Binary search. Signal: sorted input, or a monotonic answer space, or a required complexity of O(log n).
Use when: you can discard half the possibilities with one comparison.
Complexity: O(log n).
Problems: classic search, first and last position, search in rotated sorted array, square root.

Binary search on the answer. The version people miss. Signal: "find the minimum X such that…" where checking a candidate is easy but finding it directly is hard.
Use when: feasibility is monotonic — if X works, everything larger works.
Problems: Koko eating bananas, split array largest sum, minimum days to make bouquets.

lo, hi = min_possible, max_possible
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid       # try smaller
    else:             lo = mid + 1   # need bigger
return lo

Fast and slow pointers. Signal: a linked list with cycle detection, or finding a middle element, or O(1) space required.
Use when: two pointers moving at different speeds reveal structure.
Problems: linked list cycle, find the middle node, happy number, palindrome linked list.

In-place reversal. Signal: reverse a linked list or part of one, with O(1) space.
Problems: reverse a linked list, reverse between positions, reverse in groups of k.

Tree and Graph Patterns

DFS (recursive). Signal: explore all paths, compute something about subtrees, or check a tree property.
Use when: a node's answer depends on its children.
Complexity: O(n) time, O(h) space for the stack.
Problems: maximum depth, path sum, validate BST, lowest common ancestor, diameter.

BFS (level-order). Signal: shortest path in an unweighted graph, or anything phrased level by level.
Use when: you need the minimum number of steps, or to process by distance.
Problems: level-order traversal, minimum depth, word ladder, rotting oranges, shortest path in a grid.
Key point: BFS guarantees the shortest path only when every edge costs the same.

Topological sort. Signal: dependencies, prerequisites, ordering, or "can this be completed?"
Use when: the graph is directed and acyclic.
Problems: course schedule, alien dictionary, build order.

Union-Find. Signal: connected components, grouping, or detecting a cycle in an undirected graph.
Complexity: nearly O(1) per operation with path compression and union by rank.
Problems: number of provinces, redundant connection, accounts merge.

Trie. Signal: prefix matching, autocomplete, or many word lookups against a dictionary.
Complexity: O(m) per operation, where m is the word length.
Problems: implement a trie, word search II, longest common prefix.

Optimisation and Exhaustive Search

Dynamic programming. Signal: maximum, minimum, count of ways, or feasibility, with choices at each step and overlapping subproblems.
Method: write the brute-force recursion, identify the state, add memoization.
Sub-patterns: 1D such as climbing stairs and house robber; 0/1 knapsack such as subset sum; unbounded such as coin change; two-sequence such as edit distance and longest common subsequence; grid such as unique paths; interval such as matrix chain multiplication.

Backtracking. Signal: generate all subsets, permutations or combinations; or place items subject to constraints.
Template: choose, explore, undo.
Complexity: O(2ⁿ) for subsets, O(n!) for permutations — which is why constraints are always small.
Problems: subsets, permutations, combination sum, N-queens, sudoku solver, word search.

Greedy. Signal: an optimal choice at each step that is provably safe — often involving intervals or sorting first.
Use when: a local optimum leads to a global one. Be careful: this needs justification, and when it fails the answer is usually DP.
Problems: activity selection, jump game, gas station, non-overlapping intervals.

Heap / top-K. Signal: the words k largest, k smallest, k most frequent, or a running median.
Complexity: O(n log k), better than sorting when k is small.
Counter-intuitive rule: use a min-heap for the k largest, because you evict the weakest of your current best k.
Problems: kth largest element, top k frequent, merge k sorted lists, find median from a data stream.

How to Use This

Read the constraints first. They tell you the required complexity, which eliminates whole categories before you write anything.

n ≤ 20              → backtracking or bitmask is fine
n ≤ 1,000           → O(n²) acceptable — DP, nested loops
n ≤ 100,000         → need O(n log n) — sorting, heap, binary search
n ≤ 1,000,000       → need O(n) — hash map, two pointers, sliding window

Match the wording to the pattern. "Contiguous subarray" means sliding window. "Sorted array, find a pair" means two pointers. "Shortest path, unweighted" means BFS. "All combinations" means backtracking. "Maximum, with choices" means DP. "Top k" means a heap.

Practise by pattern, not at random. Solving thirty sliding-window problems teaches the pattern; solving thirty random problems teaches thirty problems. This is the single biggest change most people can make to how they prepare.

Say the pattern out loud in the interview. "This is asking for the longest contiguous substring with a property, so it is a sliding window" demonstrates the reasoning being assessed — often more convincingly than the final code.

When you are stuck: write the brute force first. It is a valid answer, it gets you partial credit, and the inefficiency in it usually points directly at the pattern that fixes it — repeated subproblems suggest DP, repeated scanning suggests a hash map or sliding window.

Frequently Asked Questions