Watch the mechanism

When values are 1..n, each value has a home index. Swap until everything is home, then whatever is misplaced is your answer.

The prefix table records how much of the pattern is reusable after a mismatch, so the text pointer never moves backwards.

Partition around a pivot, then recurse only into the side that contains the rank you want.

Walk the array swapping any pair that is out of order. After pass k the k largest values have bubbled to the end.

Repeatedly find the smallest remaining value and swap it into the next position. Always n squared comparisons, but at most n swaps.

Grow a sorted prefix by lifting each new element out and shifting bigger values right until it drops into place.

Split the array in half, sort each half recursively, then merge the two sorted runs in linear time.

Pick a pivot, partition everything smaller to its left and larger to its right, then recurse on both sides.

Tally how many times each key appears, turn the tally into positions with a prefix sum, then place elements from the back to stay stable.

Halve the search space each step by comparing the target to the midpoint of a sorted range.

Koko eating bananas. The array is not sorted, but feasibility is monotonic in the eating speed, so binary search the speed instead of the array.

On a sorted array, one pointer at each end. Move the pointer that can only push the sum in the direction you need.

Longest subarray whose sum stays within a limit. Grow on the right, shrink on the left whenever the window breaks the rule.

A deque of indices kept in decreasing value order. The front is always the maximum of the current window.

Count subarrays summing to k. Every subarray sum is a difference of two prefix sums, so a map of seen prefixes does it in one pass.

Three pointers, one flipped link per step. The whole trick is saving the next node before you overwrite it.

One pointer moves twice as fast. If there is a loop they must meet inside it, and resetting one to the head finds where the loop starts.

A dummy head removes every empty-list edge case. Then just attach whichever front node is smaller.

Keep a stack of indices with decreasing values. Every new element resolves the answer for everything it dominates.

One depth first walk, three visit times. Pre-order records on the way in, in-order between the children, post-order on the way out.

Process the queue one full level at a time by snapshotting its length before the inner loop.

Left is smaller, right is larger. That one rule turns search, insert and delete into a single walk down the tree.

Checking a node against its direct children is not enough. Pass an allowed range down the tree and narrow it at each step.

Build a max heap in place, then repeatedly swap the root to the end and sift the new root down.

A complete binary tree stored in an array. Push sifts the new value up, pop moves the last value to the root and sifts it down.

Explore in rings of increasing distance. The first time BFS reaches a node, it arrived by a shortest path.

Follow one branch as deep as it goes, then backtrack. Each fresh launch from an unvisited node is one connected component.

Always finalise the closest unfinished node, then relax its outgoing edges. Requires non-negative weights.

Repeatedly take any node with no remaining prerequisites. If you cannot empty the graph, there is a cycle.

Each set keeps one representative. Union links two roots, find walks up to the root and flattens the path behind it.

Sort every edge by weight and take it whenever it joins two different components. Union-Find makes the cycle check cheap.

A grid is a graph where each cell touches its four neighbours. Sink each island as you walk it and count how many walks you start.

At every index decide whether to extend the previous best subarray or start fresh from here.

Watch the naive Fibonacci recursion explode, then watch a cache collapse it. This is the moment dynamic programming makes sense.

Each item is taken or skipped under a shared capacity. The table row i, column w is the best value using the first i items within weight w.

Compare the last characters of two prefixes. A match extends the diagonal, a mismatch takes the better of dropping one character from either side.

Fewest coins for each amount from zero upward. Each cell asks: which coin was the last one I used?

Keep the smallest possible tail for each achievable length. Binary search replaces the inner loop and drops the cost to n log n.

Movement is restricted to right and down, which fixes the dependency order: every cell needs the one above and the one to its left.

Cheapest way to turn one string into another using insert, delete and replace. Each cell picks the cheapest of three neighbours.

Place one queen per row. Track attacked columns and both diagonals in sets so every safety check is constant time.

Every element is either in or out. That binary choice at each index builds a decision tree with 2 to the n leaves.

Fix each candidate in the current position by swapping it forward, recurse on the rest, then swap back.

Fill the first empty cell with each legal digit and recurse. Validating as you place, rather than at the end, is what makes it tractable.

Words that share a prefix share a path. Lookup costs the length of the word, no matter how large the dictionary grows.

Walk the numbers. The first unmarked number is prime, and all of its multiples are not. Start marking from its square.