DSA Reference Guide: What, When, Where, Why, How

Organized by how topics actually build on each other, not the order requested. Each entry:
what it is → when/where to use it → why (trade-off it solves) → how it works → brute force
vs optimal.

1. Foundations

When to Why (trade- Brute

Topic What Optimal
use off) force

Need
O(1)
Fast read, Access
index
Contiguous fixed- slow O(1),
Array access, —
index storage insert/delete in insert/delete
cache-
middle O(n)
friendly
iteration

Need
O(1) Linear
O(1) avg
average Trades scan
Hashing / Key→value via hash lookup, O(n)
lookup, order/memory O(n)
HashMap function worst
frequency for speed per
(collisions)
counts, lookup
dedup

Unsorted O(n) —
Linear data, Simple, no already
Scan every element O(n)
Search one-off preprocessing optimal for
search unsorted

Subsets,
toggling
flags, Extreme O(1) per op,
Operate on binary
Bit parity, speed/memory O(2^n) for
representation —
Manipulation space- savings, less subset
(AND/OR/XOR/shift)
optimized readable enumeration
state (DP
masks)
 Array: [10][20][30][40] index→value O(1)
HashMap: key → hash(key) → bucket → value avg O(1)
Bitmask: 101101 (bit i = 1 means item i is "in")

Why hashing over array search: array needs O(n) scan unless sorted+binary search (O(log
n)); hashmap gives O(1) avg but no ordering and uses more memory.

2. Searching, Sorting, and the “Window” Family

Topic What When Brute force Optimal Space

Pre-step
O(n)
for binary
Arrange elements Bubble/selection Merge/Quick/Heap or
Sorting search, two
by order O(n²) sort O(n log n) O(log
pointers,
n)
greedy

Sorted
array, or
Halve search
“find
Binary space on
boundary” Linear scan O(n) O(log n) O(1)
Search sorted/monotonic
on
data
monotonic
predicate

Repeated
Prefix Precompute Recompute sum Build O(n), query
range-sum O(n)
Sum cumulative sums each query O(n) O(1)
queries

Contiguous
Maintain a moving subarray
Check all
Sliding subarray/substring problems O(n) (window O(1)–
subarrays O(n²)
Window with two (max sum, grows/shrinks) O(k)
or O(n³)
boundaries longest
substring)

Sorted
Two indices
array pair-
Two moving Nested loop
sum, O(n) O(1)
Pointers toward/away each O(n²)
partitioning,
other
merging

Sliding Window: [a b c d e f]
 ^-----^ shrink/grow window, never re-scan from start

Two Pointers: [1 3 5 7 9 11], target=12

L→ ←R move based on sum vs target

Why binary search needs sorted/monotonic data: the halving logic only works if “less than
target” is contiguous on one side — that’s the actual prerequisite, not “sorted array” specifically
(works on any monotonic predicate, e.g. “can we finish in X days?”).

3. Recursion & Backtracking

Brute
Topic What When Why force vs
optimal

Cleaner
code for
Each call
Function self-
Tree/graph traversal, divide & O(1) extra
calls itself similar
Recursion conquer, naturally recursive work but
on smaller problems,
structure stack
subproblem costs call-
O(depth)
stack
space

Explores
Recursion +
only valid
undo move
Generate all paths via Generate-
if it fails
permutations/combinations/subsets, pruning vs all-then-
Backtracking constraints
constraint satisfaction (N-Queens, generating filter
(DFS over
Sudoku) everything O(2ⁿ·n)
decision
then
tree)
filtering

Backtracking tree (subsets of {1,2}):

[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
choose → explore → un-choose

Why backtracking over plain recursion: plain recursion explores everything; backtracking
adds the “undo + prune” step so invalid branches die early — same asymptotic worst case, but
real-world speedup.

4. Stacks, Queues & Linear Structures

Brute
Topic What When Why Optimal
force

Matching Constant
Stack
Push/pop one end brackets, undo, time both — O(1) push/pop
(LIFO)
DFS iterative ends

Frequent O(1)
insert/delete, insert/delete Insert/delete
Linked
Nodes with pointers unknown size, (given — O(1), access
List
no random node), O(n) O(n)
access needed access

Next
O(n) — each
Greater/Smaller Avoids O(n²) O(n²)
Monotonic Stack kept element
Element, pairwise nested
Stack increasing/decreasing pushed/popped
histogram max comparison loop
once
area

Recompute
Monotonic Deque kept
Sliding window max each
Queue monotonic, supports O(n·k) O(n)
max/min window
(Deque) both-end pop
O(n·k)

Need push/pop
from both ends
Deque Double-ended queue — — O(1) both ends
(BFS+window
combos)

Always- Sort
Kth largest,
Heap sorted- each Insert/extract
Binary tree, parent ≤/ scheduling,
(Priority min/max time O(log n), peek
≥ children Dijkstra, merge
Queue) without full O(n O(1)
k lists
sort log n)

Monotonic stack (Next Greater Element), arr=[2,1,5,3]:

i=0: push 2 stack:[2]
i=1: push 1 stack:[2,1]
i=2: 5>1,5>2 → pop both, NGE(1)=5, NGE(2)=5; push 5 stack:[5]
i=3: push 3 stack:[5,3]
 → each element pushed/popped at most once = O(n)

Why monotonic structures over brute force: naive “next greater element” checks every pair
(O(n²)); the monotonic stack guarantees each element is pushed and popped exactly once, so
total work is O(n) — the trade-off is needing to reason about when to pop, which is less
intuitive.

5. Array/Sequence Patterns & Math

Brute
Topic What When Optimal
force

Track running max Check all

Kadane’s
subarray sum, reset Max subarray sum subarrays O(n)
Algorithm
if negative O(n²)/O(n³)

Meeting rooms, Compare

Merge/insert/overlap Sort + sweep O(n
Intervals merge intervals, all pairs
on (start,end) pairs log n)
calendar conflicts O(n²)

Sort events by Interval overlap

Sweep coordinate, process counts, skyline O(n²)
O(n log n)
Line left→right with problem, closest pairwise
active-set pair variants

GCD/LCM, primes Divisibility, Trial

Math & Sieve O(n log log
(Sieve of combinatorics, division
Number n) for range of
Eratosthenes), cryptography- O(√n) per
Theory primes
modular arithmetic flavored problems number

Used as a proof
Proving duplicates
If n items into m<n tool, not an
Pigeonhole must exist,
boxes, some box — algorithm — O(1)
Principle bounding search
has ≥2 reasoning
space
shortcut

Kadane's: arr = [-2,1,-3,4,-1,2,1,-5,4]

curMax: reset to arr[i] if curMax+arr[i] < arr[i]
track best seen → answer = 6 ([4,-1,2,1])

Sweep line (intervals [1,3],[2,6],[8,10]):

events: (1,+1)(2,+1)(3,-1)(6,-1)(8,+1)(10,-1)
sort by time → sweep, maintain active count
6. Graphs

6a. Traversal & Building Blocks

Topic What When Complexity

Level-by-level via Shortest path (unweighted),

BFS O(V+E)
queue level order

Go deep via Connectivity, cycle detection,

DFS O(V+E)
stack/recursion topological sort base

Tree Traversal Serialize tree, BST validation,

Visit order on trees O(n)
(pre/in/post/level) expression eval

Disjoint Set
Track connected Cycle detection (undirected),
Union Naive find
components with Kruskal’s MST, dynamic
(DSU/Union- O(n)
union+find connectivity
Find)

BFS-based topological
Kahn’s DAG ordering, detect cycles
sort using in-degree O(V+E)
Algorithm in directed graph
counting

DFS-based or
Linear order respecting Build systems, course
Topological Sort Kahn’s, both
dependencies prerequisites
O(V+E)

BFS: level 0: [A]

level 1: [B,C] queue-based, guarantees shortest hops
level 2: [D,E,F]

DFS: A→B→D (backtrack)→E (backtrack)→C→F stack/recursion-based, goes deep first

BFS vs DFS trade-off: BFS guarantees shortest path in unweighted graphs but uses more
memory (stores whole frontier); DFS uses less memory (O(depth)) but doesn’t guarantee
shortest path.

6b. Shortest Path / Spanning Tree / Connectivity

When to
Algorithm Handles Complexity vs alternative
prefer
 Single-source Default O((V+E) log Faster than
Dijkstra shortest path, weighted V) with Bellman-Ford if
non-negative shortest-path heap no negative
weights edges

Single-source,
handles Negative Slower but more
Bellman-Ford negative edges O(V·E) general than
weights, detects present Dijkstra
negative cycles

Need Worse than

distance running Dijkstra
All-pairs between V times (O(V·E
Floyd-Warshall O(V³)
shortest path every pair, log V)) for
small/medium sparse graphs,
V but simpler code

Similar to
MST, grow tree Dense O(E log V)
Prim’s Dijkstra
from a vertex graphs with heap
structurally

Sparse Prefer over

MST, sort edges
Kruskal’s graphs, edge O(E log E) Prim’s when
+ DSU
list given edges ≪ V²

Strongly
Condensation
SCC connected
graph, cycle O(V+E)
(Tarjan’s/Kosaraju’s) components in
grouping
directed graph

Binary lifting:
Naive: walk
Tree distance O(log n) per
LCA (Lowest Closest shared up
queries, query after O(n
Common Ancestor) ancestor in tree O(depth)
binary lifting log n)
per query
preprocess

Dijkstra: relax edges via min-heap, always finalize closest unvisited node
Bellman-Ford: relax ALL edges, V-1 times — slower, but tolerates negative weights
Floyd-Warshall: dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) for every k — O(V³)

Why Kruskal’s over Prim’s (or vice versa): Kruskal’s sorts edges and uses DSU — good when
graph is sparse (E close to V). Prim’s grows from a seed vertex using a heap — better for dense
graphs since it doesn’t need to sort all edges upfront.
7. Trees & Divide and Conquer

Topic What When Brute force Optimal

BST Left <

Ordered Balanced BST O(log
(Binary node < Array search
insert/search/delete, n); unbalanced worst
Search right O(n)
range queries case O(n)
Tree) invariant

Split →
Divide Merge sort, quick Often O(n log n) via
solve Solve naively
and sort, fast recurrence
subparts → O(n²)
Conquer exponentiation T(n)=2T(n/2)+O(n)
merge

O(n log n) typically

Make
(sort + scan) — but
locally Activity selection,
only correct when
Greedy optimal Huffman coding, Try-all (often
problem has greedy-
Algorithm choice, coin change DP/backtracking)
choice + optimal-
never (canonical systems)
substructure
reconsider
property

Trade-off — Greedy vs DP: greedy is faster (no exploring alternatives) but only works when
locally-optimal choices provably lead to a globally optimal solution; DP is slower but correct
even when greedy fails (e.g. 0/1 knapsack vs fractional knapsack).

8. Dynamic Programming

Concept What When

Memoization (top- Recursion + cache

Natural recursive structure, sparse state space
down) results

Tabulation Avoids recursion overhead/stack limits, dense

Iterative table fill
(bottom-up) state space

DP Variant Typical problem Brute force Optimal

House robber, climbing O(2ⁿ)

Linear DP O(n)
stairs recursion

Edit distance, LCS,

String DP O(2^min(m,n)) O(m·n)
palindrome partitioning
 0/1 knapsack, subset
Knapsack-based
sum, partition equal O(2ⁿ) O(n·W)
DP
subset

Unique paths, min path

Grid-based DP O(2^(m+n)) O(m·n)
sum

Multiple state variables Polynomial, but watch

Multidimensional Exponential in
(e.g. items + capacity + memory (often needs
DP #states
count) rolling array)

Traveling Salesman, O(n!)

Bitmask DP O(2ⁿ·n)
assignment problems permutations

Matrix chain
Interval DP multiplication, burst O(2ⁿ) O(n³) typically
balloons

Count numbers with Enumerate all

Digit DP O(digits · states)
property up to N numbers O(N)

Max independent set on Exponential

Tree/Graph DP O(n) (post-order DFS)
tree, diameter subsets

LIS: O(n log n) w/ binary

Classical DP LIS, coin change, edit O(2ⁿ) or O(n²)
search; others O(n²) or
problems distance naive
O(n·target)

DP core idea: avoid recomputation by storing subproblem answers.

fib(5) naive recursion: fib(5) calls fib(4)+fib(3); fib(4) calls fib(3)+fib(2)...
→ fib(3) computed twice, fib(2) computed 3x, exponential blowup
fib(5) memoized: each fib(k) computed once → O(n)

Why memo vs tabulation: memoization is easier to write (mirrors recursion) and only
computes states actually needed; tabulation avoids recursion-depth limits and is usually faster
in practice (no function-call overhead) but computes every state in the table even if unneeded.

9. Strings & Specialized Data Structures

Topic What When Brute force Optimal

KMP
(Knuth- Pattern matching using O(n·m)
 Morris- prefix-function to avoid Substring search naive O(n+m)
Pratt) re-scanning

String
Multiple pattern
Hashing Rolling hash to compare O(n+m)
search, substring O(n·m)
(Rabin- substrings in O(1) average
equality checks
Karp)

Search
Autocomplete, prefix O(L) per
each word
Trie Prefix tree of characters search, dictionary word (L =
O(n) per
lookup word length)
word

Array +
Fenwick Tree-encoded prefix Frequent updates + Update &
recompute
Tree sums, point update + range sum/count query O(log
O(n) per
(BIT) range query queries n)
query

Tree over array

Range min/max/sum Recompute Build O(n),
Segment segments, supports
with updates, more O(n) per query/update
Tree range query + range
flexible than BIT query O(log n)
update

Also used ~O(1)

DSU /
standalone: counting amortized
Union- (see graphs section) —
components, with
Find
Kruskal’s optimizations

Trie for {cat, car, dog}:

root
/ \
c d
a o
/ \ \
t r g
(cat)(car) (dog)

Fenwick vs Segment Tree:

Fenwick: simpler, less memory, only prefix-sum-style queries
Segment Tree: more general (min/max/gcd/custom), supports range updates w/ lazy propagation

Fenwick vs Segment Tree trade-off: BIT is simpler and faster to code/lower constant factor,
but only naturally supports associative+invertible operations (sums). Segment tree handles
arbitrary range queries (min, max, gcd) and range updates via lazy propagation, at the cost of
more code and memory.
10. Quick Decision Guide (“which tool do I reach for?”)

Signal in the problem Likely tool

Sliding window, Kadane’s, prefix

“contiguous subarray/substring”
sum

“sorted array” / “find boundary” Binary search, two pointers

“all permutations/combinations/subsets” Backtracking

“next greater/smaller element” Monotonic stack

“max/min in every window” Monotonic deque

“shortest path, unweighted” BFS

“shortest path, weighted, no negatives” Dijkstra

“shortest path, negative weights” Bellman-Ford

“all-pairs shortest path, small graph” Floyd-Warshall

Prim’s (dense) / Kruskal’s

“minimum spanning tree”
(sparse)

“connected components / cycle in undirected graph” DSU

“task ordering with dependencies” Topological sort (Kahn’s or DFS)

“count ways / min cost with choices + overlapping

DP
subproblems”

“locally optimal = globally optimal” Greedy

“frequent prefix-sum updates” Fenwick tree

“range query needing min/max/custom + updates” Segment tree

“prefix/autocomplete search” Trie

“substring search” KMP / Rabin-Karp

“n items, m<n boxes → must repeat” Pigeonhole principle

11. Complexity Cheat Sheet (best/typical case)

Class Examples Big-O

O(1) Hashmap lookup, array access, DSU find (amortized) constant

O(log n) Binary search, heap insert, BIT/segment tree ops logarithmic

O(n) Linear scan, sliding window, Kadane’s, BFS/DFS (per edge sum) linear

O(n log
Sorting, Dijkstra (heap), merge sort, Kruskal’s linearithmic
n)

Naive pairwise comparison, simple DP tables, Floyd-Warshall is

O(n²) quadratic/cubic
O(V³)

O(2ⁿ) Brute-force subsets, naive recursion without memoization exponential

O(n!) Brute-force permutations (TSP without DP) factorial

General pattern across this whole list: almost every “optimal” technique above is a brute-
force approach (O(n²), O(2ⁿ), O(n!)) plus one structural insight — sorting, a hash table, a
monotonic invariant, memoization, or a tree-shaped index — that eliminates redundant work.
When stuck, ask: “what am I recomputing that I could cache, presort, or maintain
incrementally?”