DSA Patterns

Problem-Solving Patterns

The feature works on the staging dump: n = 2 × 10³. On production traffic at n = 2 × 10⁵ the same nested pair scan times out. Brute force was correct; the time budget was not. Patterns are how you name the next move after you see the .

A is a reusable scan, state, or search shape with a clear . The catalog below compresses experience so you go from “no idea” to “this smells like a ” in under a minute.

Decision journey

Restate constraints

n, sorted?, duplicates?, all answers vs one?

Brute first

State the obvious idea and its cost out loud.

What work repeats or what lookup is missing?

Match a pattern

Write one invariant sentence, then code.

What actually happens

Naive idea: try every pair, every substring, or every subset. Correctness is easy to see, and it often passes tiny tests.

Break: at n = 10⁵, O(n²) pair checks are about 10¹⁰ operations. At n = 40, naive subset search is already past a one-second budget. The failure timeline is “sample green → hidden TLE.”

Better idea: name the bottleneck, then match a pattern whose invariant removes the repeated work. Unsorted two-sum needs a hash map. Contiguous budgets need a window. Thresholds with need binary search on the answer. Overlapping work with needs DP.

What must never become false

Before you commit to a pattern, you must be able to state its in one sentence. If the claim is fuzzy, the pattern choice is still wrong (or incomplete).

How to choose a pattern

1. Walk the decision tree top-down. Take the first question that clearly fits. Prefer the tighter invariant when two patterns both seem plausible.

2. Do not force a favorite tool. Two pointers on unsorted data without sorting or hashing, or greedy without a proof, are common false starts.

3. Mix when needed. Window + hash, Dijkstra = BFS + heap, prefix hash for subarray sum = k are normal combinations.

Quantitative check

Unsorted two-sum at n = 10⁵: all pairs ≈ 5 × 10⁹ comparisons. One hash-map pass is ≈ 10⁵ lookups. That is the difference between TLE and a comfortable linear solution under a ~10⁸ ops/sec budget.

A repeatable solve workflow

Restate constraints: n size, sorted?, duplicates?, negatives?, directed graph?, need all solutions vs one / optimal only.
Brute force first: enumerate or simulate naively. State its complexity out loud.
Name the bottleneck: nested scans? repeated subproblems? missing order? no pruning?
Match a pattern: pick from the catalog below; write a one-sentence invariant.
Implement + edge cases: empty, single, duplicates, overflow, recursion depth.
Walk an example: dry-run 5–8 elements before claiming done.

30-second decision tree

Scan top → bottom. Take the first question that clearly fits; write one invariant, then code. If two patterns fit, prefer the one with the tighter invariant.

01
Sorted input, or can I sort cheaply for pairs / partitions?
palindrome, in-place swap, 2-sum on sorted
→ two pointers
02
Answer is a contiguous subarray/substring with a running constraint?
max length, min covering window, ≤ k distinct
→ sliding window
03
Need “have I seen X?”, complements, or counts in O(1)?
unsorted 2-sum, anagrams, frequency maps
→ hash map / set
04
Many range sums, or offline range updates on a static array?
subarray sum = k (with prefix hash)
→ prefix / difference array
05
Feasibility is monotone in a threshold (“min the max…”)?
only if mid valid ⇒ mid±1 stays monotone
→ binary search on answer
06
Next greater/smaller, matching brackets, or undo-last?
NGE, valid parentheses, histogram rectangle
→ stack / monotonic stack
07
Graph/grid: connectivity, components, or shortest unweighted path?
islands, topo sort, clone graph; BFS for layers
→ BFS / DFS
08
Repeated min/max, top-K, or merge K streams?
kth largest, merge k lists, Dijkstra PQ
→ heap
09
Enumerate all valid configs (perms, subsets, constraint search)?
N-Queens, subsets, word search: prune hard
→ backtracking
10
Local choice is provably safe (sort by key / exchange)?
interval scheduling, Huffman; else suspect DP
→ greedy
11
Overlapping subproblems + optimal / counting substructure?
knapsack, LIS, edit distance, house robber
→ DP

No match? Re-check constraints (sorted? negatives? need all solutions?). Mix patterns when needed (window + hash, Dijkstra = BFS + heap).

Pattern catalog

Two pointers

O(n) scan (often after O(n log n) sort)

Signal: Sorted array, palindrome, in-place partition, pair/triplet sums

Example: Two-sum on a sorted array; reverse string in place; remove duplicates.

Trap: Using two pointers on unsorted data without sorting or hashing first.

Sliding window

O(n) with a hash map / counters

Signal: Contiguous subarray/substring with a budget (sum, distinct count, max length)

Example: Longest substring with ≤ k distinct chars; min window covering a target.

Trap: Forgetting to shrink the left edge when the window becomes invalid.

Hash map / set

O(n) time, O(n) space

Signal: Need O(1) average lookup, counts, “seen before?”, index of first occurrence

Example: Two-sum (unsorted); anagram checks; frequency maps.

Trap: Assuming order; colliding on mutable keys; forgetting worst-case hashing.

Binary search / search on answer

O(log n) or O(n log U)

Signal: Sorted data, or “minimize the maximum …” with monotone feasibility

Example: First True in a boolean array; allocate books / split array largest sum.

Trap: Off-by-one on mid; searching when feasibility is not monotone.

Prefix / difference array

O(n + q)

Signal: Many range sums or offline range updates on a static array

Example: Subarray sum equals k (with prefix hash); range add then final array.

Trap: 1-based vs 0-based indexing bugs on prefix[i] - prefix[j].

Stack / monotonic stack

O(n) amortized

Signal: Matching brackets, next greater/smaller, histogram, parse with undo-last

Example: Valid parentheses; daily temperatures; largest rectangle in histogram.

Trap: Forgetting to pop while maintaining the monotone invariant.

BFS / DFS (graph)

O(V + E)

Signal: Connectivity, shortest unweighted path, cycles, topological order, components

Example: Number of islands; course schedule (topo); clone graph.

Trap: Missing visited set → infinite loops; using DFS when BFS layers are required.

Heap / top-K

O(n log k) often

Signal: Repeated min/max, merge K lists, streaming top-K

Example: Kth largest; merge k sorted lists; Dijkstra with priority queue.

Trap: Building a full sort (n log n) when a size-k heap is enough.

Greedy

Often O(n log n) from sorting

Signal: Local choice is provably safe (exchange argument / sorted by key)

Example: Interval scheduling; Huffman; jump game (when greedy works).

Trap: Greedy without a proof: many “looks greedy” problems need DP.

Dynamic programming

Poly in number of states × transitions

Signal: Overlapping subproblems + optimal substructure; small state dimension

Example: Knapsack; LIS; edit distance; house robber.

Trap: Huge state space; missing base cases; confusing DP with plain recursion.

Backtracking

Exponential (prune hard)

Signal: Enumerate permutations/combinations, constraint satisfaction, undo choices

Example: N-Queens; subsets; word search on a grid.

Trap: Forgetting to undo (backtrack) mutations; no pruning → TLE.

Quick reference table

Pattern	Often appears when …	Target
Two pointers	Sorted array, palindrome, in-place partition, pair/triplet sums	O(n) scan (often after O(n log n) sort)
Sliding window	Contiguous subarray/substring with a budget (sum, distinct count, max length)	O(n) with a hash map / counters
Hash map / set	Need O(1) average lookup, counts, “seen before?”, index of first occurrence	O(n) time, O(n) space
Binary search / search on answer	Sorted data, or “minimize the maximum …” with monotone feasibility	O(log n) or O(n log U)
Prefix / difference array	Many range sums or offline range updates on a static array	O(n + q)
Stack / monotonic stack	Matching brackets, next greater/smaller, histogram, parse with undo-last	O(n) amortized
BFS / DFS (graph)	Connectivity, shortest unweighted path, cycles, topological order, components	O(V + E)
Heap / top-K	Repeated min/max, merge K lists, streaming top-K	O(n log k) often
Greedy	Local choice is provably safe (exchange argument / sorted by key)	Often O(n log n) from sorting
Dynamic programming	Overlapping subproblems + optimal substructure; small state dimension	Poly in number of states × transitions
Backtracking	Enumerate permutations/combinations, constraint satisfaction, undo choices	Exponential (prune hard)

Tiny worked sketch: two-sum (unsorted)

Brute force: try all pairs → O(n²). Bottleneck: repeated “is target − x in the list?”. Pattern: hash map of value → index while scanning once.

python

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return None
# Invariant: seen holds all values before i.
# Time O(n), space O(n).

How to explain your plan

Do say

“Brute force is O(n²); the nested scan is the bottleneck.”
“I’ll keep a window [L, R] with the count of distinct chars.”
“Feasibility is monotone in mid, so I’ll binary-search the answer.”
“Edge cases: empty, single node, cycles, duplicates.”

Avoid

Coding silently for 10 minutes with no plan.
Claiming O(n) without defining n.
Forcing a pattern that has no clear invariant.
Skipping tests after “it looks right.”

Complexity ladder (pick the next step)

From	To	Typical move
O(n²) pairs	O(n)	Hash map or two pointers (if sorted)
O(n²) substrings	O(n)	Sliding window + counters
O(n!) perms	pruned search / DP	Backtracking with pruning, or state compression DP
O(2ⁿ) recursion	O(n · states)	Memoization / bottom-up DP
Full sort n log n	n log k	Heap of size k for top-K

Deep dives in this course

Mechanics and code live in dedicated notes. Pair patterns when problems mix ideas (Dijkstra = BFS + heap; anagram sliding window = window + hash map).

Mindset

Patterns are not a forced checklist. They are compression of common invariants. If your chosen pattern does not give a clear invariant in one sentence, keep looking: maybe you need a different abstraction or a combination of two tools.

Exercises

For “longest substring with at most k distinct characters,” which decision-tree question fires first? State the window in one sentence.
n = 10⁵ unsorted integers, find any pair summing to target. Compare pair-scan vs hash map operation counts. When would sorting + two pointers still win on memory?
Give a problem that looks greedy but needs DP. Which missing proof (exchange / stay-ahead) would have warned you?

Primary sources

Skiena, The Algorithm Design Manual: war stories and the “algorithm catalog” mindset.
Cormen et al., Introduction to Algorithms (CLRS): dynamic programming and greedy chapters for structure tests.
LeetCode Explore / classic problem statements for two-sum, sliding window, and binary search on answer.

Takeaway

Clarify → brute → bottleneck → pattern → code → tests. Match signals before coding, and refuse any pattern whose invariant you cannot state in one sentence.