DSA patterns
The handful of ideas behind most complexity improvements. Each page has the clues to spot it, a template and the traps.
Two Pointers
Walk two indices through the data so nothing is scanned twice.
O(n) after sorting
Sliding Window
Grow and shrink a contiguous range while keeping a running summary.
O(n)
Binary Search
Halve the search space using a monotone yes/no question.
O(log n) × cost of check
Prefix Sum
Precompute running totals so any range sum is a subtraction.
O(n)
HashMap / Frequency Map
Trade memory for O(1) average lookups.
O(n) average
Kadane's Algorithm
Best subarray ending here is either extend or restart.
O(n)
Monotonic Stack
Keep candidates in order so each element resolves its answer once.
O(n)
Dynamic Programming
Solve each distinct subproblem once and reuse it.
O(states × transition)
Divide and Conquer
Split, solve halves independently, combine.
O(n log n) for the classic 2-way split
DFS / BFS
Visit every node and edge once with a visited set.
O(V + E)
Backtracking
Build a candidate step by step and undo when it fails.
O(2ⁿ) to O(n!)
Heap / Priority Queue
Get the smallest or largest item in O(log n).
O(n log k)
Sorting
Pay O(n log n) once to make later steps linear or logarithmic.
O(n log n)