The general algorithmic patterns, organized into eighteen topics where each one builds on the techniques of the ones before it. The synopsis below sketches each pattern in Python, and the topic pages underneath work through the problems built on it, with solutions side by side in Python, C++, Rust, TypeScript, Go, and Swift behind a language switcher. Every topic page now opens with an interactive visualizer that plays the algorithm through real test cases one step at a time, and a solution is published only after its implementation passes unit tests against the problem's published examples.
Featured articleA long-form walkthrough of breadth-first and depth-first search and the canonical problems built on them, from flood fill and islands to topological sort, with the reasoning worked out step by step.
Read the article → NewThe problems from LeetCode's Top Interview 150 study plan that the topic pages below don't already cover, each solved in all six languages as an approach ladder: a stepper walks every solution from a naive baseline up to the optimal one.
Work the ladder →Every problem on this page is an instance of one of eighteen patterns. Each card sketches the pattern's canonical shape in Python and links to its topic below.
Replace a rescan with something remembered. A set, a count table, or a prefix sum turns quadratic probing into one pass.
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = iOn sorted or mirrored input, two indexes moving toward each other safely discard a candidate at every step.
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s < target: lo += 1
elif s > target: hi -= 1
else: return [lo, hi]Grow on the right, shrink on the left, and update state incrementally so no substring costs a fresh scan.
left, best, seen = 0, 0, set()
for right, ch in enumerate(s):
while ch in seen:
seen.remove(s[left]); left += 1
seen.add(ch)
best = max(best, right - left + 1)A stack holds exactly the prefix still unresolved, and the monotonic variants pop everything the current element settles.
stack, ans = [], [0] * len(temps)
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop(); ans[j] = i - j
stack.append(i)Any monotonic yes/no boundary can be halved, including answer spaces that are not arrays at all.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target: lo = mid + 1
else: hi = midPointer surgery behind a dummy head for edits, and two speeds of traversal for middles and cycle detection.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextRecursion mirrors the structure. Solve each subtree, combine at the root, and choose the traversal order that fits.
def depth(node):
if not node:
return 0
return 1 + max(depth(node.left),
depth(node.right))When only the current best matters, a heap serves it in logarithmic time without keeping everything sorted.
h = nums[:k]
heapq.heapify(h)
for x in nums[k:]:
if x > h[0]:
heapq.heapreplace(h, x)Build a candidate one choice at a time, recurse, then undo the choice so one path's memory serves every branch.
def backtrack(path, rest):
if not rest:
out.append(path[:]); return
for i, c in enumerate(rest):
path.append(c)
backtrack(path, rest[:i] + rest[i+1:])
path.pop()A tree keyed by characters, so words sharing a prefix share a path and prefix queries fall out for free.
node = root
for ch in word:
node = node.setdefault(ch, {})
node["end"] = TrueBreadth-first search with a queue finds shortest hop counts, while depth-first search finds components and cycles.
q, seen = deque([start]), {start}
while q:
u = q.popleft()
for v in adj[u]:
if v not in seen:
seen.add(v); q.append(v)Weights change the tools. Dijkstra's greedy frontier, union-find for connectivity, topological order for dependencies.
dist, pq = {src: 0}, [(0, src)]
while pq:
d, u = heapq.heappop(pq)
for v, w in adj[u]:
if d + w < dist.get(v, inf):
dist[v] = d + w
heapq.heappush(pq, (d + w, v))Define the answer for a prefix, write the recurrence, and fill the table so every subproblem is solved exactly once.
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]Two dimensions of state, usually positions in two sequences or a grid, filled in an order where dependencies are ready.
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(
dp[i - 1][j], dp[i][j - 1])Take the locally best step, backed by an exchange argument that no future regret is possible.
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)Sort by start, then merge or count overlaps in one sweep. Most interval problems are a sort plus one pass.
ivs.sort()
merged = [ivs[0]]
for s, e in ivs[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])In-place matrix tricks, modular arithmetic, and the handful of identities that turn simulation into formula.
matrix[:] = [list(r) for r in zip(*matrix)]
for row in matrix:
row.reverse()Treat an integer as a set of flags. Clearing the lowest set bit and XOR's self-cancellation carry most problems.
count = 0
while n:
n &= n - 1
count += 1
Writing every solution in six languages is mostly a lesson in what stays the
same. The algorithm, the invariants, and the complexity are identical
everywhere. What changes is what each language makes you say out loud. Rust is
the strictest teacher. Reversing a linked list becomes an exercise in
ownership, where each node is an Option<Box<ListNode>>
and the idiom is to take() a node out of its slot, rewire it, and
hand it back, because the borrow checker forbids the casual pointer aliasing a
C solution leans on. Its standard BinaryHeap is a max-heap, so a
min-heap wraps every entry in Reverse, strings refuse direct
indexing until you commit to bytes or chars, and debug builds panic on integer
overflow, which turns the lo + (hi - lo) / 2 midpoint from
folklore into enforced discipline.
Go pushes in the opposite direction, toward writing the machinery yourself.
There is no set type, so membership tests use map[T]struct{},
whose empty-struct values occupy zero bytes. A heap is not a container you
import but an interface you implement, five methods on your own slice type,
with the pop idiom slicing the last element off after the library swaps it
into place. Indexing a string yields raw UTF-8 bytes while ranging over it
yields runes, a distinction that decides whether a palindrome check is
correct, and sorting takes a closure through sort.Slice rather
than a comparator object.
C++, TypeScript, and Swift sit between those poles, with iterator invalidation and
reference semantics in C++, TypeScript's single number type
quietly making 64-bit bit manipulation hazardous, and Swift's value-semantic
arrays with copy-on-write, which make in-place tricks subtler than they look.
The topic pages call these differences out where they bite.
The foundation everything else builds on. Most optimal solutions here replace a rescan with something remembered, such as a hash set, a frequency table, a prefix sum, or a canonical key that makes equal things look equal.
Deep dives: Big-O and complexity analysis · Sorting: merge sort and quicksort
Given an integer array nums of length n, return an array ans of length 2n where ans[i] and ans[i+n] both equal nums[i]. Allocate the output and walk nums once, writing each value into both of its target slots. The whole problem is the index identity ans[i] = ans[i+n] = nums[i], which turns concatenation into a single O(n) pass with no edge cases.
Given an integer array, return true if any value appears at least twice and false if every element is distinct. Walk the array once, inserting each number into a hash set and returning true the moment an insert finds the value already present. The set membership check is O(1) on average, so the whole scan is O(n) time and O(n) space, beating the O(n log n) sorting alternative.
Given two strings, return true if one is an anagram of the other, meaning the same letters with the same counts. Build a 26-slot count array, incrementing for each character of the first string and decrementing for each of the second, then check every slot is zero. Compare lengths first for an early exit, and the count array keeps it O(n) time and O(1) space.
Given an array of integers and a target, return the indices of the two numbers that sum to the target. Walk the array once with a hash map from value to index, and for each number check whether its complement, target minus the number, was already stored. The trick is to check before inserting the current value, which handles duplicate values cleanly and keeps it one pass in O(n).
Given an array of strings, return the longest prefix shared by all of them, or an empty string if there is none. Scan vertically, comparing each character position of the first string against the same position in every other string. Stop at the first mismatch or when any string runs out, returning what was matched so far, and the work is bounded by the total character count.
Given an array of strings, group the words that are anagrams of each other and return the groups. Map each word to a canonical key, either its sorted characters or a 26-letter count signature, and append the word to that key's bucket in a hash map. The count signature avoids sorting each word, making the grouping O(n k) for n words of length k rather than O(n k log k).
Given an array and a target value, remove every occurrence in place and return k, the count of remaining elements, which must sit in the first k slots. Walk with a fast read pointer and a slow write pointer, copying each non-target element into the write slot and advancing it. The invariant is that everything before the write pointer is already kept, giving one stable O(n) pass.
Given an array where one value appears more than n/2 times, return that majority value. Run Boyer-Moore voting. Keep a candidate and a counter, increment when the current element matches the candidate, decrement otherwise, and adopt a new candidate whenever the counter hits zero. It works because every decrement cancels one majority vote against one other vote, and the majority has votes to spare, giving O(n) time and O(1) space.
Implement a hash set supporting add, remove, and contains for integer keys without using built-in hash containers. Back it with a fixed array of buckets, hash each key with modulo the bucket count, and chain collisions inside each bucket using a list. Scan the chain before inserting so duplicates are never stored twice, and with a sensible bucket count the average operation stays O(1).
Implement a hash map supporting put, get, and remove for integer keys and values without built-in hash containers. Use the same bucket array with chaining as a hash set, but store key and value pairs in each chain, and have put overwrite the value when the key already exists. The overwrite-on-existing-key check inside put is the detail most often missed, and modulo bucketing keeps average operations O(1).
Given an integer array, sort it in ascending order in O(n log n) time without calling the library sort. Implement merge sort. Recursively split the array in half, sort each half, and merge the two sorted halves with two pointers into a buffer. Merge sort guarantees O(n log n) worst case, while a quicksort with naive pivots degrades to O(n^2) on sorted or equal-heavy inputs, which is worth being able to explain.
Given an array containing only 0s, 1s, and 2s, sort it in place in a single pass. Apply the Dutch national flag partition with low, mid, and high pointers. Swap a 0 at mid down to low, swap a 2 up to high, and step over 1s. After swapping with high, do not advance mid, because the element brought in from the right is still unexamined.
Given an integer array and k, return the k most frequent values in any order. Count occurrences with a hash map, then bucket by frequency. Build an array where slot f holds the values appearing exactly f times, and collect from the highest slot down until k values are gathered. Frequency never exceeds n, so the bucket array is linear in size and the whole solution runs in O(n), beating a heap.
Design encode and decode functions that pack a list of strings into one string and recover it exactly, even when the data contains any delimiter characters. Prefix each string with its length and a sentinel such as '#', producing chunks like 4#word, then decode by reading digits up to the sentinel and slicing exactly that many characters. The length prefix removes all ambiguity because payload bytes are never interpreted, unlike escaping schemes.
Preprocess an immutable integer matrix so sumRegion(row1, col1, row2, col2) returns any rectangle's sum in O(1). Build a prefix table with one extra row and column of zeros, where each entry holds the sum of the rectangle from the origin up to that cell. Answer queries by inclusion-exclusion, subtracting the top and left strips and adding back the doubly removed corner, and the zero padding eliminates boundary checks.
Given an integer array, return an array where each position holds the product of all other elements, without division and in O(n). Do a forward pass writing the product of everything strictly left of each index, then a backward pass multiplying in a running product of everything to the right. The prefix-times-suffix decomposition is the idea, and carrying the suffix product in one variable keeps extra space at O(1).
Given a 9x9 board partially filled with digits, decide whether the placed digits break any Sudoku rule, ignoring solvability. Scan every cell once while maintaining nine row sets, nine column sets, and nine box sets, reporting failure the moment a digit repeats within any of its three sets. The box index is (row / 3) * 3 + col / 3 with integer division, the one formula worth memorizing.
Given an unsorted integer array, return the length of the longest run of consecutive values, in O(n) rather than by sorting. Load everything into a hash set, then for each value whose predecessor n-1 is absent, count upward while n+1, n+2, and so on remain in the set. Starting only at sequence beginnings is the trick, since every element is touched a constant number of times, keeping the scan linear.
Given daily stock prices with unlimited transactions while holding at most one share, return the maximum total profit. Sum every positive day-to-day difference. Whenever tomorrow's price beats today's, add the delta, which amounts to buying before every rise and selling at every peak. The justification is that any optimal trade decomposes into consecutive single-day gains, so the greedy one-pass O(n) sweep loses nothing.
Given an integer array, return all values appearing more than n/3 times, of which at most two can exist. Run Boyer-Moore voting with two candidates and two counters, replacing a candidate only when its counter is zero and the element matches neither. The voting pass alone is insufficient, so a second pass must verify each surviving candidate's true count exceeds n/3, keeping the whole thing O(n) time and O(1) space.
Given an integer array and a target k, count contiguous subarrays whose elements sum exactly to k. Sweep once with a running prefix sum and a hash map from prefix-sum value to occurrence count, adding the count stored under sum minus k at every step before recording the current sum. Seed the map with zero mapping to one so subarrays starting at index zero count, and the map handles negatives where windows fail.
Given an unsorted integer array, return the smallest missing positive integer in O(n) time and O(1) extra space. Treat the array itself as the hash table. Repeatedly swap each value v in 1..n into slot v-1, then scan for the first index i whose value is not i+1 and return i+1. Each swap places one value at its final home, so the loop is linear, and values outside 1..n are simply left alone.
When the input is sorted or mirrored, two indexes that only move toward each other can replace a full pass over every pair, cutting quadratic work to linear.
Deep dives: Two pointers and sliding window
Given a character array, reverse it in place using O(1) extra memory. Put one pointer at the first index and one at the last, swap the characters, and walk both inward until they meet or cross. The only detail is the loop condition, where left < right handles both even and odd lengths, since the middle character of an odd-length array needs no swap.
Given a string containing mixed punctuation, spaces, and letters, decide whether it reads the same forward and backward when only alphanumeric characters are considered, case-insensitively. Use two pointers from the ends, advancing each past non-alphanumeric characters before comparing lowercased characters and stepping inward. The pitfall is bounds, since the inner skip loops must also check left < right, or the pointers can run past each other on strings made entirely of punctuation.
Given a string, determine whether it can become a palindrome by deleting at most one character. Compare from both ends as usual, and at the first mismatch branch into two checks, verifying the remaining range is a palindrome after skipping the left character or after skipping the right one. Trying both skips is essential because either side might be the correct deletion, and with only one mismatch allowed the total work stays O(n).
Given two strings, build the result by taking characters from them alternately, starting with the first, then appending whatever remains of the longer string. Walk a shared index while it is inside both strings, pushing one character from each per step, then append the leftover tail. Handling unequal lengths is the only real content, and slicing the tail after the shared loop avoids per-character bounds checks.
Given two sorted arrays where the first has enough trailing space to hold both, merge the second into the first in place. Compare from the back with three pointers, the last real element of each array and a write pointer at the very end, always placing the larger value. Filling backward is the trick, since the write position never catches up to unread data, and any leftovers of the second array still need copying.
Given a sorted integer array, remove the duplicates in place so each value appears once, and return the new length k with the unique values at the front. Use a slow write pointer and a fast read pointer, copying an element forward only when it differs from the last written value. Sortedness guarantees duplicates are adjacent, which is why a single O(n) comparison against the previous keeper suffices.
Given a 1-indexed array sorted in ascending order and a target, return the 1-based indices of the two numbers that sum to it, using constant extra space. Start pointers at both ends. If the sum is too small move the left pointer right, if too large move the right pointer left, until the target is hit. Sortedness is what makes each move safe, since the discarded element could not appear in any valid pair.
Given an integer array, return all unique triplets that sum to zero. Sort the array, then for each index i run the sorted two-sum two-pointer scan on the suffix looking for the complement of nums[i]. Duplicate handling is the hard part. Skip repeated values for i, and after recording a triplet advance both inner pointers past their own repeats, which keeps results unique without a set in O(n^2).
Given an integer array and a target, return all unique quadruplets summing to the target. Sort, then fix two indices with nested loops and close each pair with the standard two-pointer scan on the remaining range, skipping duplicate values at every one of the four levels. This is the general k-sum recursion pattern, peeling off fixed elements until two remain. Watch for overflow when summing four large values.
Given an array and an integer k, rotate the array to the right by k steps in place. Take k modulo n, reverse the entire array, then reverse the first k elements and finally the remaining n minus k elements. The triple-reversal identity is the whole trick, and forgetting the k mod n reduction breaks the case where k exceeds the array length.
Given an array of line heights, pick the two lines that hold the most water against the x-axis and return that maximum area. Start pointers at both ends, record width times the smaller height, and move the pointer at the shorter line inward each step. Width only shrinks as pointers advance, so any pairing kept with the shorter wall cannot beat the current area, which is what makes one O(n) pass sufficient.
Given people's weights and a boat weight limit, with at most two people per boat, return the minimum number of boats. Sort the weights, then point at the lightest and heaviest. If they fit together send both, otherwise send the heaviest alone, counting one boat either way. The greedy pairing is safe because the heaviest person must board something and the lightest is the best possible companion, giving O(n log n) overall.
Given an elevation map of bar heights, compute how much rainwater is trapped between the bars. Keep two pointers with running maxima leftMax and rightMax, always advancing the side whose maximum is smaller and adding that side's max minus its current height. The invariant is that water over the smaller-max side is already determined, because a wall at least that tall exists on the other side, giving O(n) time and O(1) space.
A window over the array grows on the right and shrinks on the left while its state updates incrementally, so every substring question stops costing a fresh scan.
Deep dives: Two pointers and sliding window
Given an integer array and an integer k, decide whether two equal values exist at indices at most k apart. Slide a window of the last k elements as a hash set. Check membership before adding each element, and once the set exceeds size k evict the element that fell out of range. The rolling eviction bounds memory at O(min(n, k)) and keeps every check O(1), instead of comparing all pairs.
Given daily stock prices, choose one day to buy and a later day to sell, returning the maximum profit or zero if no profit is possible. Sweep once, tracking the minimum price seen so far and the best difference between the current price and that minimum. The invariant is that for each day the running minimum is the optimal buy among all earlier days, so a single O(n) pass with two variables suffices.
Given a string, return the length of the longest substring with no repeated characters. Slide a window with a map from character to last seen index, and when the current character was seen at or after the left edge, jump the left edge past that occurrence. The pitfall is moving the left edge backward, so take the maximum of its current position and the jump target to keep it monotonic and the pass O(n).
Given an uppercase string and an integer k, return the longest substring length achievable by changing at most k characters so all match. Expand a window with per-letter counts, tracking maxFreq, the highest single-letter count in the window, and shrink from the left while window length minus maxFreq exceeds k. The subtle point is that maxFreq need not decrease when shrinking, since a stale value only blocks growth and the recorded best stays valid.
Given strings s1 and s2, decide whether s2 contains any permutation of s1 as a contiguous substring. Slide a fixed window of length len(s1) across s2, maintaining 26-letter counts for both strings and updating only the entering and leaving characters each step. Tracking a matches counter of how many of the 26 letters agree turns each window comparison into O(1), so the scan is O(n) rather than comparing full count arrays every step.
Given positive integers and a target, return the length of the shortest contiguous subarray whose sum reaches the target, or zero if none does. Expand the window rightward adding elements, and whenever the sum is at least the target, shrink from the left while that still holds, recording the smallest length. Positivity is the key assumption. Sums grow with expansion, so both pointers move only forward and the pass is O(n).
Given a sorted array, an integer k, and a value x, return the k elements closest to x in ascending order. Binary search the left edge of the size-k window over positions 0 to n-k, comparing x - arr[mid] with arr[mid+k] - x to decide which direction to move. Comparing raw differences instead of absolute distances is the trick, since it handles the tie-breaking toward smaller elements correctly and yields O(log(n-k) + k) overall.
Given strings s and t, return the smallest substring of s containing every character of t with multiplicity, or an empty string. Expand the right edge while tallying characters, and once the count of fully satisfied characters reaches the number required, shrink from the left and record the best window. Tracking have versus need as scalar counters keeps each step O(1), and shrinking eagerly whenever the window is valid is what guarantees minimality.
Given an integer array and a window size k, return the maximum of each contiguous window as it slides across. Maintain a deque of indices with strictly decreasing values. Pop smaller values from the back before pushing each index, drop the front when it exits the window, and read the maximum at the front. Each index enters and leaves the deque at most once, so the pass is O(n) despite the nested-looking pops.
A stack remembers exactly the prefix that is still unresolved. The monotonic variants answer next-greater and span questions in one pass by popping everything the current element settles.
Given operations where a number records a score, '+' adds the previous two scores, 'D' doubles the previous score, and 'C' cancels it, return the total of the final record. Simulate with a stack of integers, pushing the result of each scoring operation and popping on 'C'. The only care needed is that '+' reads the top two entries without removing them, and the answer is simply the sum of whatever remains.
Given a string of the six bracket characters, decide whether every bracket is closed by the matching type in the correct order. Push each opening bracket onto a stack, and for each closing bracket check that the stack is nonempty and its top is the matching opener, then pop. The classic pitfalls are a closer on an empty stack and leftover openers, so the string is valid only if the stack finishes empty.
Implement a LIFO stack supporting push, pop, top, and empty using only queue operations. The clean approach uses one queue. After enqueueing a new element, rotate by dequeuing and re-enqueueing all the older elements so the newest sits at the front. That makes push O(n) while pop and top become plain O(1) queue operations, the standard trade against the two-queue variant.
Implement a FIFO queue supporting push, pop, peek, and empty using only two stacks. Push always onto the in-stack. For pop or peek, when the out-stack is empty, pour the entire in-stack into it, which reverses the order so the oldest element surfaces on top. Each element moves between stacks at most once, so every operation is amortized O(1) even though a single pop can be O(n).
Design a stack supporting push, pop, top, and getMin, all in O(1) time. Store with each entry the minimum of the stack at that depth, either as a pair on one stack or as a parallel min stack pushed and popped in lockstep. Snapshotting the minimum per level is the trick, because popping automatically restores the previous minimum with no recomputation.
Given an arithmetic expression in reverse Polish notation as an array of tokens, evaluate it and return the integer result. Scan tokens left to right, pushing numbers onto a stack, and on each operator pop two values, apply the operation, and push the result. Operand order is the classic slip. The first pop is the right operand, which matters for subtraction and division, and division truncates toward zero.
Given asteroids where the sign encodes direction and the magnitude encodes size, return the survivors after all collisions destroy the smaller of any colliding pair. Push right-movers onto a stack. When a left-mover arrives, pop strictly smaller right-movers off the top, then handle equality by popping both and a larger top by dropping the newcomer. Only a right-mover followed by a left-mover collides, so left-movers with no opposing top are simply pushed.
Given daily temperatures, return for each day how many days until a warmer temperature, or zero if none comes. Keep a stack of indices whose temperatures are monotonically decreasing. When a warmer day arrives, pop every colder index and record the index difference as that day's answer. Pushing indices rather than temperatures is the point, since the answer is a distance, and each index is pushed and popped at most once for O(n).
Implement a class whose next(price) returns the span, the count of consecutive prior days, including today, with prices at or below today's. Keep a monotonic stack of (price, span) pairs. On each call pop every pair with price at or below the new price, accumulating their spans into the new entry, then push it. Collapsing popped runs into a single pair is the trick that makes each call amortized O(1).
Given car positions and speeds heading toward a target on one lane, return how many fleets arrive, since a car that catches a slower one slows and merges. Sort by position descending, compute each arrival time as distance remaining over speed, and push a time only when it exceeds the stack top. A car whose time is at most the stack top joins that fleet, so the final stack height is the fleet count.
Given an absolute Unix-style file path, return its canonical form with no trailing slash, no '.' or '..' components, and single slashes. Split on '/', then process each piece with a stack of directory names, skipping empty pieces and '.', popping on '..', and pushing everything else. Joining the stack with slashes under a leading '/' rebuilds the path, and '..' at the root, meaning an empty stack, must be silently ignored.
Given an encoded string where k[inner] means the bracketed content repeats k times, possibly nested, return the decoded string. Scan with two stacks, one for counts and one for partial strings. On '[' push both and reset, on ']' repeat the current segment by the popped count and append it to the popped string. Multi-digit counts must be accumulated digit by digit, and nesting works because each ']' closes exactly the most recent '['.
Design a stack where push adds a value and pop removes the most frequent one, breaking ties by recency. Keep a count map from value to frequency plus one stack per frequency level, pushing each value onto the stack for its new count while tracking the maximum frequency. Popping from the max-frequency stack handles ties naturally, since copies remain on lower stacks and resurface as the maximum drops, keeping every operation O(1).
Given histogram bar heights, return the largest rectangle area inside the histogram. Maintain an increasing stack of indices, and when the current bar is shorter than the top, pop and multiply the popped height by the width between the new top and the current index, exclusive. Each pop finalizes one bar, bounded by the first shorter bar on each side, and a zero-height sentinel at the end flushes everything for an O(n) total.
Anything with a monotonic yes/no boundary can be searched, including answer spaces that are not arrays at all, such as eating speeds, ship capacities, and largest-sum limits.
Deep dives: Binary search
Given a sorted array of integers and a target, return the index of the target or -1 if absent. Maintain lo and hi pointers, compute the middle index, and discard the half that cannot contain the target until the pointers cross. The classic pitfall is boundary handling. With an inclusive hi, loop while lo <= hi and move hi to mid - 1, which guarantees termination in O(log n).
Given a sorted array of distinct integers and a target, return the index of the target or the index where it would be inserted to keep order. Binary search with lo at 0 and hi at the array length, shrinking toward the first element greater than or equal to the target, and return lo. This is exactly lower_bound, whose invariant is that everything left of lo is strictly less than the target.
An integer between 1 and n was picked, and the guess API reports whether a query is too high, too low, or correct. Return the picked number. Binary search the range 1 to n, calling the API at each midpoint and keeping the half it points to. The predicate comes from the API instead of an array, and computing the midpoint as lo + (hi - lo) / 2 avoids integer overflow.
Given a non-negative integer x, return the integer square root, meaning the largest k with k*k <= x, truncating any decimal part. Binary search k over 0 to x, squaring the midpoint and keeping the highest value that does not exceed x. Frame it as the last k satisfying k*k <= x rather than the first failure, and compare via k <= x / k or use 64-bit math so the square never overflows.
Given an m x n matrix where each row is sorted and the first element of each row exceeds the last of the previous row, determine whether a target exists. Run one binary search over indexes 0 to m*n - 1, mapping each index to matrix[idx / n][idx % n]. The grid is one sorted array in disguise, so row and column come from a single division and modulo, giving O(log(mn)).
Given banana pile sizes and a deadline of h hours, find the minimum integer eating speed k where each pile takes ceil(pile / k) hours and the total must not exceed h. Binary search k from 1 to the largest pile, summing hours at each candidate and keeping the smallest feasible speed. The search runs over the answer space, not the array. Hours decrease monotonically as k grows, so feasibility forms a clean boundary.
Given package weights shipped in order and a limit of d days, find the minimum ship capacity that delivers everything on time. Binary search capacity between the heaviest package and the total weight, and for each candidate greedily fill days, starting a new day whenever the next package would overflow. The greedy check is valid because packages cannot be reordered, and the lower bound matters, since capacity below the heaviest package can never ship it.
Given a sorted array of distinct values rotated at an unknown pivot, return the minimum element in O(log n). Binary search comparing nums[mid] against nums[hi]. If mid's value is greater, the minimum lies strictly right of mid, otherwise it is at mid or to its left. The comparison must be against the right end, because checking nums[lo] breaks on an already sorted array, and hi moves to mid, never past the candidate.
Given a rotated sorted array of distinct values and a target, return its index or -1 in O(log n). At each step compare nums[lo] with nums[mid] to decide which half is sorted, then check whether the target falls inside that sorted half's range to choose where to recurse. The invariant is that at least one half is always properly sorted, and the range test must handle its boundaries carefully so the target is never skipped.
Given a rotated sorted array that may contain duplicates and a target, return whether the target exists. Use the same sorted-half logic as the distinct version, but when nums[lo], nums[mid], and nums[hi] are all equal nothing can be inferred, so shrink both ends by one and continue. Those equal-edge shrinks are the trick, since duplicates can hide which half is sorted, and they degrade the worst case to O(n) while typical cases stay logarithmic.
Design a store with set(key, value, timestamp) and get(key, timestamp), where get returns the value with the largest timestamp at or before the query, or an empty string. Keep a hash map from key to a list of (timestamp, value) pairs and binary search for the rightmost timestamp not exceeding the query. The lists stay sorted for free because timestamps strictly increase, and get is a floor search, not an exact match.
Given an array of non-negative integers and an integer k, split it into k contiguous subarrays so the largest subarray sum is minimized, returning that value. Binary search the answer between the maximum element and the total sum, and for each candidate cap greedily count how many pieces it forces. Feasibility means the count is at most k, and it is monotone in the cap, the property that justifies binary searching the answer.
Given two sorted arrays, return the median of their merged order in O(log(min(m, n))) time. Binary search a cut in the smaller array, and the cut in the larger one is then forced so the two left halves hold half of all elements combined. A cut is valid when each left maximum is at most the opposite right minimum. Sentinel infinities handle empty sides, and searching the smaller array keeps the cut in bounds.
Given an interactive mountain array, strictly increasing then strictly decreasing, return the smallest index of a target, or -1, using a limited number of get calls. First binary search for the peak by comparing each mid against its right neighbor, then run an ascending search on the left slope and a descending one on the right. Searching the left slope first guarantees the smallest index, and locating the peak restores sortedness to each half.
Pointer rewiring under constraints. Dummy heads remove edge cases, fast and slow pointers find middles and cycles, and the two cache designs are the classic exercises in composing data structures.
Given the head of a singly linked list, reverse it and return the new head. Walk the list with prev and cur pointers, saving cur.next into a temporary, pointing cur.next back at prev, then advancing both pointers one step. The order of operations is critical. Capture next before rewiring or the rest of the list is lost, and prev ends as the new head when cur runs off the end.
Given the heads of two sorted linked lists, splice them into one sorted list and return its head. Create a dummy node, keep a tail pointer, and repeatedly attach whichever list's current node is smaller, advancing that list, then attach the leftover remainder when one list empties. The dummy head removes every special case around an empty result or choosing the first node, and reusing the existing nodes keeps it O(1) extra space.
Given the head of a linked list, return whether following next pointers ever revisits a node, meaning a cycle exists. March a slow pointer one step and a fast pointer two steps. If fast runs off the end the list is acyclic, and if the pointers meet there is a cycle. They must meet because inside a cycle fast gains one node on slow per step, so it can never jump over slow.
Given a list L0, L1, ..., Ln, rearrange it in place into L0, Ln, L1, Ln-1, and so on, alternating front and back nodes. Find the middle with slow and fast pointers, reverse the second half, then interleave the two halves by alternating splices. Remember to cut the first half's tail to null before interleaving, and the front half may hold one extra node when the length is odd, so it leads the merge.
Given a linked list head and an integer n, remove the nth node from the end in one pass and return the head. Start two pointers at a dummy before the head, advance the lead n steps, then walk both together until the lead hits the last node. The trail then sits just before the target, so one next reassignment removes it, and the dummy is what lets the head itself be deleted cleanly.
Given a linked list whose nodes each have a next pointer and a random pointer to any node or null, return a deep copy. Do one pass building a hash map from each original node to a fresh clone, then a second pass wiring every clone's next and random through the map. The map resolves random pointers that target nodes not yet visited, and the O(1) space variant interleaves each clone after its original instead.
Given two non-empty linked lists storing non-negative integers in reverse digit order, return their sum as a list in the same format. Walk both lists in step, adding the two current digits plus the carry, appending sum mod 10 to a dummy-headed result and carrying sum / 10 forward. Loop while either list has nodes or the carry is nonzero, since forgetting the final carry drops the leading digit on sums like 5 plus 5.
Given n+1 integers in the range 1 to n with one repeated value, find the duplicate without modifying the array, in O(1) space. Treat index i as a node pointing to nums[i] and run Floyd's algorithm. After fast and slow meet, restart one pointer at zero and advance both in single steps. They reconverge at the cycle entrance, which is the duplicate, since two indices holding the same value point at the same node.
Given a list and positions left and right, reverse the sublist between those positions in one pass and return the head. From a dummy node, walk to the node before position left, then do right minus left head insertions, each detaching the node after the sublist start and relinking it after the anchor. The anchor and original sublist head stay fixed, keeping both seams connected, and the dummy covers reversal starting at the head.
Design a fixed-capacity circular queue supporting enQueue, deQueue, Front, Rear, isEmpty, and isFull. Back it with an array of size k plus a head index and a count. Enqueue writes at (head + count) mod k, dequeue advances head modulo k, and the count answers isEmpty and isFull. Tracking the count is the trick, since it distinguishes a full buffer from an empty one when head and tail coincide.
Design a fixed-capacity cache where get and put both run in O(1) and put evicts the least recently used key when full. Pair a hash map from key to node with a doubly linked list ordered by recency. Each access moves its node to the front, and eviction removes the node before the tail. Dummy head and tail sentinels eliminate null checks, and updating an existing key must still refresh its recency.
Design a fixed-capacity cache with O(1) get and put where eviction removes the least frequently used key, breaking ties by least recent use. Keep a key-to-node map plus one doubly linked list per frequency bucket, and track the minimum frequency, and each access moves a node into the next bucket. The minFreq pointer is the subtlety. It resets to 1 on every insertion and only increments when an access empties the bucket it points at.
Given an array of k sorted linked lists, merge them into one sorted list and return its head. Push each non-null head into a min-heap keyed by node value, then repeatedly pop the smallest node, append it to a dummy-headed tail, and push that node's next if it exists. Every pop is O(log k) over n total nodes, giving O(n log k), and the pairwise divide and conquer merge achieves the same bound without a heap.
Given a list and an integer k, reverse every group of k consecutive nodes, leaving a final shorter group untouched, and return the head. From a dummy node, first probe k nodes ahead to confirm a full group, reverse that block with the usual three-pointer walk, then splice it back between the neighbors. Probing before reversing protects the short tail, and the group's original first node becomes its tail, anchoring the next splice.
Nearly every tree problem is one recursion shape. Return a fact about each subtree once, combine the children's answers, and keep a separate best when the answer is not the return value.
Deep dives: Depth-first search (DFS) · Breadth-first search (BFS)
Given the root of a binary tree, return the values of its nodes in inorder, meaning left subtree, node, then right subtree. The recursive version is two lines, but the iterative version drives a stack. Push nodes while walking left, then pop one, record it, and switch to its right child. The stack version is the interesting one, since every stacked node still owes its visit, while a popped node's left side is already complete.
Given the root of a binary tree, return its node values in preorder, meaning node first, then left subtree, then right subtree. Iteratively, push the root on a stack, then pop a node, record its value, and push its right child before its left so the left is processed first. Pushing right before left is the detail to remember, and preorder is the easiest traversal to iterate since the node is handled at pop time.
Given the root of a binary tree, return its node values in postorder, meaning left subtree, right subtree, then the node itself. The cleanest iterative route runs a modified preorder visiting node, right, left by pushing left before right, then reverses the collected output at the end. That reversal trick sidesteps the awkward state tracking of true one-stack postorder, where each node must wait until its right subtree is finished before it can be emitted.
Given the root of a binary tree, mirror it by swapping the left and right children of every node, and return the root. Recurse top down. Swap the current node's two child pointers, then invert each subtree, or do the same with an explicit stack or queue. The swap is of pointers, not values, so one exchange moves whole subtrees, and the null root base case is the only edge condition, all in O(n).
Given the root of a binary tree, return its maximum depth, the number of nodes along the longest path from root to a leaf. Recurse. A null node has depth 0, and any other node has depth 1 plus the larger of its children's depths. The same answer falls out of BFS by counting levels, and the recursive form is the seed pattern for many harder tree problems, computing a value bottom up from children.
Given the root of a binary tree, return its diameter, the number of edges on the longest path between any two nodes, which need not pass through the root. Run a DFS that returns each subtree's height while a shared maximum tracks left height plus right height at every node. The separation is the trick. The function returns the best downward arm, while the answer is the best bend, collected as a side effect.
Given the root of a binary tree, return whether it is height-balanced, meaning every node's subtree heights differ by at most one. Compute heights bottom up with DFS, but return -1 as a sentinel the moment any subtree is unbalanced, and propagate that sentinel straight up without further work. Folding the boolean into the height return is what keeps it O(n), while the naive version recomputes heights at every node and degrades to O(n^2).
Given the roots of two binary trees, return whether they are structurally identical with equal node values throughout. Recurse on both trees simultaneously. Two nulls are the same, one null or mismatched values are not, and otherwise the answer is the left pair check and the right pair check combined. Checking the null cases before touching values keeps the comparison safe, and this simultaneous recursion reappears in Subtree of Another Tree.
Given the roots of trees root and subRoot, return whether some subtree of root is identical to subRoot in structure and values. Traverse root and at each node run a full Same Tree comparison against subRoot, returning true on the first success. A subtree here means a node plus all its descendants, so a matching region that continues below subRoot's leaves does not count, and the nested check runs in O(m * n).
Given a binary search tree and two nodes p and q, return their lowest common ancestor. Walk down from the root. When both values are smaller than the current node go left, when both are larger go right, and stop at the first node where they split or one equals it. The BST ordering makes the LCA the split point, a node counts as its own ancestor, and the walk runs in O(h).
Given the root of a binary search tree and a value guaranteed not to be present, insert it and return the root. Walk down, going left when the value is smaller and right when larger, until a null child slot appears, then attach a new leaf there. No rebalancing is required since any valid BST is accepted, and the only edge case is an empty tree, where the new node itself is the answer.
Given a BST root and a key, delete the node holding that key while keeping the tree a valid BST. Recurse to the node. With at most one child return that child or null, and with two children copy in the inorder successor's value, then delete that successor from the right subtree. The successor, the leftmost node of the right subtree, never has a left child, so the second deletion hits an easy case.
Given the root of a binary tree, return its node values level by level as a list of lists, left to right within each level. Run BFS with a queue, and at the start of each round snapshot the queue's size, then pop exactly that many nodes into one level list while enqueueing their children. The size snapshot separates the levels, since without it the queue mixes parents and children and the boundaries vanish.
Given the root of a binary tree, return the rightmost node value of each level, top to bottom. Run BFS with the size-snapshot pattern and keep the last node of each level, or DFS right child first, recording the first node at each new depth. The rightmost node is not always a right child. A deep left branch can stick out past a shallow right side, so per-level tracking is essential.
Given an n x n binary grid with n a power of two, build its quad tree and return the root. Recurse on the four quadrants. If all four children return as leaves sharing one value, collapse them into a single leaf, otherwise wrap them in an internal node. The merge test after recursion is the heart of it. The base case is a single cell, and each leaf summarizes a uniform region.
Given the root of a binary tree, count the nodes that are good, meaning no node on the root-to-node path has a strictly greater value. DFS carrying the path maximum down. A node is good when its value is at least that maximum, and the maximum updates before recursing into the children. Information flows top down as a parameter rather than bottom up as a return value, and the root always counts as good.
Given the root of a binary tree, return whether it is a valid BST, where every node's left subtree holds strictly smaller values and its right subtree strictly larger ones. DFS passing down an open interval (lo, hi). Each node must fall inside it, the left child narrows hi to the node's value, and the right child raises lo. Checking only parent against children misses grandparent violations, so the bounds must travel with the recursion.
Given the root of a binary search tree and an integer k, return the kth smallest value. Run an inorder traversal, which visits BST values in sorted order, decrementing k at each visited node and stopping when it reaches zero. The iterative stack version is preferred because it can halt mid-traversal at the kth node, costing O(h + k) instead of walking the whole tree.
Given the preorder and inorder traversals of a binary tree with distinct values, rebuild the tree and return its root. The first preorder element is always the root. Find it in the inorder array, where everything left of it forms the left subtree and everything right the right subtree, and recurse on the two slices. A value-to-index map over inorder removes the linear search per node, taking the build from O(n^2) to O(n).
Given a binary tree of money values, maximize the total robbed when no parent and child are both taken. Postorder DFS returns a (rob, skip) pair per node. Rob adds the node's value to both children's skip results, while skip takes the maximum of each child's pair. The subtle point is that skipping a node does not force robbing its children, so skip uses each child's best of both states.
Given a tree and a target, delete every leaf with that value, including nodes that become leaves after their children go, and return the root. Postorder DFS recurses into both children first, reassigning each child pointer to the recursive result, then returns null if the current node is now a target-valued leaf. Deciding after the children are processed is essential, because deletions cascade upward and a node is judged only after its subtree settles.
Given a binary tree with possibly negative values, return the maximum sum over all paths, where a path connects any chain of nodes and need not include the root. DFS returns each node's best downward sum while a global maximum collects the bend, node value plus both children's downward sums. Clamping each child's contribution at zero is the key, since negative branches are better dropped, and the returned arm uses at most one child.
Design serialize and deserialize methods that turn an arbitrary binary tree into a string and rebuild it exactly. Serialize with preorder DFS, writing each node's value and a marker like # at every null, while deserialize consumes tokens in order, building a node and then recursively its left and right subtrees. The explicit null markers make one preorder pass unambiguous, since without them a single traversal cannot pin down the structure.
A heap keeps only what matters, the top k of a stream, the next event by time, or the boundary between the lower and upper half of the data.
Deep dives: Heaps and priority queues
Design a class that accepts streaming integers and after each add call returns the kth largest value seen so far. Maintain a min-heap holding only the k largest elements. Push every new value, then pop whenever the size exceeds k. The invariant is that the heap root is always the kth largest, so each add costs O(log k) and the smaller values are safely discarded.
Given an array of stone weights, repeatedly smash the two heaviest stones, leaving their difference if unequal, and return the last remaining weight or zero. Use a max-heap. Pop the two largest, push back the difference when it is nonzero, and loop until at most one stone remains. In Python, negate values to simulate a max-heap with heapq, and remember the empty-heap case returns zero.
Given a list of 2D points and an integer k, return the k points closest to the origin by Euclidean distance, in any order. Keep a max-heap of size k keyed on squared distance, popping the farthest whenever the heap grows past k, for O(n log k). Compare squared distances to avoid floating-point square roots, and recall that quickselect achieves average O(n) when needed.
Given an unsorted integer array and k, return the kth largest element without fully sorting. Quickselect partitions around a pivot and recurses only into the side containing index n minus k, giving average O(n) time. The pitfall is pivot choice. A fixed pivot degrades to quadratic on adversarial input, so randomize it, or fall back to a size-k min-heap for guaranteed O(n log k).
Given task labels and a cooldown n that must separate identical tasks, return the minimum number of CPU intervals, idle slots included, needed to finish them all. Count frequencies, find the maximum frequency f and the number of tasks tied at f, then compute (f-1)*(n+1) plus the tie count. Floor the answer at the total task count, because with enough distinct tasks every idle slot fills and the formula undercounts.
Design a class supporting postTweet, follow, unfollow, and getNewsFeed, where the feed returns the 10 most recent tweets from the user and everyone they follow. Store per-user tweet lists stamped with a global timestamp, and on getNewsFeed merge the relevant lists with a max-heap, popping up to ten times. Seed the heap with each list's newest tweet and after each pop push that author's next older one, the standard k-way merge.
Given tasks with enqueue times and processing durations, return the order a single-threaded CPU executes them when it always runs the shortest available task, ties broken by lower index. Sort by enqueue time, sweep a clock forward, push all arrived tasks into a min-heap keyed by duration then index, and pop the next task to run. When the heap is empty, jump the clock straight to the next arrival, and keep original indices when sorting.
Given a string, rearrange its characters so no two adjacent characters are equal, returning any valid arrangement or the empty string if impossible. Greedily build the answer with a max-heap of letter counts. Pop the most frequent letter, append it, and only push it back after the next pop. Holding back the just-used letter enforces the spacing, and impossibility happens exactly when one letter's count exceeds (n+1)/2.
Given counts a, b, and c, build the longest string from those three letters that never contains three identical letters in a row. Use a max-heap by remaining count. Pop the most plentiful letter, but if appending it would create a triple, take the second-best letter instead. The hold-back caps every run at two, and the string ends cleanly when only a triple-forcing letter remains in the heap.
Given trips as passenger count, pickup, and dropoff locations plus a capacity, decide whether one car driving east can serve every trip without exceeding capacity. Build a difference array over stops, adding passengers at pickup and subtracting at dropoff, then prefix-sum and compare the running load against capacity. Locations are bounded by 1000, which makes the difference array tiny, and a min-heap ordered by dropoff works when coordinates are large.
Design a structure supporting addNum and findMedian over a stream of integers. Keep two heaps, a max-heap for the lower half and a min-heap for the upper half, rebalancing after every insert so the sizes differ by at most one. The invariant that every low-half element is at most every high-half element makes the median either the larger heap's root or the average of the two roots.
Given projects with capital requirements and profits, starting capital w, and at most k picks, maximize the final capital, where each finished project adds its profit. Sort projects by required capital, and in each of k rounds push all newly affordable profits into a max-heap and pop the largest. The greedy is safe because profit only grows capital and unlocks more options. Stop early if the heap ever empties.
One template generates the whole topic. Choose, recurse, undo. The problems differ only in what a choice is, what prunes a branch, and when to record a result.
Deep dives: Backtracking
Given an integer array, compute the sum of the XOR totals over every one of its 2^n subsets. Recurse with include and exclude branches per element, carrying a running XOR down and adding it to the answer at every leaf. A shortcut worth remembering is that each set bit appears in exactly half the subsets, so the answer also equals the OR of all numbers times 2^(n-1).
Given an array of distinct integers, return every possible subset, the full power set, in any order. Backtrack with a start index, recording the current path at every node, then looping i from start onward, appending nums[i], recursing with i+1, and popping to undo. The start index is the invariant, since only elements after the last chosen one are eligible, which stops the same subset appearing in two different orders.
Given distinct candidate numbers and a target, return all unique combinations that sum to the target, where each candidate may be reused unlimited times. Backtrack over a start index, subtracting each chosen candidate from the remaining target and pruning the branch when it goes negative. The reuse rule is encoded by recursing with i rather than i+1, which permits the same element again while still preventing permuted duplicates.
Given candidates that may contain duplicates and a target, return all unique combinations summing to the target, with each array element used at most once. Sort the array, backtrack with a start index, and recurse with i+1 since reuse is forbidden. The key guard is to skip nums[i] when i is greater than start and it equals nums[i-1], which removes same-depth repeats while still allowing stacked duplicates.
Given integers n and k, return all combinations of k numbers chosen from 1 through n. Backtrack with a start value, appending each candidate, recursing from the next number, and popping, recording the path once it reaches length k. The pruning that matters is to cut the branch immediately, rather than exploring it, when the numbers remaining past the current start cannot fill the open slots.
Given an array of distinct integers, return every possible permutation. Since order matters a start index no longer works, so instead keep a used array, and at each depth loop over all elements, choosing any unused one, recursing, then unmarking it. The recursion finishes when the path length reaches n, and the choose, recurse, undo cycle on the used flags is the entire pattern.
Given an integer array that may contain duplicates, return all unique subsets. Sort first, then run the standard subset backtracking with a start index, recording the path at every node of the tree. The duplicate skip mirrors Combination Sum II. When i is greater than start and nums[i] equals nums[i-1], continue past it, so each value extends a given path only once per depth.
Given an array that may contain duplicates, return all unique permutations. Sort the array and backtrack with a used array as in regular permutations, choosing any unused element at each depth. The duplicate rule is to skip nums[i] when it equals nums[i-1] and nums[i-1] is not currently used, which forces equal values to be placed left to right and eliminates mirrored branches.
Given n, return all strings of n pairs of parentheses that are well formed. Build the string one character at a time, recursing on two choices, adding an open parenthesis while open is below n, and adding a close parenthesis while close is below open. Those gates are the whole validity proof, since no prefix ever closes more than it opens, and recursion stops at length 2n.
Given a 2D board of letters and a word, decide whether the word can be traced through horizontally or vertically adjacent cells without reusing a cell. From every cell matching the first letter, run a DFS that advances one character per step into the four neighbors. Mark the current cell with a sentinel before recursing and restore it afterward. That undo step is what lets other paths reuse the cell.
Given a string s, return all ways to partition it into substrings that are each palindromes. Backtrack on the cut position. From the current start, try each end whose substring is a palindrome, append it, recurse from end+1, then pop. The real choice is where to cut, and checking the palindrome before recursing prunes whole subtrees, and a precomputed table makes each check O(1).
Given a string of digits 2 through 9, return all letter strings those digits could represent on a phone keypad. Map each digit to its letters, then DFS one digit position at a time, appending each candidate letter, recursing to the next digit, and removing it. This is a plain cartesian product over the letter groups, and the one trap is returning an empty list rather than a single empty string for empty input.
Given matchstick lengths, decide whether all of them can form a square with every stick used exactly once. First check the total is divisible by 4, then backtrack each stick into one of four side buckets targeting total/4, removing it on failure. Sorting sticks in descending order fails fast, and skipping buckets whose current sum equals an already-tried bucket's sum removes symmetric duplicate work.
Given an integer array and k, decide whether it can be split into k subsets with equal sums. Either backtrack elements into k running buckets as in Matchsticks to Square, or memoize over a bitmask of chosen elements, completing one subset at a time. Pruning carries it. Sort descending, skip buckets with equal sums, and when a subset hits the target restart the search for the next one.
Given n, return all boards placing n queens on an n by n grid so that no two attack each other, formatted with dots and Qs. Place one queen per row, looping over columns and recursing to the next row whenever the square is safe. Safety checks are O(1) with three hash sets, occupied columns plus the two diagonal directions keyed by r+c and r-c, each added before recursing and removed after.
Given n, return only the number of distinct n-queens placements rather than the boards themselves. Run the same row-by-row backtracking as N Queens, with sets for columns and the two diagonals keyed by r+c and r-c, incrementing a counter on reaching row n. The point is identical machinery without board construction, and bitmask versions pack the three sets into integers for extra speed.
Given a string s and a dictionary, return every sentence formed by inserting spaces so that each piece is a dictionary word. Backtrack over prefixes. For each dictionary word matching the front of the remaining suffix, recurse on the rest and prepend the word to every returned sentence. Memoizing the sentence list for each suffix start index avoids recomputing shared subproblems, turning overlapping branches into lookups.
A prefix tree turns whole-word lookups into per-character walks, which is what makes searching a grid for hundreds of words at once tractable.
Deep dives: Tries (prefix trees)
Implement a trie supporting insert, search for a full word, and startsWith for a prefix. Each node holds a children map or 26-slot array plus an isEnd flag. Insert walks the word creating missing children and marks the last node, while both queries walk without creating. The only difference between search and startsWith is whether the final node's isEnd flag must be true.
Design a structure with addWord and a search where a dot character matches any single letter. Store the words in a trie. Search runs a DFS that follows the matching child for a literal letter but branches into all children on a dot. Success requires consuming the whole query and landing on a node with isEnd set, and the wildcard is what forces recursion over plain iteration.
Given a string s and a dictionary, break s into non-overlapping dictionary words and return the minimum number of leftover characters belonging to no word. Define dp[i] as the minimum extras from index i onward. Either waste s[i] for dp[i+1] plus one, or jump past any dictionary word starting at i. Walking a trie from position i discovers all matching words in one descent, replacing repeated substring lookups.
Given a grid of letters and a list of words, return every word that can be traced through adjacent cells without reusing a cell. Build a trie of all the words, then one DFS per starting cell walks the board and the trie in lockstep, abandoning any path lacking a trie child. Store each word at its end node to collect matches cleanly, and prune exhausted trie leaves so later searches stay fast.
BFS for distances, DFS for structure, indegrees for ordering, and union-find for connectivity. The twelve canonical traversal variants are written out in six languages on the graph traversal page.
Deep dives: Graph traversal in six languages · Breadth-first search (BFS) · Depth-first search (DFS) · Graph theory: topological sort and cycles · Union-Find (disjoint sets)
Given a grid of 1s for land and 0s for water containing exactly one island, return the island's perimeter. Scan all cells. Each land cell adds 4, then subtract 2 for each land neighbor above or to its left, since both cells share that edge. Counting only already-seen neighbors avoids double subtraction. Equivalently, add 1 for every side facing water or the grid border.
Given an alien alphabet order and a list of words, decide whether the words are sorted lexicographically under that order. Build a map from each character to its rank, then compare every adjacent pair of words at their first differing character. The edge case is a pair with no differing character, where the longer word must not come first, because a prefix sorts before its extension.
Given n people and trust pairs meaning a trusts b, return the town judge, who trusts nobody and is trusted by everyone else, or -1. Track a single score per person, subtracting one for each outgoing trust and adding one for each incoming trust. The judge is the unique person scoring exactly n-1, since any outgoing trust ruins the total, and no adjacency structure is needed.
Given a 2D grid of 1s for land and 0s for water, count the islands formed by 4-directionally connected land. Scan the grid, and at each unvisited land cell launch a flood fill, DFS or BFS, that sinks the whole component by overwriting its cells. The number of launches equals the number of islands, and marking cells during the fill stops one island from being counted twice.
Given a grid of 0s and 1s, return the area of the largest 4-connected island, or 0 if there is none. Run the Number of Islands scan, but make the flood fill return how many cells it sank, taking the maximum over all launches. Recursively each cell returns 1 plus its four neighbor calls, with visited cells zeroed first so nothing is counted twice.
Given a reference to one node of a connected undirected graph, return a deep copy of the entire graph. DFS or BFS from the start node, keeping a hash map from each original node to its clone, creating clones on first visit and wiring neighbor lists from mapped entries. The map doubles as the visited set, and checking it before recursing is what keeps cycles from looping forever.
Given a grid of gates, walls, and empty rooms marked infinity, fill each room with the distance to its nearest gate, in place. Seed one queue with every gate and run a single BFS outward, writing the distance on first arrival and stepping only into rooms still holding infinity. Multi-source BFS works because all sources expand in lockstep, so the first arrival at any room comes from the nearest gate.
Given a grid of empty cells, fresh oranges, and rotten oranges that rot adjacent fresh ones each minute, return the minutes until no fresh orange remains, or -1. Seed a queue with all initially rotten oranges and BFS in level-sized rounds, counting one minute per round while decrementing a fresh counter. Watch two pitfalls. Return -1 if any fresh orange stays unreachable, and avoid counting an extra minute after the final round.
Given a height matrix where water flows to equal-or-lower neighbors, return cells able to reach both the Pacific along the top and left edges and the Atlantic along the bottom and right edges. Search inward from each ocean's border cells, moving only to equal-or-higher neighbors, and record each ocean's reachable set. The answer is the intersection of the two sets, and reversing the flow avoids simulating from every cell.
Given a board of Xs and Os, flip every O region that is fully surrounded by Xs, leaving regions touching the border untouched. Run DFS or BFS from every border O, marking each reached O with a temporary letter, then sweep the board flipping unmarked Os to X and restoring marked ones. Inverting the question, finding the survivors instead of the captured regions, is the whole trick.
Given deadend combinations and a target, return the fewest single-wheel turns taking a four-wheel lock from 0000 to the target. BFS over the implicit graph whose nodes are the 10000 wheel states and whose edges are the eight one-turn moves, each wheel stepping up or down with wraparound. Treat deadends as already visited before starting, and check 0000 itself, returning -1 immediately if it is a deadend.
Given numCourses and prerequisite pairs, decide whether every course can be finished, which means the directed prerequisite graph has no cycle. Run DFS with three states, unvisited, in progress, and done, flagging a cycle when an in-progress node is re-entered, or use Kahn's algorithm and check that every node gets processed. The in-progress state is essential, since a plain visited set cannot tell a cycle from a diamond reconvergence.
Given numCourses and prerequisite pairs, return any valid order to take all courses, or an empty array if a cycle makes it impossible. Either run Kahn's algorithm, repeatedly dequeuing zero-indegree nodes and decrementing their neighbors, or DFS with cycle detection and reverse the postorder. Remember that a node finishes DFS only after everything it points to, which is exactly why reversed postorder is a valid topological order.
Given n nodes and an undirected edge list, decide whether they form a valid tree, meaning connected and free of cycles. Check that the edge count is exactly n-1, then confirm connectivity with one DFS or BFS, or use union-find where every merge must join two different roots. With exactly n-1 edges, connected implies acyclic, so the count does half the work and only one property needs checking.
Given prerequisite edges between courses and queries asking whether u is a prerequisite of v, answer each query including indirect chains. Process nodes in topological order, propagating to each node the full set of its ancestors, namely each direct prerequisite plus that prerequisite's own ancestor set. Precomputing full reachability is the point, since queries become O(1) set lookups, and Floyd-Warshall over a boolean matrix achieves the same in O(n^3).
Given n nodes labeled 0 to n-1 and an undirected edge list, return the number of connected components. Start a counter at n and run union-find over the edges, decrementing once for each union that actually merges two distinct roots. Counting successful merges is the trick, since each one reduces the component count by exactly one, and DFS launches from unvisited nodes work just as well.
Given a graph built by adding one extra edge to a tree of n nodes, return the edge whose removal restores a tree, preferring the one appearing last in the input. Run union-find over the edges in order, and the first edge whose two endpoints already share a root is the answer. That edge closes the unique cycle, and processing in input order automatically satisfies the last-edge tiebreak.
Given accounts as a name followed by a list of emails, merge accounts sharing any email and return each merged account with its emails sorted. Run union-find over the emails, unioning all emails within each account, then group every email under its root representative. Accounts sharing an email are guaranteed to share a name, so the name rides along. Remember to sort each group's emails before output.
Given equations like a / b = k with numeric values, answer queries for the ratio between two variables, or -1.0 when it cannot be derived. Build a weighted graph with an edge from a to b of weight k and a reverse edge of weight 1/k, then DFS from the numerator multiplying weights along the path to the denominator. The path product telescopes into the ratio. Return -1.0 for unknown variables or disconnected pairs.
Given a tree of n nodes as an undirected edge list, return all roots that minimize the resulting tree's height. Repeatedly peel off all current leaves layer by layer, like a reverse BFS from the outside in, until only one or two nodes remain. The survivors are the tree's centers and the answer. Every tree has at most two centers, which is why one or two nodes always survive.
Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence changing one letter at a time through list words, or 0. BFS the implicit graph where words differing by one letter are adjacent, generating neighbors by substituting every position with every alphabet letter. Bidirectional BFS expanding the smaller frontier cuts the branching sharply. The answer counts words rather than steps, and endWord must appear in the list.
Weighted edges change the rules. Dijkstra and its max-edge variants, minimum spanning trees, Bellman-Ford under a stop budget, and Eulerian paths.
Deep dives: Dijkstra's shortest path · Union-Find (disjoint sets)
Given a grid of heights, find a route from the top left to the bottom right minimizing the maximum absolute height difference between consecutive cells. Run Dijkstra where a path's cost is the largest step taken so far, popping the cell with the smallest such cost from a min-heap. The key change is relaxing with the max of current effort and the step difference instead of summing, and binary search on effort plus BFS also works.
Given a directed weighted graph of n nodes and a starting node k, return the time for a signal from k to reach every node, or -1 if some node is unreachable. Run standard Dijkstra from k with a min-heap to get shortest distances to all nodes. The answer is the maximum of those distances, and any unreachable node, detected by a missing distance, forces the -1 result.
Given airline tickets as directed from-to pairs, reconstruct an itinerary starting at JFK that uses every ticket once, choosing the lexicographically smallest valid order. Sort or heap each airport's destinations, then run Hierholzer's algorithm. DFS greedily along unused edges and append an airport to the route only when its destinations are exhausted. The answer is the reversed postorder, and pure greedy walking without the postorder trick can strand itself in a dead end.
Given points on a plane, connect them all at minimum total cost, where an edge costs the Manhattan distance between its endpoints. Build a minimum spanning tree with Prim's algorithm, growing from one point and repeatedly absorbing the cheapest outside point via a min-heap or a distance array. Because the graph is complete with O(n^2) edges, the array form of Prim's is the natural fit, though Kruskal with union-find also passes.
Given an n by n grid of elevations, find the minimum time t that permits swimming from top left to bottom right through cells of elevation at most t. Run Dijkstra where a path's cost is the maximum elevation seen, expanding the cell with the smallest such maximum from a min-heap. The cost is a minimax, not a sum. Binary search on t with BFS, or union-find adding cells in elevation order, also work.
Given a list of words sorted in an unknown alien alphabet, return any valid ordering of the letters, or an empty string if none exists. Compare each adjacent pair of words, taking the first differing characters as a directed edge, then topologically sort the letter graph with Kahn's BFS or DFS. Watch the invalid prefix case where a longer word precedes its own prefix, and a cycle in the graph also means no answer.
Given flights as directed weighted edges, find the cheapest price from src to dst using at most k intermediate stops, or -1 if impossible. Run Bellman-Ford for exactly k+1 rounds, relaxing every edge each round, but read distances from a snapshot copied at the start of the round. The snapshot is the trick. It stops multiple edges from chaining within one round, so round i holds the best price using at most i edges.
Given a weighted undirected graph, classify each edge as critical, meaning every MST must include it, or pseudo-critical, meaning some MST can include it. First compute the baseline MST weight with Kruskal, then for each edge rerun Kruskal once with that edge excluded and once with it forced in first. Exclusion raising the weight or disconnecting the graph marks critical, and forcing it in while matching the baseline weight marks pseudo-critical.
Build a k by k matrix containing 1 through k exactly once, where row conditions force one number above another and column conditions force one number left of another. Topologically sort the numbers twice, once over row conditions and once over column conditions, assigning each number a row index and a column index. The row and column axes never interact, which is the insight, and a cycle in either sort means returning an empty matrix.
Given an array of integers, decide whether every pair of indices connects through a path where adjacent elements share a gcd above 1. Factor each number and union it with a node representing each of its prime factors, then check that all numbers end up in one component. Routing unions through shared primes avoids comparing all pairs. A single element is trivially true, while any 1 in a longer array forces false.
Name the subproblem in one sentence, write the transition, and fill states in dependency order. These are the linear-state problems where that habit gets built.
Deep dives: Dynamic programming
Given n stairs climbable one or two steps at a time, count the distinct ways to reach the top. The count for step i equals the ways to reach i-1 plus the ways to reach i-2, so iterate from the base cases keeping only two rolling variables. Recognize this as the Fibonacci sequence in disguise, giving O(n) time and O(1) space without any memo table.
Given stair costs and moves of one or two steps, return the minimum total cost to reach the top of the staircase, starting from index 0 or 1. Compute dp[i] as cost[i] plus the minimum of the previous two dp values, then answer with the smaller of the final two entries. The subtlety is that the top sits one past the array, so either of the last two stairs can finish the climb.
Given n, return the nth Tribonacci number, where T0 is 0, T1 and T2 are 1, and each later term sums the previous three. Iterate from the base cases, maintaining three rolling variables and shifting them forward each step. The only care points are returning the base cases directly for n below 3 and keeping the variable rotation order straight, giving O(n) time and O(1) space.
Given an array of house values along a street, return the maximum sum obtainable without robbing two adjacent houses. Sweep once, computing for each house the better of skipping it, keeping the previous best, or robbing it, adding its value to the best from two houses back. Two rolling variables capture the whole state, and the invariant is that each position stores the optimal answer for the prefix ending there.
Same robbery setup as House Robber, except the houses form a circle, so the first and last houses are adjacent and cannot both be taken. Run the linear House Robber routine twice, once on the array without the first house and once without the last, returning the larger result. Splitting the circle into two overlapping lines removes the wraparound constraint cleanly. Remember the single-house array as a special case.
Given a string, return the longest contiguous substring that reads the same forwards and backwards. For each of the 2n-1 centers, both single characters and gaps between characters, expand outward while the two ends match, tracking the longest span found. Handling even-length palindromes via the between-character centers is the part people forget, and the expansion runs in O(n^2) time with O(1) extra space.
Given a string, count how many of its substrings are palindromes, counting each occurrence separately. Use the same center expansion as Longest Palindromic Substring. For each of the 2n-1 odd and even centers, expand while the ends match and add one to the count per successful step. Every expansion step is itself a distinct palindrome, which is why counting inside the loop rather than after it gives the exact total in O(n^2).
Given a digit string where 1 maps to A through 26 to Z, count the number of ways to decode it. Walk left to right with dp[i] for the prefix of length i. Add dp[i-1] when the current digit is nonzero, and add dp[i-2] when the two-digit number falls in 10 to 26. Zeros are the whole difficulty, since a lone or invalid 0 kills branches, and two rolling variables suffice for O(1) space.
Given coin denominations with unlimited supply and a target amount, return the fewest coins that sum to the amount, or -1 if impossible. Build dp over amounts 0 through amount, where dp[a] is one plus the minimum of dp[a-coin] over all usable coins. Initialize entries to a sentinel like amount+1 so unreachable values never win the min, and translate a surviving sentinel into -1 at the end.
Given an integer array, return the largest product over all contiguous subarrays. Sweep once tracking both the maximum and minimum product of a subarray ending at the current index, recomputing each from the element alone or the element times the previous max or min. The minimum matters because a negative element turns the most negative product into the most positive one, and a zero resets both trackers naturally.
Given a string and a dictionary of words, decide whether the string can be segmented into a sequence of dictionary words, with reuse allowed. Fill a boolean dp where dp[i] is true when some earlier dp[j] is true and the substring from j to i is in the dictionary, seeding dp[0] as true. Storing the dictionary in a hash set and bounding j by the longest word length keeps the O(n^2) scan fast.
Given an integer array, return the length of its longest strictly increasing subsequence. Maintain a tails array where tails[k] is the smallest tail of any increasing subsequence of length k+1. For each number binary search the first tail at least as large and overwrite it, appending when none exists. The tails array stays sorted, justifying the binary search and the O(n log n) bound, but it is not itself a valid subsequence.
Given an array of positive integers, decide whether it can be split into two subsets with equal sums. Compute the total, return false if odd, then run subset-sum dp asking whether some subset reaches total/2, using a boolean array over sums updated once per number. Iterating the sums downward for each number is essential, since an upward sweep would let one number be reused, and bitset tricks make the inner loop very fast.
Given distinct positive integers and a target, count the sequences of numbers, with reuse allowed, that sum to the target, where different orderings count separately. Build dp over targets 0 through target with the target in the outer loop, adding dp[t-num] for every number that fits, seeded with dp[0] equal to 1. Loop order is the entire point. Target outside counts permutations, while coins outside, as in Coin Change II, would count combinations.
Given an integer n, return the fewest perfect square numbers that sum to n. Fill dp from 1 to n where dp[i] is one plus the minimum of dp[i-s] over every square s up to i, with dp[0] equal to 0. The structure is exactly Coin Change with squares as the coins, giving O(n sqrt n) time, and BFS over amounts, where each level adds one square, finds the answer too.
Given an integer n, split it into at least two positive integers and return the maximum product of the parts. Either fill dp[i] as the max over j of j times the larger of i-j and dp[i-j], or use the fact that optimal splits use only 3s, with a 4 replacing a leftover 1. The pitfall is the small cases, since 2 and 3 must be broken even though keeping them whole would score higher.
Alice and Bob alternately take 1, 2, or 3 stones from the front of a value array, playing optimally. Return who wins or Tie. Define dp[i] as the best score difference the mover can achieve from suffix i, maximizing over the three choices the stones taken minus dp at the next index. Framing the state as a score difference instead of two totals is the trick, and the sign of dp[0] decides the winner.
Two indexes of state. Prefix pairs for string alignment, intervals for games and balloons, and grids where the path itself is the state.
Deep dives: Dynamic programming
Given an m by n grid, count the distinct paths from the top left to the bottom right moving only right or down. Each cell's path count is the sum of the counts above and to the left, so sweep row by row reusing one 1-D array of length n. The first row and column are all ones as base cases, and the closed form is the binomial coefficient choose(m+n-2, m-1).
Same right-or-down path counting as Unique Paths, but some grid cells contain obstacles that block movement. Run the same dp where each cell sums the counts from above and the left, except an obstacle cell is forced to zero paths. The subtle cases are the start cell holding an obstacle, which makes the answer zero, and obstacles in the first row or column cutting off everything beyond them.
Given a grid of non-negative numbers, find the minimum sum of values along a path from top left to bottom right moving only right or down. Fill dp where each cell holds its value plus the minimum of the entries above and to the left, seeding the first row and column as prefix sums. The grid can serve as the dp table for O(1) extra space, and the answer sits in the bottom right cell.
Given two strings, return the length of the longest subsequence, not necessarily contiguous, that appears in both. Fill a 2-D table over prefix pairs where matching characters extend the diagonal value by one, and otherwise the cell takes the max of dropping a character from either string. The diagonal-on-match versus max-of-neighbors split is the whole recurrence, and two rolling rows cut space to O(min(m, n)).
Given stones that smash pairwise, with the smaller destroyed and the difference surviving, return the smallest possible final stone weight. Any smash sequence effectively assigns plus or minus signs to the stones, so the goal is a subset sum as close to total/2 as possible. Run subset-sum dp over reachable sums up to half the total, answering total minus twice the best sum. Seeing through the game disguise is the hard part.
Given daily prices where selling forces a one-day cooldown before the next buy, return the maximum total profit from any number of transactions. Model three states per day, holding a share, just sold, and resting with cash, and write the transitions. Hold comes from holding or buying after rest, sold from holding plus price, and rest from resting or the previous sold. Drawing the small state machine first prevents transition mistakes, and rolling variables give O(1) space.
Given coin denominations with unlimited supply and an amount, count the distinct combinations of coins that make the amount, ignoring order. Use a 1-D dp over amounts seeded with dp[0] equal to 1, putting coins in the outer loop and ascending amounts inside, adding dp[a-coin] to dp[a]. The coin-outer order collapses different orderings into one combination, while flipping the loops, as in Combination Sum IV, would count permutations instead.
Given numbers and a target, count the ways to assign plus or minus to every number so the expression evaluates to the target. Let P be the sum of the positive group. Algebra gives P equals (total+target)/2, so count subsets summing to P with a 1-D counting dp iterated downward. The transformation to subset counting is the trick, and if total plus target is odd or negative, the answer is zero.
Given strings s1, s2, and s3, decide whether s3 can be formed by interleaving s1 and s2 while preserving the internal order of each. Fill a boolean dp over prefix pairs (i, j) where dp[i][j] is true if a matching character from s1 or from s2 extends a true predecessor. Check the length sum first, since unequal lengths fail immediately, and the index into s3 is always i+j, so no third dimension is needed.
Alice and Bob alternately take a pile from either end of a row of piles, playing optimally. Return whether Alice wins. Run interval dp on score difference, where dp(i, j) is the mover's best lead on that interval, taking an end pile minus the opponent's value on the rest. With an even pile count and odd total the first player always wins, so returning true passes, but the interval pattern transfers to harder variants.
Players alternately take the first X remaining piles with X between 1 and 2M, where M starts at 1 and becomes max(M, X). Return Alice's maximum total. Memoize dp(i, M), the best total the mover collects from suffix i, computed as the suffix sum minus the opponent's best over every allowed X. Precomputing suffix sums turns each choice into total minus opponent, avoiding two scores, and when 2M reaches the remaining pile count, take everything.
Given an integer matrix, return the length of the longest path of strictly increasing values moving in the four cardinal directions. DFS from every cell with memoization, where memo[r][c] caches the longest increasing path starting there, built from neighbors holding larger values. The strictly increasing rule means the implicit graph is a DAG, so no visited set is needed and each cell resolves once, giving O(mn) time.
Given strings s and t, count how many distinct subsequences of s equal t. Fill a count table over prefix pairs. When characters match, add the ways that use the match, the diagonal value, to the ways that skip this character of s, the value above, and otherwise carry the skip value alone. Empty t gives one way as the base case, and counts grow enormous, so use a wide integer type.
Given two words, return the minimum number of single-character insertions, deletions, and replacements that transform one into the other. Fill a table over prefix pairs. Matching characters copy the diagonal for free, otherwise take one plus the minimum of the three neighbors, representing insert, delete, and replace. The base cases are the empty prefixes, costing i or j outright. Keeping which neighbor means which operation straight is the usual stumble.
Given balloons with numbers, bursting balloon i scores its value times its two current neighbors. Return the maximum total coins. Pad the array with 1s and run interval dp where dp(l, r) maximizes over the balloon k popped last in the open interval, scoring nums[l]*nums[k]*nums[r] plus the two subintervals. Choosing the last pop rather than the first is the insight, since it fixes k's neighbors as the interval borders and decouples the halves.
Decide whether a pattern, where '.' matches any character and '*' means zero or more of the preceding element, matches an entire input string. Fill a boolean dp over prefix pairs, where a star gives two branches. Zero copies skips the element and star, and one more copy applies when the current character matches. Initializing the empty-string row for patterns like a*b* and tying '*' to its preceding element are the usual failure points.
A greedy solution stands on an exchange argument. The locally best choice never blocks a globally best one. Each problem here teaches a distinct invariant worth saying out loud before coding.
Deep dives: Greedy algorithms
Customers line up paying for five-dollar lemonade with five, ten, or twenty dollar bills, and the task is to report whether correct change can always be given starting with no cash. Track counts of fives and tens, paying out the largest usable bills first for each purchase. The greedy point is that a twenty should be changed with a ten plus a five when possible, since fives are the scarce universal resource.
Given an integer array, return the largest sum of any contiguous subarray. Kadane's algorithm walks the array once keeping a running sum that restarts at the current element whenever the running sum has gone negative, while tracking the best sum seen. The invariant is that a negative prefix can never help a later subarray, so dropping it is always safe, giving O(n) time.
Given a circular integer array, return the maximum possible sum of a nonempty subarray that may wrap around the end. Run Kadane's for both the maximum and the minimum subarray, then take the larger of the plain maximum and total sum minus the minimum, since a wrapping subarray complements a middle minimum. The pitfall is the all-negative array, where total minus minimum describes an empty subarray, so return the plain Kadane answer there.
Given an integer array, return the length of the longest subarray where comparisons between consecutive elements strictly alternate between greater and less. Sweep once, extending the current run when the sign of the new comparison flips from the previous one, and resetting otherwise. The detail to remember is the reset. Equal neighbors reset the run to length one, while a non-alternating strict comparison resets to length two, since that pair starts a fresh run.
Given an array where each value is the maximum jump length from that index, decide whether the last index is reachable from the first. Sweep left to right maintaining the farthest index reachable so far, updating it with i plus nums[i] at every position still within reach. The invariant is that if the sweep ever reaches an index beyond the current farthest reach, the answer is false, and otherwise reaching the end proves true.
Given an array of maximum jump lengths with the end guaranteed reachable, return the fewest jumps to the last index. Sweep with two markers, the end of the current jump's range and the farthest reach seen, and when i crosses the range end, count one jump and extend the range to the farthest reach. This is implicit BFS where each range is one level, so jumps are counted per boundary, not per step.
Given a binary string plus minJump and maxJump, decide whether index 0 can reach the last index when each move lands between minJump and maxJump positions ahead and only on '0' characters. Compute dp[i], whether i is reachable, while maintaining a sliding count of reachable indices inside the window [i-maxJump, i-minJump]. The trick is that the window count makes each dp check O(1), turning a quadratic scan into O(n).
Given gas available at each station and the cost to drive to the next, return the unique starting index that completes the circuit, or -1 if none exists. Check that total gas covers total cost, then sweep with a running tank, restarting the candidate at j+1 whenever the tank goes negative at j. Failing at j eliminates every start between the candidate and j, and a feasible total guarantees the last candidate works.
Given an array of card values and a group size, decide whether the cards can be split entirely into groups of consecutive values of exactly that size. Build a count map, then repeatedly take the smallest remaining card and consume one copy of each of the next groupSize consecutive values, failing if any is missing. The greedy is safe because the smallest card can only ever begin a run, never extend one.
Given a string of 'R' and 'D' senators voting in rounds, where each active senator can permanently ban one opponent, return which party eventually announces victory. Keep two queues of senator indices, repeatedly pop the front of each, let the smaller index ban the other, and re-enqueue the winner at index plus n to fight in the next round. The trick is that earlier position wins each duel, and adding n preserves correct round ordering.
Given a list of triplets and a target triplet, decide whether repeatedly taking elementwise maxima of chosen triplets can produce the target exactly. Filter out any triplet with a coordinate exceeding the target, then check whether the surviving triplets together hit each target coordinate, effectively taking their elementwise maximum. The insight is that a triplet that nowhere exceeds the target is always safe to merge, so only per-coordinate coverage matters.
Given a string, split it into as many parts as possible so each letter appears in one part only, returning the part sizes. Record the last occurrence index of every letter, then sweep while extending the current partition's boundary to the last occurrence of each letter seen, closing the part when i reaches the boundary. The invariant is that the boundary is the farthest last occurrence inside the part, making the close point safe.
Given a string of '(', ')', and '*' where star can act as an open, a close, or nothing, decide whether it can form a valid parenthesis string. Sweep once tracking a range [lo, hi] of possible open-bracket counts, where '(' increments both, ')' decrements both, and '*' decrements lo and increments hi. Clamp lo at zero, fail immediately if hi drops below zero, and accept at the end only when lo is zero.
Given children's ratings in a line, distribute the minimum candies so each child gets at least one and any child rated above an adjacent neighbor gets more. Sweep left to right giving each rising rating one more candy than its left neighbor, then sweep right to left applying the same rule against the right neighbor. The trick is taking the maximum of the two sweep values rather than overwriting, which satisfies both directional constraints.
Sort by the boundary that controls conflicts, then sweep once. Sorting by end time solves scheduling, and sorting by start time solves merging.
Deep dives: Greedy algorithms
Given sorted non-overlapping intervals and one new interval, insert and merge it so the result stays sorted and non-overlapping. Process in three phases. Copy intervals ending before the new one starts, then absorb every overlapping interval by taking min start and max end, then copy the rest. The pitfall is the overlap test. An interval overlaps while its start is at most the merged end, and the merged interval is appended exactly once.
Given an unsorted list of intervals, merge all overlapping ones and return the resulting non-overlapping intervals. Sort by start, then sweep while keeping an active interval, extending its end with max whenever the next start falls at or before the active end, and emitting the active interval otherwise. The detail worth remembering is that extension must use max of the ends, since a later interval can be fully contained inside the active one.
Given a list of intervals, return the minimum number to remove so the remaining intervals do not overlap. Sort by end time, sweep while keeping the interval with the earliest end, count a removal whenever the next interval starts before the current kept end, and otherwise advance the kept end. The exchange argument is the heart. Keeping the earliest-ending interval never hurts, because it leaves the most room for everything after, giving O(n log n).
Given a list of meeting time intervals, determine whether one person can attend them all, meaning no two intervals overlap. Sort the intervals by start time and scan adjacent pairs, returning false the moment a meeting starts before the previous one ends. Sorting reduces the all-pairs overlap question to neighbor checks only, and intervals that touch exactly at an endpoint count as non-overlapping.
Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. Sort the start times and end times separately, then sweep both arrays with two pointers, incrementing the room count when the next start is before the earliest unfinished end and otherwise advancing the end pointer. The answer is the peak count of simultaneous meetings, and the sweep works because only event ordering matters, not which meeting owns which time.
Given n rooms and meetings, each takes the lowest-numbered free room or waits for the earliest room to free, keeping its duration. Return the room hosting the most meetings, lowest index on ties. Sort meetings by start and keep two heaps, free rooms by index and busy rooms by end time then index, releasing finished rooms before each assignment. When a meeting waits, its new end is the freed end time plus the original duration.
Given intervals and queries, return for each query the size of the smallest interval containing it, or -1. Sort intervals by start and process queries in ascending order, pushing every interval whose start is at or below the query into a min-heap keyed by size, then popping entries whose end is below the query. Lazy expiry lets each interval enter and leave the heap once, and answers must be restored to the original query order.
Simulation problems where the win is finding the exact numeric invariant. Matrix layers, carries, modular identities, and exponentiation by squaring.
Given a positive integer, return its Excel column title, where 1 maps to A, 26 to Z, and 27 to AA. Repeatedly take the number mod 26 to get a letter and divide by 26, building the string in reverse. The catch is the 1-based offset. Decrement the number before each mod and divide step, since this is base 26 with digits 1 through 26 rather than 0 through 25.
Given two strings, return the largest string that divides both, where dividing means the string repeated some whole number of times reproduces each input. Check whether s + t equals t + s. If not return the empty string, otherwise return the prefix whose length is gcd of the two lengths. The concatenation test is the whole proof, since the strings share a repeating unit exactly when they commute under concatenation.
Given a linked list of integers, insert between every pair of adjacent nodes a new node holding the gcd of their values, and return the modified list. Walk with a current pointer, compute gcd of current and next values, splice a new node between them, then advance to the old next node. The only real pitfall is the advance step. Skip over the freshly inserted node, or the loop will process it again.
Given a matrix, return its transpose, the matrix flipped over its main diagonal so rows become columns. Allocate a new matrix with the dimensions swapped and set out[j][i] equal to in[i][j] for every cell with a double loop. The thing to remember is that the input can be rectangular, so an in-place swap is impossible in general and the fresh cols-by-rows allocation is required.
Given an n by n matrix of image pixels, rotate it 90 degrees clockwise in place. Transpose the matrix by swapping element (i, j) with (j, i) for j greater than i, then reverse every row. The decomposition is the memorable part. Transpose plus row reversal equals clockwise rotation, while transpose plus column reversal would rotate counterclockwise, and the transpose loop must only touch one triangle or it undoes itself.
Given an m by n matrix, return all elements in spiral order, going right, down, left, then up around shrinking rings. Maintain four boundaries, top, bottom, left, and right, walk one side at a time, and shrink the corresponding boundary after finishing each side. The classic pitfall is a leftover single row or column. Re-check the boundary conditions before the leftward and upward passes, or those elements get emitted twice.
Given an m by n matrix, set the entire row and column of every zero cell to zero, in place. Use the first row and first column as marker space, recording separately whether each originally contained a zero, then zero interior cells from the markers and handle the first row and column last. The ordering is the trick, since clearing the first row or column too early destroys the markers for everything else.
Given a positive integer, decide whether repeatedly replacing it with the sum of the squares of its digits eventually reaches 1, which makes it happy. Generate the digit-square sequence and detect repetition, either with a seen set or with Floyd's fast and slow pointers stepping through the sequence. The insight is that the sequence always falls into a cycle, so this is pure cycle detection, where reaching 1 means happy and any other cycle means not.
Given a number represented as an array of its digits, add one and return the resulting digit array. Walk from the last digit toward the front, setting any 9 to 0 and continuing, and otherwise incrementing the digit and returning immediately. The only special case is a carry surviving past the front, as in 999, where a new leading 1 must be prepended to a now all-zero array.
Given a Roman numeral string, return the integer it represents. Map each symbol to its value and scan the string, adding each value but subtracting it instead whenever the symbol to its right has a strictly larger value. That subtraction rule handles all six subtractive pairs like IV and CM uniformly, with no special casing, and the final symbol is always added since nothing follows it.
Given a double x and an integer n, compute x raised to the power n. Use exponentiation by squaring. Square x while halving n, multiplying the result in whenever the current exponent bit is odd, which runs in O(log n). Handle negative n by inverting x and negating n, and remember the edge case that negating the minimum 32-bit integer overflows unless done in a wider type.
Given two non-negative integers as strings, return their product as a string without using big-integer libraries or direct conversion. Allocate a result array of length m+n, and for each digit pair multiply d1 by d2, adding the product into positions i+j and i+j+1 with carry handling. The position fact is the whole solution. Digit i times digit j always lands in those two slots, and leading zeros must be stripped at the end.
Design a structure with add, which stores a point allowing duplicates, and count, which returns how many axis-aligned positive-area squares have the query point as a corner. Store point counts in a hash map, and for each query scan stored points as diagonal partners, multiplying the counts of the two remaining corners. A valid partner differs by the same nonzero amount in x and y, and the diagonal fixes the other corners, so counts multiply.
A small toolbox that shows up everywhere. XOR cancellation, clearing the lowest set bit, and building answers bit by bit from the top.
Given an array where every element appears exactly twice except one that appears once, return the single element. XOR all the numbers together. The result is the answer, computed in one pass with O(1) extra space. It works because XOR is commutative and associative and any value XORed with itself cancels to zero, leaving only the unpaired number.
Given an unsigned 32-bit integer, return the number of set bits in its binary representation, its Hamming weight. Loop applying n = n & (n-1), counting iterations until n becomes zero. The identity is that AND-ing n with n minus one clears exactly the lowest set bit, so the loop runs once per set bit instead of once per bit position.
Given an integer n, return an array where entry i is the number of set bits in i, for every i from 0 to n. Fill the array in order with the recurrence dp[i] = dp[i >> 1] + (i & 1), which reuses the count for i shifted right one bit. The insight is that shifting right drops only the lowest bit, so adding that bit back gives the count in O(n) total.
Given two binary strings, return their sum as a binary string. Walk both strings from their last characters with a shared carry, summing up to three bits per step, appending sum mod 2, and carrying sum divided by 2, then reverse the result. The loop condition should keep running while either index remains or the carry is nonzero, which cleanly handles different lengths and a final carried 1.
Given a 32-bit unsigned integer, return the integer whose binary representation is the bit-reversed form of the input. Loop exactly 32 times, shifting the result left one position, OR-ing in the input's lowest bit, then shifting the input right. The loop must run all 32 iterations regardless of leading zeros, since those zeros become trailing zeros in the answer and skipping them misaligns everything.
Given an array containing n distinct numbers drawn from 0 to n, return the one number in that range that is missing. XOR every array value together with every index from 0 to n. All present numbers pair with their matching index and cancel, leaving the missing one. The sum formula n(n+1)/2 minus the array sum works equally well, and both run in O(n) with O(1) space.
Given two integers, return their sum without using the plus or minus operators. Loop computing the partial sum as XOR of the two values and the carry as their AND shifted left one, then repeat with those two until the carry becomes zero. XOR adds bits without carrying while AND finds the carry positions, and in languages with unbounded integers like Python the values must be masked to 32 bits to terminate on negatives.
Given a signed 32-bit integer, return it with its decimal digits reversed, or 0 if the reversal overflows the 32-bit range. Pop the last digit with mod 10, push it onto the result with multiply by 10 plus digit, and divide the input by 10 each round. The overflow check must happen before the push, comparing the result against INT_MAX / 10, since checking after the multiplication is already too late.
Given two integers left and right, return the bitwise AND of every integer in the inclusive range between them. Shift both endpoints right together, counting shifts, until they become equal, then shift that shared value back left by the count. The result is the common high-bit prefix of left and right, because every bit below the first disagreement takes both values 0 and 1 somewhere in the range and gets ANDed away.
Given integers n and x, build a strictly increasing array of n positive integers whose bitwise AND equals x, and return the smallest possible last element. Every element must contain all of x's set bits, so candidates are x with extra bits in x's zero positions, and the kth smallest writes k into those gaps. The answer is x with the bits of n-1 filled, lowest first, into x's zero positions.