Mastering DSA
Through Patterns

Prune half the search space at every step.

Turn O(n²) subarray loops into O(n) with a moving window.

Eliminate half the search space every step.

Precompute prefix sums. Any range query becomes O(1).

One element + its complement. HashMap stores what you've seen. O(n) beats O(n²).

Rotate with 3 reverses. Mark visited in-place. Rearrange with index encoding.

Add delta to range [l,r] in O(1). Prefix sum to recover. Sweep line in 1D.

Count how many times each element contributes to the answer. Reverse the summation.

When you can check "is X achievable?" in O(f(n)), find optimal X in O(f(n) log range).

Next permutation, cycle decomposition, inversions, k-th permutation in O(n).

Can we split a string into valid words? DP with trie or set lookup.

SCS(s,t) = |s| + |t| - LCS(s,t). Find minimum string containing both as subsequences.

Max subarray sum in O(n). Circular variant, k disjoint subarrays, submatrix.

3Sum, 4Sum, remove duplicates, partition. Multiple pointer coordination.

Place each number at its correct index. Find missing/duplicate in O(n) O(1).

Rotate by k, search in rotated array, circular queue/buffer problems.

Find next/previous permutation in-place. Kth permutation, all permutations in order.

Dummy node. Slow/fast pointers. Reverse in-place.

Segment tree for range queries. Fenwick for prefix sums. O(log n) both.

Precompute powers of 2. Answer range min/max in O(1).

Range update in O(log n). Defer the work until you actually need it.

Floyd's tortoise and hare. O(n) time, O(1) space. Detects AND finds the cycle.

Preorder[0] = root. Inorder splits left/right. Find the split, recurse.

Find common ancestor of two nodes. Binary lifting O(n log n). Euler tour + RMQ O(n).

Heavy child inherits parent's data. Light children merged small-to-large. O(n log n).

Diameter via two BFS. Rerooting DP for all-root path queries. Longest path in O(n).

Answer all LCA queries in O(n + q) using Union-Find. Process queries offline.

Two trees are isomorphic iff they have the same canonical form. AHU in O(n log n).

Undo union operations. Offline dynamic connectivity with O(n log²n).

Jump 2^k ancestors in O(log n). LCA, kth ancestor, path queries on trees.

Point updates and range queries in O(log n). Build, query, update.

Root-to-leaf paths, path sums, max path through any nodes.

DFS without recursion. Explicit stack for inorder, preorder, postorder, Morris.

BST insert, delete, validate, floor/ceiling, kth element, convert to/from sorted.

Reverse full list, reverse k-groups, reverse between positions, copy with random.

BFS tree traversals: zigzag, right side view, level averages, cousins.

DP on trees with arbitrary number of children. Subtree properties, rerooting.

O(log n) access to the min or max. Always.

Fast prefix lookup. One character per level.

Next greater element in O(n). Sliding window max in O(n).

Trading time for space. One pass with a map beats two nested loops.

LIFO for matching/nesting. FIFO for BFS/order. Deque for sliding extremes.

Count pairs, subarrays, paths. Always ask: what structure enables efficient counting?

QuickSelect for O(n), heap for O(n log k), binary search for implicit structures.

Sliding window max/min in O(1). Deque keeps candidates in sorted order.

Balance a max-heap and min-heap to maintain median in O(log n).

Stack for matching. Count valid sequences. DP for generation. Min removals.

O(1) average via "charge" analysis. Two stacks, stack with min, queue from stacks.

Stack-based evaluation. Shunting-Yard for precedence. Recursive descent parser.

Binary trie on bit representation. Find max XOR pair in O(n log MAX).

Merge k sorted structures with a min-heap. Find smallest range, kth smallest.

Overlapping subproblems + optimal substructure = DP.

Try every option. Undo. Move on.

Make the locally optimal choice. Hope it's globally optimal.

Dijkstra for non-negative weights. Bellman-Ford for negatives. Floyd for all pairs.

Subsets as integers. 2^n states where n ≤ 20.

Split. Solve each half. Merge. Repeat until trivial.

Iterate backwards for 0/1. Forwards for unbounded. Know the difference.

Tarjan finds everything: SCCs, bridges, articulation points — one DFS.

2-colorable = bipartite. BFS/DFS detects it. Matching pairs them up optimally.

Map large values to small ranks. Enables Fenwick/SegTree on value-based problems.

Order nodes so all edges point forward. BFS (Kahn's) or DFS post-order.

Connect all nodes with minimum total edge weight. Kruskal or Prim.

Max flow = min cut. Dinic's runs in O(V²E). Models matching, assignment, feasibility.

Split problem in half. Enumerate each half independently. Combine in O(n log n).

Optimize DP with min/max of linear functions. Maintains a convex hull of lines.

Divide tree at centroid. Every path passes through O(log n) centroids.

Sweep a line across events. Sort by x, process events with a sorted structure.

Solve boolean formulas with 2-literal clauses in O(V+E) via SCC.

Find critical edges and vertices. DFS with low[] array. O(V+E).

Find max flow with minimum total cost. SPFA/Bellman-Ford on residual graph.

Edge has both minimum and maximum flow. Reduce to standard max-flow via supply/demand.

BFS from both source and target. Meet in the middle. Reduces O(b^d) to O(b^(d/2)).

Dijkstra guided by a heuristic. Finds optimal path faster when heuristic is good.

x_j - x_i ≤ w → edge i→j with weight w. SSSP gives feasible solution.

Every node has exactly one outgoing edge. Each component = rho (ρ) shape: tail + cycle.

Bipartite matching = max flow in O(E√V). General matching = Blossom algorithm.

Assign colors so no adjacent vertices share a color. Greedy gives ≤ Δ+1 colors.

Maintain top-K elements in streams. Heap-based selection, frequency tracking.

Tarjan's and Kosaraju's algorithms. Condense cycles into DAG of SCCs.

BFS/Dijkstra on augmented states. (node, extra_state) as graph vertices.

Activity selection, meeting rooms, interval scheduling. Sort + greedy sweep.

Build a valid answer from constraints. Greedy construction, invariant maintenance.

Prune search space early. Bound functions, symmetry breaking, feasibility checks.

BFS from multiple sources simultaneously. 0-1 BFS with deque for mixed weights.

Connected components in grids. BFS/DFS flood fill, area, perimeter, enclosure.

Shortest paths with negative edges. Detect negative cycles. SPFA optimization.

Reachability and minimum jumps. BFS, greedy, DP on jump range problems.

Connect components dynamically. Detect cycles, count components, earliest connection.

Remove k digits, largest number, reorganize string. Monotone stack for ordering.

Two-color graphs to find odd cycles. Divide into two groups satisfying constraints.

O(V³) all-pairs shortest paths. Transitive closure, detect negative cycles.

KMP, Z-algo, rolling hash — pattern matching in O(n).

KMP: O(n+m) search using failure function. Rabin-Karp: hash-based. Z-algorithm: substring in O(n).

LIS in O(n log n). LCS from DP. Every sequence has a structure.

Spiral traversal, rotation, 2D prefix sums — grids have patterns.

dp[i][j] = answer for s1[0..i-1] and s2[0..j-1]. Match or skip.

Expand from center, or DP on intervals. Two approaches cover every palindrome problem.

Compare substrings in O(1) after O(n) preprocessing. Rabin-Karp for pattern matching.

Sort all suffixes. Build LCP array. Enables O(n log n) solutions for hard string problems.

Multi-pattern string matching in O(n + m + k). KMP generalized to many patterns.

z[i] = length of longest string starting at i that matches a prefix. O(n) pattern matching.

Find all palindromic substrings in O(n). Extends each palindrome using previous results.

Compact structure for all substrings. O(n) build. All substring queries in O(n).

Build all distinct palindromic substrings in O(n). Count occurrences in O(n).

Lexicographically minimum rotation in O(n). Check rotation in O(n) via concatenation.

Every string = unique product of decreasing Lyndon words. Duval's algorithm O(n).

Build target strings via DP. Edit distance, word ladder, minimum operations.

Decode encoded strings, run-length encoding, parenthesis-based nesting.

atoi, add binary/strings, multiply strings, number to/from base.

GCD, primes, modular arithmetic — the engine behind CP.

XOR is your best friend. Masks are your toolkit.

nCr, inclusion-exclusion, Catalan numbers — count without listing.

XOR determines the winner. Grundy values generalize everything.

Cross products determine orientation. Convex hull wraps everything.

GCD, primes, modular arithmetic — the math behind the tricks.

E[X] = Σ p(outcome) × value(outcome). DP builds it up iteratively.

Find minimum of unimodal function in O(log n). Divide range into thirds.

Multiply polynomials in O(n log n). Convolution. Count pairs summing to k.

Every impartial game = Nim pile. Grundy value = mex of reachable states.

Solve x ≡ a1 (mod m1), x ≡ a2 (mod m2), ... in one shot. Extended Euclidean key.

Smallest convex polygon enclosing all points. Graham scan O(n log n). Andrew's monotone chain.

|A∪B| = |A| + |B| - |A∩B|. Generalize to n sets. Count with constraints.

C(n) counts balanced parentheses, BST shapes, polygon triangulations, and more.

n people in a circle, every k-th eliminated. Find survivor's position in O(n).

Linear sieve, Euler's totient sieve, Möbius function. Each number factored once.

Count distinct objects under symmetry. Average fixed points over group actions.

Adjacent Gray codes differ by one bit. Bit tricks: lowbit, popcount, bit pairs.

Solve XOR linear systems. Find XOR basis rank. Determine reachability by XOR.

C(n,k) mod prime p in O(log_p n). Pascal mod p has fractal structure.

Count paths on a grid with constraints. Reflection principle. Catalan structures.

Partition numbers, Bell numbers, Stirling numbers. DP on combinatorial structures.

Farthest pair, diameter, closest parallel edges in O(n) after O(n log n) hull.

DP tracking carries in arithmetic operations. Count valid assignments with constraints.

Expected number of steps in random processes. Linear system or DP on states.

Reverse digits, Roman numerals, palindrome numbers, Excel column mapping.

Count set bits, Hamming distance, Brian Kernighan's trick, DP counting bits.

Speed up any linear recurrence from O(n) to O(log n) with matrix power.

Binary search on reals. Ternary search on unimodal functions. Simulated annealing for hard optimizations.

Sort by deadline. Greedy + heap beats brute force every time.

Triangles, rectangles, circles — every shape reduces to distance + area math.

BFS on state space, majority vote, puzzle inversions — the patterns that don't fit elsewhere.

LRU, LFU, iterators — combine primitives for O(1) every operation.

Non-comparison sorts beat O(n log n). Sorting enables patterns: binary search, two pointers.

Do exactly what the problem says. Edge cases are the challenge.

Compute linear recurrences in O(k³ log n). Fibonacci in O(log n).

Random choices eliminate worst cases. Reservoir sampling, random pivot, shuffle.

Maintain sorted collections dynamically. Order statistics, rank queries, range operations.

O(1) get/put with HashMap + doubly linked list. LFU with frequency buckets.

Rotate 90°, transpose, spiral traversal, search in sorted matrix.

Shortest path → BFS. Connected components → DFS. Know which in 10 seconds.

Sort by start. Merge overlaps. Sweep with a heap. All interval problems reduce to three patterns.

Postorder + return value = tree DP. Same template solves diameter, max path, subtree counts.

Find the root. Union the sets. Near-constant time with path compression.

Count integers in [0, N] satisfying a digit property.

dp[i][j] = best answer for subproblem on range [i..j].

dp[i][j] depends on neighbors. Fill row by row.

Model transitions between states. Stock problems are the canonical example.

Top-down DP. Cache the result of each subproblem. Never recompute.

Mark visited. BFS for shortest. DFS for components. Multi-source for distances from all.

Range sum and point update in O(log n). Simpler than segment tree for prefix queries.

Decompose tree into O(log n) chains. Enables range queries on any tree path.

Flatten a tree into an array. Subtree queries become range queries.

Sort offline queries to minimize total movement. O((n+q)√n) for range queries.

Gaussian elimination on XOR. Find max XOR, k-th XOR value, XOR spanning set.

Visit every EDGE exactly once. Hierholzer's algorithm. Degree condition check.

Reduce O(n²k) DP to O(nk log n) when optimal split point is monotone.

Divide array into √n blocks. O(√n) per query/update. No preprocessing needed.

Keep all historical versions. Query any past state in O(log n). Share nodes across versions.

BST + heap priorities. Split and merge in O(log n). Dynamic order statistics.

Solve 3D partial order problems offline. Process left half, measure cross contributions.

Process 64 elements at once with uint64 bitmasks. DP optimized by 64x.

Maintain the piecewise-linear convex function via two heaps. DP in O(n log n).

Range chmin/chmax in O(n log²n). Tags break only when strictly better value exists.

Split array into groups with balanced sums. Fairness DP, multiway partition.

Count tilings column by column. State = which cells in current column are filled.

DP with "exactly k" constraint → binary search on cost penalty λ.

Count/find longest AP subsequences. State = (last, diff). Key: hash by difference.

Count subsequences with constraints. DP on choices: include or exclude each element.

At-most-k trick: exactly-k = at-most-k minus at-most-(k-1). Frequency-based windows.

O(1) rectangle sum queries. 2D range updates with difference arrays.

Sliding window DP: O(n²) → O(n). Deque maintains useful transitions.

Buy/sell with cooldown, fees, k transactions. State machine DP on market states.

Rolling array: reduce O(n²) DP space to O(n) or O(1). Fill order matters.

Minimum window substring, anagram in string, longest with K distinct chars.

DP for pattern matching. Wildcard '?' and '*', regex '.' and '*'.

Count subarrays satisfying constraints. Prefix sums, two pointers, "at most K" trick.

Minimum cuts, minimum insertions, count palindromic substrings. Interval DP.

Water trapped between heights. Two pointers, stack, 2D BFS variants.

Optimal parenthesization, burst balloons, stone merging. O(n³) interval DP.

Both players play optimally. DP for competitive game results and optimal values.

Count subarrays with target sum, equal 0s and 1s, balanced strings.