Start here: the must-solve set

You need a pair of values summing to a target on unsorted input, and you want indices back — that pairing-by-value need is the hash-map signal. For a current value x, the only partner that works is target - x. If you remember every value you have already passed (mapped to its index), you can check that partner in O(1) as you go.

1. Scan the array once, tracking each value and its index in a map
2. At value x, compute the complement target - x
3. If the complement is already in the map, return its stored index and the current index
4. Otherwise record x and its index and continue

You must cluster items that are 'equal' under some normalization (reordering letters). Whenever equality is defined by a canonical form, map that canonical form to a bucket. Two words are anagrams exactly when their sorted letters match, so the sorted string is a fingerprint. Use that fingerprint as a dictionary key and append each word to its bucket.

1. Create an empty map from canonical key to list of words
2. For each word, build a canonical key (its sorted characters)
3. Append the word to the list under that key
4. Return all the map's value lists

Each output depends on everything except one position, and division is banned — that points to combining a running product from the left with one from the right. The product excluding index i equals (product of everything to its left) times (product of everything to its right). Both can be swept in linear time and multiplied together.

1. Fill answer[i] with the product of all elements strictly to the left, using a running prefix
2. Sweep from the right with a running suffix product
3. Multiply each answer[i] by the suffix so far, then extend the suffix
4. Return answer

You need the longest chain of consecutive values in O(n), and sorting (O(n log n)) is too slow — that rules in a hash set with membership tests. Only start counting a run from a value that has no predecessor (x - 1 absent). From such a starter, walk upward as long as the next value exists; each element is visited at most twice overall.

1. Put all numbers in a set for O(1) membership
2. For each value x, skip it unless x - 1 is absent (so x begins a run)
3. From a starter, count upward while x + length is present
4. Track the maximum run length found

You must find combinations that hit a fixed sum (0) and the order of elements does not matter, so sorting plus a two-pointer sweep is far cheaper than trying every triple. Sort first; then fix the smallest element of the triplet and reduce the rest to a 2Sum-on-a-sorted-array problem, moving two pointers inward based on whether the current sum is too small or too large.

1. Sort nums so pointers can move monotonically
2. Fix each index i as the first element, skipping duplicate values
3. Set lo = i+1 and hi = n-1 and scan toward each other
4. Move lo up when the sum is negative, hi down when positive, record and skip duplicates when it is zero

You want the best pair over all index pairs where value depends on the gap between them and the smaller of two endpoints, which screams two pointers starting at the widest gap. Start at the maximum possible width and always move the pointer at the shorter line inward, since keeping the shorter line can never beat what we just measured while width only shrinks.

1. Place left at 0 and right at n-1 to start with maximal width
2. Compute the area as width times the shorter of the two heights and update the best
3. Move the pointer at the shorter line inward
4. Repeat until the pointers meet

You are asked for the longest contiguous stretch that satisfies a 'no duplicates' constraint over a string or array — a variable-size window over a sequence. Grow a window to the right; when the incoming character duplicates one already inside the window, jump the left edge to just past that character's previous position so the window is valid again.

1. Track the last index where each character was seen
2. For each right index, if the char was seen at or after the current start, move start to last+1
3. Update the last-seen index of the current char
4. Record the best window length (right - start + 1)

Longest substring where you may 'fix' up to k mismatches — the window is valid while (window length - count of its most frequent letter) <= k. In any window, the characters you must replace are all the non-majority ones. If that number of replacements exceeds k, the window is invalid, so shrink from the left.

1. Extend the window one character to the right and update its frequency
2. Track the highest single-character frequency seen in the window (max_freq)
3. While window_len - max_freq > k, shrink from the left
4. Record the largest valid window length

Smallest window that must cover a required multiset of characters — expand to satisfy, then contract to minimize. Grow the window until it contains all required characters, then shrink from the left as far as possible while it still contains them, recording the smallest such window.

1. Count required characters of t in a need map and set missing = len(t)
2. Expand right: if the char was still required, decrement missing
3. While missing == 0, record the window if it is the shortest so far, then release the left char and move left forward
4. Return the best window found (empty string if none)

You are counting contiguous subarrays with a target sum, and values can be negative so a sliding window fails — count prefix sums in a hash map instead. A subarray (j, i] sums to k exactly when prefix[i] - prefix[j] = k. So for the running prefix P, every earlier prefix equal to P - k ends a qualifying subarray; count how many times each prefix value has occurred.

1. Keep a running prefix sum and a map from prefix value to how many times it has occurred, seeded with {0: 1}
2. At each element, add it to the prefix
3. Add the count of prefix - k already seen to the answer
4. Record the current prefix in the map

A sorted array that has been rotated, plus an explicit O(log n) requirement, signals a modified binary search rather than a linear scan. At any midpoint, at least one of the two halves [lo..mid] or [mid..hi] is still perfectly sorted; check whether target lies inside that sorted half to decide which way to move.

1. Compute mid and return it if nums[mid] equals target
2. Determine which side of mid is sorted by comparing nums[lo] and nums[mid]
3. If target lies within the sorted side's range, search that side; otherwise search the other side
4. Repeat until lo passes hi, then return -1

Finding the minimum (or the pivot) of a rotated sorted array in log time is the canonical 'search for the inflection point' pattern. The minimum is the only element smaller than its predecessor; comparing nums[mid] to nums[hi] tells you which side the unsorted drop (and therefore the minimum) lives on.

1. Set lo and hi to the array ends
2. While lo < hi, compute mid
3. If nums[mid] > nums[hi], the minimum is strictly right of mid, so lo = mid + 1
4. Otherwise the minimum is at mid or left, so hi = mid
5. Return nums[lo] when the window collapses

You are asked for the minimum rate/capacity such that a task fits a limit, and 'faster works, slower fails' is monotonic, which is the textbook signal for binary search on the answer. If speed k lets Koko finish in time, any speed greater than k also does; this monotonicity lets you binary-search the smallest feasible k instead of trying every value.

1. Set the search range to [1, max(piles)] since eating faster than the biggest pile never helps
2. For a candidate speed mid, compute total hours as the sum of ceil(pile / mid)
3. If hours <= h the speed is feasible, so shrink hi to mid; else raise lo to mid + 1
4. Return lo, the smallest feasible speed

Nested or interleaved bracket matching where the most recently opened bracket must close first is the textbook signal for a LIFO stack. The last opening bracket seen is the first one that must be closed, so a stack of unmatched openers lets you verify each closer against the correct partner in O(1).

1. Scan each character left to right
2. Push opening brackets onto the stack
3. On a closing bracket, pop and confirm it matches; fail if the stack is empty or the types differ
4. After the scan, the string is valid only if the stack is empty

You are asked, for each element, how far away the next strictly greater element is. 'Next warmer / next greater' over an array is the canonical monotonic-stack signal. Keep a stack of indices whose warmer day has not been found yet, ordered by decreasing temperature. When a hotter day arrives it resolves every colder day sitting on top of the stack at once, and the gap in indices is the wait.

1. Initialize answer with zeros and an empty stack of indices
2. For each day, while the stack's top is colder than today, pop it and record the index gap as its wait
3. Push today's index onto the stack
4. Indices never resolved keep their default 0

Maximizing a rectangle bounded by bar heights, where each bar can extend left and right until it hits a shorter bar, is the classic monotonic-stack histogram problem. A bar of height h can widen left and right until it meets the first strictly shorter bar on each side. If we process bars left to right with an increasing stack, popping a bar tells us its right boundary, and the index stored beneath tells us its left boundary.

1. Maintain a stack of (start_index, height) pairs in increasing height order
2. When the current bar is shorter than the stack top, pop it and compute area = height x (current_index - start)
3. Carry the popped start index leftward so the shorter current bar can extend back over that span
4. After the scan, settle remaining bars using the array length as the right boundary

You are asked to combine overlapping ranges into a minimal covering set — the classic cue to sort intervals by start and merge neighbors. Once intervals are sorted by start, any interval that overlaps the current group must start before the group's running end; so only the most recent merged interval can ever absorb the next one.

1. Sort intervals by start value
2. Walk through them keeping a running merged list
3. If the current start is <= the last merged interval's end, extend that end
4. Otherwise append the current interval as a new group

The input is already sorted and non-overlapping and you must place one new range in — a signal for a single linear pass split into before/overlap/after phases. Because the list is already sorted, all intervals ending before the new one come first untouched, all intervals overlapping the new one form one merged block, and everything after is copied verbatim.

1. Copy every interval that ends before newInterval starts
2. While intervals overlap newInterval, expand newInterval to cover their union
3. Append the merged newInterval
4. Copy every remaining interval unchanged

Minimizing removals to make intervals disjoint is the classic activity-selection problem — maximize how many you keep, remove the rest. To pack the most non-overlapping intervals, always keep the one that finishes earliest; it leaves the most room for the intervals that follow.

1. Sort intervals by end value ascending
2. Track the end of the last interval you kept
3. If the next interval starts at or after that end, keep it and update the end
4. Otherwise it overlaps, so count it as a removal

Asking for the maximum number of simultaneously active intervals (the peak concurrency) is the signature of a sweep line or a min-heap of end times. Sort meetings by start; a min-heap holds the end times of meetings currently occupying rooms, and the heap size at its peak is the number of rooms you need.

1. Sort meetings by start time
2. Keep a min-heap of end times of ongoing meetings
3. For each meeting, pop any meeting that has already ended (end <= current start) to free its room
4. Push the current meeting's end; the maximum heap size is the answer

The prompt asks to invert the direction of a singly linked list in place with no value copying — the classic signal for the prev/curr/next reversal walk. You only ever need three references: the node before you (prev), the node you are rewiring (curr), and a saved handle to the rest of the list (next) so you don't lose it when you flip curr.next.

1. Initialize prev to None and curr to head
2. Save curr.next before overwriting it
3. Point curr.next back to prev
4. Advance prev and curr one step
5. When curr is None, prev is the new head

You must decide if traversal ever repeats a node using O(1) memory — the textbook cue for the tortoise-and-hare technique. If a cycle exists, a pointer moving two steps will lap a pointer moving one step and land on the same node; if there is no cycle, the fast pointer simply runs off the end.

1. Start slow and fast at the head
2. Advance slow by one and fast by two each iteration
3. If fast reaches None or fast.next is None, there is no cycle
4. If slow and fast ever reference the same node, return true

A reorder that interleaves the front of the list with its reversed back half signals the compound find-middle + reverse + merge routine. Splitting at the middle gives a front half and a back half; reversing the back half lets you zip the two halves together one node at a time to achieve the front-back-front-back weave.

1. Find the middle with slow/fast pointers and cut the list into two halves
2. Reverse the second half in place
3. Merge the two halves by alternating nodes from each
4. Because the operation is in place, the function returns None

You must deep-copy a structure with arbitrary cross-links (random pointers), so you need a way to map each original node to its clone — a hash map or pointer interleaving. If you first create every clone and remember original -> clone, then wiring each clone's next and random is just a dictionary lookup on the corresponding original pointer.

1. First pass: create a clone for every original node and store it in a dict keyed by the original
2. Second pass: for each original, set clone.next and clone.random via dict lookups
3. Use dict.get so None pointers map cleanly to None
4. Return the clone of the original head

A cache needing O(1) lookup plus O(1) eviction of the least recently used item points to a hash map paired with a recency-ordered doubly linked list (or Python's OrderedDict). A hash map gives O(1) access by key; a doubly linked list ordered by recency gives O(1) move-to-most-recent and O(1) removal of the oldest — Python's OrderedDict bundles both.

1. Store entries in an OrderedDict where the front is least recently used and the back is most recently used
2. On get, if the key exists move it to the back and return its value, else return -1
3. On put, insert/update the key and move it to the back
4. If size exceeds capacity, pop the front (oldest) item

You are asked for a single number that depends on the whole subtree beneath each node — a classic signal for a post-order DFS that combines children's results. A tree's depth is 1 (for the current node) plus the larger of its two subtree depths; an empty tree contributes depth 0.

1. If the node is null, return 0
2. Recurse on the left child to get its depth
3. Recurse on the right child to get its depth
4. Return 1 + max(left, right)

You want the longest path between any two nodes, and the best path 'bends' at some node — a signal to compute heights bottom-up while checking each node as a potential turning point. The longest path that turns at a node equals leftHeight + rightHeight (in edges); computing heights once lets you test every node as the turning point in a single pass.

1. Define a height helper that returns edge-height of a subtree
2. At each node compute leftHeight and rightHeight
3. Update a global best with leftHeight + rightHeight
4. Return 1 + max(leftHeight, rightHeight) as this node's height
5. Return the best after the traversal

The output is grouped by depth and read left-to-right — the defining signal for breadth-first search processing one full level at a time. If you record the queue's size at the start of each iteration, that count is exactly the number of nodes on the current level, so you can carve the stream into levels.

1. Return [] if root is null
2. Push root into a queue
3. Loop while the queue is nonempty
4. Snapshot the queue length as the current level size and pop exactly that many, collecting values and enqueuing their children
5. Append the collected level to the result

You must check ordering against an entire subtree, not just immediate children — the cue to pass down an allowed (low, high) value window. A node is valid only if it falls strictly inside an open interval; descending left tightens the upper bound to the node's value, descending right tightens the lower bound.

1. Start the root with bounds (-inf, +inf)
2. At each node check low < node.val < high
3. Recurse left with high updated to node.val
4. Recurse right with low updated to node.val
5. A null node is trivially valid

You need the deepest node from which both targets are reachable — a signal to bubble 'found' signals up from the leaves and detect where the two paths meet. If one target appears in a node's left subtree and the other in its right subtree, that node is the meeting point; a node that is itself a target and finds the other below it is also the answer.

1. Return the node if it is null, equal to p, or equal to q
2. Recurse into the left subtree
3. Recurse into the right subtree
4. If both sides return non-null, the current node is the LCA
5. Otherwise return whichever side is non-null

You are given preorder plus inorder of a tree with unique values — the textbook setup where the preorder head names the root and inorder splits left from right. The first element of preorder is always the current root; its position in inorder partitions inorder into the left subtree (before it) and right subtree (after it), and their sizes tell you how to slice preorder.

1. Map each inorder value to its index for O(1) lookup
2. Consume preorder left-to-right with a moving pointer for the next root
3. Locate the root in inorder to find the split
4. Recursively build the left subtree, then the right subtree
5. Return the assembled node

You need the best path that can bend at a node (go down-left and down-right) but a node can only extend one branch upward to its parent — that split between what you return and what you record is the tell. For each node compute the maximum downward gain of a single branch. The best path THROUGH a node is node.val + left_gain + right_gain, but the value you hand back to the parent can only include one branch, because a path cannot fork twice.

1. Recurse post-order to get each child's max single-branch gain
2. Clamp negative gains to 0 so harmful branches are dropped
3. Update a global best with node.val + left + right (the bent path)
4. Return node.val + max(left, right) to the parent (one branch only)

You must fully capture tree shape AND values in a flat string and rebuild unambiguously — the classic fix is to emit explicit null markers so structure is never guessed. A pre-order walk that writes a sentinel for every missing child makes the sequence uniquely decodable: reading the same pre-order stream lets a recursive builder consume values in exactly the order they were written.

1. Serialize: pre-order DFS, append each value, append '#' for null children
2. Join tokens into a comma-separated string
3. Deserialize: split into tokens and read them with an iterator
4. Rebuild recursively — '#' becomes None, otherwise create a node and build its left then right

You need the kth largest (or smallest) element but not a full ordering — a signal to keep only the k best seen so far in a heap. If you keep a min-heap that never grows past size k, its smallest element (the root) is always the kth largest among everything processed. Anything smaller than the root can never be the answer once k bigger values exist.

1. Push each element onto a min-heap
2. Whenever the heap exceeds size k, pop the smallest
3. After processing all elements the root is the kth largest

Repeatedly querying the middle of a growing, unsorted stream signals splitting the data into a lower half and an upper half kept in balance. Keep the smaller half in a max-heap and the larger half in a min-heap. The two roots straddle the middle, so the median is one root or the average of both — available in O(1) after O(log n) inserts.

1. Push the new number into the max-heap (lower half)
2. Move that heap's largest into the min-heap to keep order between halves
3. Rebalance so the max-heap has equal size or one extra
4. Median is the max-heap root, or the average of both roots when sizes are equal

The prompt asks for ALL subsets / the power set of a small array (n <= 10), which is the canonical signal for exhaustive backtracking rather than a formula. Each element is an independent binary choice: include it or not. Walking that decision tree with a start index guarantees every subset is generated exactly once and in non-decreasing index order, so no duplicates arise.

1. Record the current path as a subset at the top of every call
2. Loop i from a start index to the end of nums
3. Choose nums[i], recurse with start = i + 1, then un-choose (pop) to explore the sibling

Asking for all combinations summing to a target WITH repetition allowed is the signature; the small target bound makes exhaustive search viable. Reuse is modeled by recursing with the same index i (not i + 1), letting a candidate repeat; passing i as the new start still forbids going back to earlier candidates, which prevents permutation-style duplicates like [2,3] and [3,2].

1. Track the remaining amount still needed
2. When remaining hits 0, record a copy of the path
3. Loop from the current start; skip a candidate larger than remaining, else pick it and recurse with the SAME index i so it can repeat

Asking for ALL orderings / arrangements (not combinations) of a tiny array is the permutation-backtracking signal; here order matters, so no start index is used. A permutation uses every element exactly once, so unlike subsets we scan all indices each level and only skip those already placed. A used[] boolean array marks which elements are currently in the path.

1. When the path length equals n, record a copy as a finished permutation
2. Loop over every index; skip indices whose used flag is set
3. Mark used, append, recurse, then unmark and pop to restore state

Searching a grid for a sequence along adjacent cells with a no-reuse rule is textbook DFS backtracking from every possible start cell. Try each cell as the first letter; from a matching cell, recurse into its four neighbors for the next letter. Temporarily overwrite the visited cell with a sentinel so the current path cannot step on it, then restore it on the way back so other start paths remain valid.

1. If the whole word is matched (k == len(word)) return True
2. Reject out-of-bounds cells and cells not equal to word[k]
3. Mark the cell visited, recurse into all four neighbors for word[k+1], then restore the cell and return whether any branch succeeded

You are asked to count connected components in a 2D grid where adjacency is 4-directional; that is a flood-fill problem. Each time you find an unvisited land cell it must start a new island, so scan the grid, and whenever you hit land, drown the entire connected region so it is never counted again.

1. Scan every cell of the grid
2. When you meet an unvisited '1', increment the island count
3. Run DFS from that cell, flipping every reachable '1' to '0' to mark it visited
4. Continue the scan; each fresh '1' starts exactly one new island

You must reproduce a graph's structure exactly while creating fresh objects; the challenge is handling cycles, which signals a visited/clone map. Map each original node to its single clone the first time you see it; whenever an edge points to an already-cloned node, reuse that clone so shared references and cycles are preserved.

1. Handle the empty input by returning None
2. Create the clone of the start node and record it in a map
3. BFS over originals; for each neighbor not yet cloned, create its clone and enqueue it
4. Wire clone-of-current to clone-of-neighbor for every edge

You need the shortest time for something to spread from multiple starting points at once, which is textbook multi-source BFS measuring levels. Seed the queue with every rotten orange, then expand one full ring per minute; the number of rings processed until all fresh oranges rot is the answer.

1. Enqueue every rotten orange and count fresh ones
2. Process the queue level by level, each level being one minute
3. Rot fresh neighbors, decrement the fresh count, enqueue them
4. After the loop, return the minutes if no fresh remain, else -1

Pairwise 'must come before' constraints over labeled items is a dependency graph, and 'can it all be done' means 'is the directed graph acyclic'. A course with no remaining prerequisites can be taken now; taking it removes it as a prerequisite for others. If you can keep finding such courses until none are left, there was no cycle.

1. Build a directed graph pre -> course and count in-degrees (number of unmet prerequisites)
2. Seed a queue with every course whose in-degree is 0
3. Pop a course, mark it done, and decrement the in-degree of its dependents, enqueuing any that reach 0
4. Return true only if the number of courses processed equals numCourses

You are adding edges one at a time and asked which edge first joins two nodes that were already connected. Detecting the moment two components merge (or fail to) is the signature of Union-Find. Process edges in order and union their endpoints. The first (and here only) edge whose two endpoints already share a root does not connect anything new, so it is the redundant edge that closes the cycle.

1. Initialize a parent array so every node is its own root
2. For each edge (a, b), find the roots of a and b
3. If the roots are equal, this edge creates a cycle, return it
4. Otherwise union the two roots and continue

Shortest travel time from a single source in a graph with non-negative edge weights is the textbook signal for Dijkstra. The answer is the maximum of the shortest distances from k to every node. Dijkstra settles nodes in increasing distance, so the first time we pop a node its distance is final.

1. Build an adjacency list from times
2. Push (0, k) into a min-heap and pop the closest unsettled node
3. Skip already-settled nodes; otherwise fix its distance and relax its neighbors
4. After the heap empties, return the max distance if all n nodes were reached, else -1

You want a maximum sum over a linear array with a 'no two chosen elements are adjacent' rule -- the classic signal for take-or-skip DP. At each house the best total is either the best up to the previous house (skip this one) or this house's money plus the best up to two houses back (take this one).

1. Track best-so-far excluding the previous house (prev) and best-so-far including it (curr)
2. For each house compute max(curr, prev + money)
3. Shift the two variables forward
4. Return the final curr

Minimizing the count of items chosen with unlimited repetition to hit an exact total is the unbounded-knapsack / coin-change signature. The fewest coins for amount a is one more than the fewest coins for a - c, minimized over every coin c that fits.

1. Create dp of size amount+1 with dp[0]=0 and the rest set to an unreachable sentinel
2. For each amount a from 1 up, try every coin c <= a
3. Set dp[a] = min(dp[a], dp[a-c] + 1)
4. Return dp[amount], or -1 if it stayed unreachable

'Longest increasing subsequence' (order preserved, not contiguous) plus a desire to beat O(n^2) points at the patience-sorting + binary-search technique. Maintain the smallest possible tail value for an increasing subsequence of each length; a smaller tail leaves more room to extend later.

1. Keep a list tails where tails[k] is the smallest tail of an increasing subsequence of length k+1
2. For each x, binary-search the first tail >= x
3. If none exists, append x (extends the longest run); otherwise overwrite that tail with x
4. The length of tails is the answer

Two sequences and a question about the best way to match/align them while preserving order is the classic signal for a 2D 'grid over the two strings' DP. Compare the last characters. If they match, that character can end the LCS, so add 1 to the LCS of the two shorter prefixes; if not, the answer is the better of dropping the last character of one string or the other.

1. Build a table dp[i][j] = LCS length of text1[:i] and text2[:j], with row/column 0 as zeros
2. For each pair of prefix lengths, if the current characters match set dp[i][j] = dp[i-1][j-1] + 1
3. Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. Return dp[m][n]

Transforming one string into another with per-character insert/delete/replace costs is the textbook edit-distance grid DP. Aligning prefixes, if the last characters match nothing is spent; otherwise the last move is one of insert, delete, or replace, each reducing the problem to a slightly smaller prefix pair, so take the cheapest.

1. Define dp[i][j] = edits to turn word1[:i] into word2[:j]
2. Seed dp[i][0]=i (delete all) and dp[0][j]=j (insert all)
3. If characters match, copy the diagonal dp[i-1][j-1]
4. Otherwise take 1 + min(delete dp[i-1][j], insert dp[i][j-1], replace dp[i-1][j-1])
5. Return dp[m][n]