Which pattern does this problem want?

input size hint: n up to 1e5–1e6

• constraints
• complexity

Target O(n) or O(n log n) — a nested loop won't pass

Constraints tell you the intended complexity. 1e5 ⇒ n log n; 1e9 ⇒ O(log n) or O(1).

“in place”, “O(1) extra space”, “modify the array itself”

• array
• in-place
• space

Write index / in-place array mechanics

A slow write index lags the scan and only advances on elements you keep — dedup, compaction and partitioning are all this one idiom.

“rotate the array by k”

• array
• in-place
• rotation

Three reversals

Reverse the whole array, then the first k, then the rest — O(n) time and no second array.

lowercase letters only / a fixed small alphabet

• string
• counting

Fixed-size frequency array, not a map

A [26]int is stack-allocated, needs no hashing, and is comparable with == so two tables compare in one expression.

“anagram”, “seen before”, “count of each”, “group by”

• string
• count
• dedupe

Hash map / frequency map

Any time identity or multiplicity matters and order doesn't, a map turns O(n²) scans into O(n).

“has this been visited?”, need a set of things

• set
• membership

Hash set (map[T]struct{})

O(1) membership. In Go there's no set type — use map[T]struct{}.

sorted array + find a pair / triplet / condition

• array
• sorted
• pair

Two pointers

Sortedness lets one pointer move in from each end and discard half the space per step.

“in-place”, “remove duplicates”, “move zeroes”, partition an array

• array
• in-place

Two pointers (fast/slow write index)

A slow write pointer + fast read pointer compacts the array with O(1) extra space.

“contiguous subarray” / “substring” + best or count

• array
• string
• optimization

Sliding window

Contiguous + an optimum means you can grow/shrink a window instead of re-scanning every range.

“subarray sum equals k” (not necessarily positive)

• array
• hashmap
• count

Prefix sum + hash map

Window breaks with negatives; prefixSum[j]-prefixSum[i]=k, so store seen prefix sums in a map.

“range sum / range update”, many queries over an array

• array
• range-query

Prefix sums / difference array (or a Fenwick tree)

Precompute once, answer each range query in O(1). Difference arrays do the same for range updates.

search in a sorted thing / “minimum X such that feasible(X)”

• sorted
• monotonic
• optimization

Binary search (on array or on the answer)

Monotonic predicate ⇒ you can halve the search space. 'Answer' problems are binary search in disguise.

“matching”, “nesting”, “most recent unmatched”, parentheses

• parsing
• nesting

Stack

LIFO = 'the thing I care about is the most recent one I haven't resolved'.

“next greater / smaller element”, “largest rectangle”, spans

• array
• next-greater

Monotonic stack

Keep the stack sorted; pop while the new element dominates — each element pushed/popped once ⇒ O(n).

“reverse a list”, “detect a cycle”, “nth from end”, “reorder list”

• linked-list
• pointers

Linked list pointer manipulation (dummy head, fast/slow)

No indexing — everything is done by re-wiring `next` pointers with 2–3 cursors.

“all permutations”, “all subsets”, “generate every valid …”

• recursion
• enumeration

Recursion / backtracking

Enumerating every combination is a decision per element, which is a recursive tree — choose, recurse, un-choose.

the problem is defined in terms of itself — a tree, nested structure, or “solve the smaller case”

• recursion
• tree
• divide-and-conquer

Recursion (define the base case first)

When the shape is self-similar, the code is: base case, recurse on the parts, combine. Getting the base case wrong is the usual bug, not the recursion.

“generate all”, “all combinations/permutations/subsets”, N-Queens, Sudoku

• enumerate
• constraints

Backtracking

Build a candidate incrementally, abandon (‘prune’) partial candidates that can't succeed.

“tree”, “hierarchy”, “traverse”, “depth”, “ancestor”

• tree
• recursion

Tree DFS/BFS recursion

Most tree problems are 'do something at each node + combine children's answers'.

“BST”, “kth smallest in a tree”, “range of values in a tree”

• tree
• sorted

In-order traversal / BST invariant

In-order visits a BST in sorted order — kth smallest, validation, closest value all follow.

“top k”, “k largest/smallest”, “k closest”, streaming median

• k
• streaming
• selection

Heap / priority queue

You only need the boundary element, not a full sort — a size-k heap is O(n log k).

“merge k sorted lists/arrays”

• k
• merge
• sorted

Min-heap of heads

Always emit the global minimum among the k current fronts — that's exactly a min-heap.

“prefix”, “autocomplete”, “words starting with”, dictionary of strings

• string
• prefix
• dictionary

Trie

Shared prefixes are stored once; lookup/insert is O(len), independent of dictionary size.

“shortest path” in an unweighted grid/graph, “fewest steps”

• graph
• grid
• shortest-path

BFS

BFS explores in layers, so the first time you reach a node is via a shortest path.

“all paths”, “connected components”, “flood fill”, cycle detection

• graph
• grid
• components

DFS (recursion or explicit stack)

DFS naturally follows one path to exhaustion — ideal for reachability and enumeration.

“shortest path” with non-negative weights

• graph
• weighted
• shortest-path

Dijkstra (min-heap)

Greedily settle the closest unsettled node; a priority queue gives you that node in O(log n).

“course schedule”, “build order”, “dependencies”, DAG ordering

• graph
• dag
• ordering

Topological sort (Kahn's BFS or DFS)

A valid order exists iff the dependency graph is acyclic; toposort produces one or detects a cycle.

“are these two in the same group?”, connectivity queries, Kruskal

• graph
• connectivity

Union-Find (disjoint set)

Near-O(1) union and find with path compression — beats re-running BFS per query.

“can you split / schedule / assign to hit a target”, feels greedy but tricky

• scheduling
• optimization

Greedy — then prove it, or fall back to DP

Greedy is right only when a local best is never regretted (exchange argument). If it can be, use DP.

“number of ways”, “min/max cost to…”, “can you reach…”, overlapping choices

• count
• optimization
• sequence

Dynamic programming

Optimal substructure + the same subproblem recurring ⇒ memoize or fill a table.

“longest increasing subsequence”, edit distance, “X and Y strings/arrays”

• string
• sequence
• 2d-dp

DP over indices (often 2-D)

State = (position in A, position in B); transitions compare/skip one element.

“merge overlapping intervals”, “can attend all meetings”, calendar

• intervals
• sorting
• sweep

Sort by start, sweep

After sorting, overlap is a local check against the last kept interval / a running end time.

n ≤ ~20, need exact answer, subsets of items

• bitmask
• small-n
• subset

Bitmask (subset enumeration / bitmask DP)

2^20 ≈ 1e6 states fit; an int is a fast, hashable set of up to 64 items.

“without extra space”, “find the single number”, XOR-friendly

• bits
• space

Bit tricks (XOR, low bit, masks)

XOR cancels pairs; a^a=0. Many O(1)-space tricks come from bit identities.