Algorithmic Patterns & Solving Techniques

Rotate an array in place by reversing the whole array and then reversing its two constituent segments.

Track the best subarray sum ending at the current index, resetting to zero whenever the running sum turns negative.

Precompute running sums (or products) so range queries or comparisons become O(1) instead of re-scanning.

Build fixed- or variable-length combinations by choosing the next element from a remaining candidate pool.

DFS with backtracking over a 2D grid, marking/unmarking visited cells while searching for a path matching a target.

Build the recursion tree by choosing where to make the next cut/partition point, rather than an include/exclude decision per element.

Build all orderings of a set by swapping/marking used elements at each recursive level.

Build the recursion tree by deciding, for each element in turn, whether to include it in the current subset.

Place items one row/column at a time, pruning branches immediately when a placement violates a global constraint set.

Standard binary search over a sorted array (or a local monotonic comparison) to locate a target index or boundary.

Binary search adapted to a rotated sorted array by determining which half is still sorted at each step.

Binary search over the space of possible answer values, using a feasibility check to decide which half to keep.

Count, shift, or accumulate individual bits to compute a numeric property (popcount, reversal, running totals).

Use XOR's self-cancelling property to isolate a unique or missing value among duplicates.

Split the problem into independent subproblems, solve each recursively, and combine their results.

DP where each item may be used at most once, choosing a subset that hits or approaches a target.

Handle a circular adjacency constraint by reducing to two linear DP passes that each exclude one end.

Treat every index (and gap between indices) as a palindrome center and expand outward while it still matches.

DP over a 2D grid where each cell's value depends on cells reachable by the allowed moves (down/right, etc.).

DP over subarray/substring ranges [i, j], combining results of smaller sub-ranges to solve larger ones.

A DP recurrence over a single sequence where each state depends on a small fixed window of previous states.

DP (optionally with binary search) tracking the best increasing subsequence length ending at each index.

DP where state represents game configuration (remaining piles, positions, turns) and we compute win/loss from each state assuming optimal play from both players.

DP tracking which of several explicit states (e.g. holding/not-holding stock, in/out of cooldown) you're in at each step.

2D DP over two string indices to compare, align, or count subsequences/substrings between them.

DP where taking an element forbids taking its immediate neighbor, tracking best-with/without-current at each step.

DP where each item/coin can be reused an unlimited number of times while building toward a target.

Standard BFS where each edge has equal weight, so the first time a node is reached is guaranteed shortest.

Relax edges for a limited number of rounds (bounding the number of hops/stops) rather than running unbounded Dijkstra, since the constraint makes plain Dijkstra unsound.

Priority-queue-driven shortest path on a weighted graph with non-negative edges, greedily finalizing the closest node.

Recursively (or iteratively) spread a fill from a starting cell to all connected cells matching a condition.

DFS across an explicit or implicit graph (adjacency list) to visit, clone, or reconstruct connected structure.

DFS across grid cells following adjacency (usually 4-directional), typically to explore or measure a connected region.

Build a minimum-weight tree connecting all nodes, either by growing from a frontier (Prim's) or sorting edges and using union-find (Kruskal's).

Seed the BFS queue with multiple starting nodes simultaneously so distances propagate from all sources in lockstep.

Order nodes of a DAG so every directed edge points from earlier to later, via DFS post-order or Kahn's algorithm.

Maintain disjoint sets with union and find operations to detect connectivity or cycles as edges are processed.

Maintain a single candidate and a counter, incrementing on a match and decrementing otherwise, to find a majority element in one pass with O(1) space.

Greedily track the farthest index reachable so far while scanning left to right to decide feasibility or minimum jumps.

Sort intervals by end time and greedily keep/skip each one to maximize non-overlapping selections.

Track a running [lower, upper] bound of possible values while scanning, collapsing or rejecting when the range becomes invalid.

Make a locally optimal choice while scanning once left to right, where the specific decision rule is simple enough not to warrant its own named pattern.

Scan left-to-right then right-to-left (or vice versa), each pass enforcing a local ordering constraint against the neighbor.

Use a hashmap or set purely to answer 'have I seen this before' or 'does the complement exist', not to count occurrences.

Track counts or per-key state (character tallies, bijective mappings) in a single pass with a hashmap, then compare or query those counts.

Bucket items together under a derived canonical key (e.g. sorted string) using a hashmap of lists.

Maintain a fixed-size heap to track the k largest/smallest/most-frequent elements seen so far.

Use a partition step (like quicksort) to find the kth largest/smallest element in average O(n) without fully sorting.

Balance a max-heap of the lower half against a min-heap of the upper half to maintain a running median.

Sort intervals by start time and merge or insert while adjacent intervals overlap.

A tortoise-and-hare pair of pointers moving at different speeds to detect a cycle or find a midpoint/kth-from-end node.

Use a hashmap as an old-object-to-new-object identity map to reconstruct a structure with internal cross-references (e.g. cloning a list with random pointers).

Rewire next-pointers to reverse a linked list or a sublist in place without extra storage.

Merge two or more already-sorted linked lists into one sorted list by repeatedly picking the smallest head.

Splice a linked list into separate chains by a pivot condition, then reconnect them in the required order.

Simulate elementary-school arithmetic (add/multiply) digit-by-digit with carries, because the operands exceed native integer range.

Peel off and reconstruct a number digit-by-digit to reverse it, check a property, or apply an increment.

Determine game outcome from simple parity, count-based, or mathematical invariants without full state DP (e.g., whether count is even/odd, modulo-based reasoning).

Apply a number-theoretic property (factor counting, GCD/slope reasoning) rather than a general-purpose algorithm.

Directly simulate a described traversal or transformation over a 2D matrix (spiral order, rotation, in-place zeroing).

Slide a window of constant size across the input, incrementally updating window state as it moves.

Expand and shrink a window's right/left edges based on a validity condition to find an optimal-length substring/subarray.

Maintain a stack that only ever decreases, popping elements when a larger one arrives to find next-greater relationships.

Maintain a double-ended queue of candidate indices in monotonic order to answer sliding-window max/min in O(1) amortized.

Maintain a stack that only ever increases, popping when a smaller element arrives to bound a region (e.g. largest rectangle).

Use a stack to match nested symbols or evaluate an expression by pushing/popping in the correct order.

Build an output string through several structured passes or an explicit layout algorithm, rather than one linear scan.

A single linear pass over string indices (with simple lookups/comparisons) to extract or convert a value.

Exploit the left-less-than-node-less-than-right invariant of a BST to prune search space or produce sorted output.

Use a BIT/Fenwick tree to answer prefix sum queries or range queries with point updates in O(log n) time, typically when the operation is associative and invertible.

Exploit a tree's complete (heap-shaped) structure to binary search for where the last level ends, unrelated to BST ordering.

Plain recursive depth-first traversal used to transform or visit every node, where no more specific tree pattern applies.

Find the deepest node that is an ancestor of two given nodes, via recursive search or BST-property comparison.

Build a segment tree to answer range queries (sum, min, max, etc.) or perform range updates in O(log n) time, often with lazy propagation.

Process a tree level-by-level using a queue, tracking level boundaries as needed.

Compute subtree heights bottom-up during DFS to check depth or balance conditions, often with early termination.

Carry a running value down (or aggregate a value up) a root-to-leaf or arbitrary path during DFS.

Rebuild a binary tree from two given traversal orders by using one to locate roots and the other to size subtrees.

Encode a tree into a linear representation (e.g. preorder with null markers) and decode it back into the same structure.

Recursively compare two trees (or a tree against a mirrored version of itself) node-by-node for structural/value equality.

Build a tree of characters so prefix lookups, insertions, and searches share common paths.

Sort the input first, then fix one element and use two pointers over the remainder to find combinations meeting a target.

Start pointers at both ends of a sorted or symmetric structure and move them toward each other based on a comparison.

A read/write or slow/fast pair of pointers moving the same direction through a sequence, compacting or scanning in place.