Data Structures & Algorithms Cheatsheet

Pattern Cheat Table

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

How To Use This

Read the problem statement, find the phrase or input shape below, and start with the pattern in that row. The complexity column is what a correct solution should land on, so if your idea is slower than the listed target you are on the wrong pattern.

Order of operations before writing any code:

Read the constraints first. They pin the target complexity, which usually eliminates all but two or three patterns.
Find the signal phrase in the master table below.
State the approach and its complexity out loud before typing.
Handle the empty and single-element case in the first two lines.

Master Signal Table

Signal in the problem	Pattern	Typical complexity
sorted array, find a pair summing to a target	two pointers from both ends	O(n) time, O(1) space
triplets or quadruples summing to a target	sort plus inner two pointers	O(n^(k−1))
unsorted array, find a pair summing to a target	hash map complement lookup	O(n) time, O(n) space
contiguous subarray or substring, longest or shortest	sliding window	O(n)
subarray of a fixed size k	fixed sliding window	O(n)
subarray sum equals k, values may be negative	prefix sums plus a hash map	O(n)
count subarrays with exactly k distinct	at most k, minus at most k−1	O(n)
many range-sum queries, no updates	prefix sum array	O(n) build, O(1) query
many range updates, one final read	difference array	O(1) update, O(n) finalize
range queries interleaved with point updates	Fenwick tree or segment tree	O(log n) each
sliding window maximum or minimum	monotonic deque	O(n)
next greater or previous smaller element	monotonic stack	O(n)
balanced parentheses, nesting, undo the last thing	stack	O(n)
largest rectangle in a histogram, trapping rain water	monotonic stack, or two pointers	O(n)
in-place filter, dedupe, or partition keeping order	read and write pointers	O(n), O(1) space
sort 0s, 1s, and 2s in one pass	Dutch national flag, three pointers	O(n), O(1) space
sorted input and you need an index or a boundary	binary search, lower_bound template	O(log n)
first or last occurrence, insertion position, floor, ceiling	binary search boundary template	O(log n)
rotated sorted array	binary search on the sorted half	O(log n)
"minimum k such that", "minimize the maximum"	binary search on the answer	O(n log R)
huge numeric range but a cheap feasibility check	binary search on the answer	O(n log R)
kth largest or kth smallest, one query	quickselect	O(n) average
kth largest under a stream, or top k	heap of size k	O(n log k)
merge k sorted lists or arrays	min-heap of one head per list	O(N log k)
running median of a stream	two heaps, max and min	O(log n) per insert
repeatedly need the cheapest remaining option	priority queue	O(log n) per operation
middle of a linked list, cycle detection	fast and slow pointers	O(n), O(1) space
reverse a list or a sublist in place	three-pointer reversal	O(n), O(1) space
the head of a list may be removed or replaced	dummy sentinel node	O(n)
prefix queries, autocomplete, dictionary of words	trie	O(m) per word
word search in a grid against many words	trie plus DFS backtracking	O(rc · 3^L)
maximum XOR of a pair	binary trie over bits	O(32n)
sorted output from a tree, kth smallest in a BST	inorder traversal	O(n), O(h + k)
the answer at a node needs its children's answers	postorder DFS aggregation	O(n)
per-level aggregate, right-side view, minimum depth	BFS level order	O(n)
shortest path, unweighted graph or grid	BFS	O(V + E)
shortest path, non-negative weights	Dijkstra with a heap	O((V + E) log V)
shortest path, weights are 0 or 1	0-1 BFS with a deque	O(V + E)
shortest path with negative edges	Bellman-Ford	O(V · E)
shortest path with at most k hops	Bellman-Ford with a snapshot per round	O(k · E)
all-pairs shortest paths, V ≤ 400	Floyd-Warshall	O(V³)
minimum steps in a state space, moves are reversible	BFS over encoded states	O(states · moves)
count islands, flood fill, connected regions	DFS or BFS per unvisited cell	O(rc)
distance from every cell to the nearest source	multi-source BFS	O(rc)
connectivity under incremental edge additions	union-find	O(α(n)) per operation
detect a cycle in an undirected graph	union-find, or DFS with a parent check	O(V + E)
detect a cycle in a directed graph	three-color DFS, or Kahn's length check	O(V + E)
minimum spanning tree	Kruskal with union-find, or Prim with a heap	O(E log E)
group items by an equivalence relation	union-find	O(n · α(n))
prerequisites, dependencies, valid ordering	topological sort, Kahn's	O(V + E)
minimum rounds or semesters under dependencies	Kahn's, level by level	O(V + E)
longest path in a DAG	DP in topological order	O(V + E)
2-colorable, no odd cycle	BFS or DFS bipartite check	O(V + E)
"return all" subsets, permutations, or combinations	backtracking	O(2ⁿ · n), O(n! · n)
constraint satisfaction: N-Queens, Sudoku, colorings	backtracking with occupied sets	exponential with pruning
"count the number of ways"	DP	usually O(n) to O(n²)
minimum or maximum over a sequence of choices	DP	O(n) to O(n²)
take-or-skip each item toward a capacity, one copy each	0/1 knapsack, capacity descending	O(n · W)
unlimited copies of each item toward a target	unbounded knapsack, capacity ascending	O(n · W)
count combinations reaching a target	unbounded DP, items in the outer loop	O(n · W)
count permutations reaching a target	unbounded DP, target in the outer loop	O(n · W)
longest increasing subsequence	patience DP with binary search	O(n log n)
two strings compared or transformed	2D DP on prefix pairs	O(nm), O(min) space
minimum edits between two strings	edit distance DP	O(nm)
grid paths, minimum path sum, maximal square	2D grid DP, rolled to one row	O(rc), O(c) space
optimal over every split of an interval	interval DP, iterate by length	O(n³)
n ≤ 20 and you must track a visited set	bitmask DP	O(2ⁿ · n)
intervals: merge or union them	sort by start, extend a running block	O(n log n)
maximum non-overlapping intervals kept	sort by end, activity selection	O(n log n)
minimum removals to make intervals disjoint	total minus the maximum kept	O(n log n)
minimum rooms, machines, or resources at once	sort by start, min-heap of end times	O(n log n)
minimum points or arrows hitting every interval	sort by end, greedy placement	O(n log n)
can you reach the end, furthest reach so far	greedy invariant	O(n), O(1) space
a locally best choice is provably safe	greedy with an exchange argument	O(n log n)
every element appears twice except one	XOR everything	O(n), O(1) space
subsets of a small set, or a visited mask	bitmask enumeration	O(2ⁿ)
powers of two, lowest set bit, popcount	bit tricks	O(1)
GCD, LCM, modular inverse, huge exponent	number theory, Euclid and fast power	O(log n)
primes up to n, or many factorizations	sieve of Eratosthenes	O(n log log n)

Constraints To Target Complexity

The constraint is the strongest hint in the entire problem statement. Judges run roughly 10⁸ simple operations per second.

Max n	Target	Patterns that fit
≤ 10	O(n!) · O(2ⁿ · n)	full permutation backtracking
≤ 20–22	O(2ⁿ · n)	bitmask DP, subset enumeration
≤ 100	O(n³)	Floyd-Warshall, interval DP
≤ 1,000–5,000	O(n²)	2D DP, quadratic LIS, pairwise loops
≤ 10⁵–10⁶	O(n log n)	sort, heap, binary search, sweep line, patience LIS
≤ 10⁷–10⁸	O(n)	hash map, two pointers, sliding window, prefix sums, Kadane
≤ 10¹⁸	O(log n) · O(1)	binary search on the answer, math, fast exponentiation

Data Structure Selection

What you need	Structure	Cost
index by position	array or dynamic array	O(1) read, O(n) middle insert
membership, counting, grouping	hash set or hash map	O(1) average
sorted iteration, ranges, floor and ceiling	balanced BST, `TreeMap`, `std::map`	O(log n)
the smallest or largest remaining item	heap	O(log n) push and pop, O(1) peek
LIFO, undo, nesting, next greater	stack	O(1)
FIFO, level order, BFS	deque	O(1) both ends
window extremes	monotonic deque	O(1) amortized
prefix strings, autocomplete	trie	O(m) per word
connectivity under merges	union-find	O(α(n))
range query plus point update	Fenwick or segment tree	O(log n)
range query, no updates	prefix sums	O(1) query
set of ≤ 64 elements, fast set algebra	bitmask integer	O(1) per operation

Structural Rewrites

Recognizing that a problem is a different problem in disguise is often the whole solution.

Looks like	Actually is
a grid	a graph, cells are vertices and 4 or 8 neighbors are edges
a puzzle with legal moves	a graph over encoded states, solved by BFS
"minimum moves" with reversible moves	unweighted shortest path, so BFS
equal numbers of 0s and 1s	map 0 to −1 and look for a prefix sum of 0
"at most k distinct"	a sliding window with a frequency map
"exactly k"	at most k, minus at most k−1
Russian doll envelopes, chain of pairs	sort, then longest increasing subsequence
longest palindromic subsequence	LCS of the string with its reverse
partition into two equal halves	subset sum to total / 2, a 0/1 knapsack
minimum removals to de-overlap	total minus the maximum non-overlapping kept
find the duplicate in `1..n` in O(1) space	Floyd cycle detection on the index-to-value function
the longest path in a DAG	DP in topological order, linear
ratios or offsets between grouped items	weighted union-find
deletions from a connectivity structure	process the timeline in reverse so deletions become unions
"minimize the maximum" or "maximize the minimum"	binary search on the answer with a feasibility check

Wrong-Pattern Warning Signs

You reached for	It breaks when	Use instead
sliding window on sums	the array has negative values	prefix sums plus a hash map
Dijkstra	any edge weight is negative	Bellman-Ford
greedy coin change	denominations are arbitrary	DP, unbounded knapsack
greedy 0/1 knapsack by density	items cannot be split	DP, O(n · W)
a single `visited` set for a directed cycle	the graph has a diamond shape	three-color DFS
two pointers	the array is unsorted and cannot be sorted	hash map
binary search	the predicate is not monotone	linear scan or a different pattern
a hash map	you need order, ranges, or the minimum	balanced BST or heap
`list.pop(0)` as a queue	n is large, this is O(n) per call	`collections.deque`
backtracking to count	subproblems repeat	DP or memoization
negating weights for a longest path	the graph has cycles	only valid on a DAG
a rolled DP array	you must reconstruct the chosen items	keep the full table

Universal Correctness Checklist

Run this list before declaring a solution done. Most rejected submissions fail on one of these, not on the algorithm.

Empty input. Zero-length array, empty string, None root, no edges.
Single element. Many two-pointer and window solutions index a[1] implicitly.
All duplicates, and all identical values.
Already sorted, and reverse sorted. These are quicksort's and greedy's worst cases.
Negative numbers and zero. They break sum windows, product problems, and if not x guards.
Integer overflow. Use long for sums in Java and C++, and lo + (hi - lo) / 2 for midpoints.
1-indexed input. Size arrays n + 1 or subtract 1 consistently.
Disconnected graphs. Loop over every vertex as a potential traversal start.
Self-loops and parallel edges in graph input.
Recursion depth. Python raises past about 1,000 frames, so deep recursion needs an explicit stack.
Copy before recording in backtracking. out.append(path) stores a live reference.
Undo unconditionally after every recursive call, including on early returns.
Restore mutated input if the caller still needs it.
State the final complexity, time and space, and say which variable n refers to.