Algorithms

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; 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; 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; 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; 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; 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; 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: 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: 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; 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.

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; 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; taking the maximum of its current position and the jump target keeps 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.

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: the 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: 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; 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; 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; 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.

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 what interviews probe; 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: 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: 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; 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); 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; 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; 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; 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: 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; 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; without them a single traversal cannot pin down the structure.

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: 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: 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: 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: when the numbers remaining past the current start cannot fill the open slots, cut the branch immediately rather than exploring it.

Given an array of distinct integers, return every possible permutation. Since order matters a start index no longer works; 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: 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: add an open parenthesis while open is below n, and add 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; 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; 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; 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.

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: 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; 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; 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; 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; 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: if it is a deadend, return -1 immediately.

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; 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; 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; 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.

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; 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; 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; 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; 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; 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; 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; the sign of dp[0] decides the winner.

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; 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.

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: 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: 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: reaching 1 means happy, 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.