Algorithm Cheatsheet

If some quantity only ever moves in one direction as you change an input — a window grows and its sum only grows, an index grows and a predicate flips false → true exactly once — you can almost certainly replace brute force with binary search, two pointers, or a monotonic stack.

Ask this first, always: "What's monotone here?" Before you write a single line of code, name the thing that only grows, only shrinks, or only flips once. If nothing is monotone, brute force (or DP) is probably unavoidable — but check twice, because monotonicity is often hidden — see Binary Search further down: a yes/no "is X achievable?" check can be monotone even when nothing in the input is sorted.

State, in one sentence, what is true at the top of every iteration:

• "Everything left of i is sorted."
• "The stack holds indices with strictly increasing values."
• "seen contains every value from nums[0..i-1]."

If you can't write that sentence, the code is probably wrong. If you can, the correctness proof (and the edge cases) follow with little extra work — the invariant tells you what must hold before the loop starts (base case) and what the loop body must preserve (inductive step).

For DP, BFS, backtracking, and memoization, the state is the minimum information that makes the rest of the problem independent of how you got there (the Markov property — the path to a state doesn't matter, only the state itself).

• Too much state → almost no two calls share a state, so the cache never hits and you recompute everything: TLE (Time Limit Exceeded).
• Too little state → two genuinely different situations collide in the cache, wrong answers.

The design skill of DP is finding the smallest state that's still sufficient.

"Count things with property P" is often easier as:

This pays off whenever "does not have P" (or "has at most B", when P is "has exactly B") has a simple, direct one-pass count, even though "has P" itself does not.

Worked example — Number of Sub-arrays With Odd Sum (LC 1524): checking every subarray's sum directly for odd or even is O(n^2). Counting the complement — subarrays with an even sum — takes one pass instead:

Other complement-shaped problems:

Many "novel" problems are a classic problem wearing a costume:

Before designing a new algorithm, spend 30 seconds asking "have I seen this shape before, under a different name?"

Always write the O(n²) or O(2ⁿ) brute force in your head (or on paper) first. Then ask exactly one question:

• "Where am I recomputing the same thing?" → prefix sums, memoization, hashing.
• "Which branches can never win, so I can stop exploring them?" → pruning, greedy, monotonic stacks.

The optimized algorithm is almost always the brute force with one of those two questions answered.

Before you pick a technique for an array or string problem, decide one thing: does the position of each element matter, or only its value? The answer decides whether you may sort the input, whether a hash set is enough, and whether you must keep every element where it is.

The problem statement tells you. A few words carry the answer.

Key phrase decoder

Side by side: similar words, different rules

Problem names that sound alike can sit on opposite sides of this line.

Values versus positions

• Longest Consecutive Sequence (LC 128). Key phrase: "longest consecutive elements sequence". Order matters? No. "Consecutive" is about values (1, 2, 3, 4), not positions. Best approach: put every value in a hash set and look each neighbour up in O(1), for O(n) time and O(n) space. Or sort the array in place, for O(n log n) time and O(1) extra space.
• Longest Continuous Increasing Subsequence (LC 674). Key phrase: "continuous increasing subsequence". The word "subsequence" is misleading here: "continuous" makes it a subarray. Order matters? Yes. Each element must sit right after the previous one and be larger than it (nums[i] < nums[i + 1]). Best approach: one linear scan that counts the current run, for O(n) time and O(1) space.

Subarray versus subsequence

• Maximum Subarray (LC 53). Key phrase: "subarray". Order matters? Yes. You cannot reorder elements, and you cannot skip an element in the middle of the run. Best approach: Kadane's algorithm, for O(n) time and O(1) space. See Kadane's Algorithm in Part 2.
• Longest Increasing Subsequence (LC 300). Key phrase: "strictly increasing subsequence". Order matters? Yes, but only the relative order. You may skip elements. The elements you keep must stay in their original left-to-right order. Best approach: dynamic programming in O(n²) time, or the binary-search method (often called "patience sorting") in O(n log n) time.

Values versus index output

• Two Sum (LC 1). Key phrase: "return the indices of the two numbers". Order matters? Yes, because the answer is made of positions. If you sort the input in place, you lose the original positions. Best approach: a hash map from each value to its index, for O(n) time and O(n) space.
• Two Sum II - Input Array Is Sorted (LC 167). Key phrases: "sorted in non-decreasing order", "return the indices". Order matters? Yes, for the indices. But the input is already sorted, so no sort is needed and no position is lost. Best approach: two pointers, one at each end, for O(n) time and O(1) space.

Quick self-check

Ask these two questions before you write code.

1. "If I shuffle the input, does the answer change?"
   • No: order does not matter. Use a hash set, sorting, or counting.
   • Yes: order matters. Go to question 2.
2. "If I skip an element, does the condition break?"
   • Yes: the problem is about a subarray or substring. Use a sliding window or two pointers.
   • No: the problem is about a subsequence, or about a set of values. Use dynamic programming, a monotonic stack, or a hash set.

Invariant: monotonic expansion until valid, monotonic contraction until optimal. This only works when validity is monotone in window size (Principle #1 above).

Mental trick: ask "if I move the right pointer right, does my metric change in only one direction?" If yes — sliding window beats brute force O(n²) scanning.

Note on defaultdict(int) vs Counter(): the window above tracks distinct by hand instead of calling len(counts), because neither defaultdict(int) nor Counter() deletes a key once its count drops to 0 — len(counts) would keep counting characters that left the window. The at_most(k) helper right below takes the other approach: it deletes a key the moment its count hits 0, so len(count) stays accurate and there's no separate counter to maintain. See the Python Cheatsheet's defaultdict/Counter comparison for the full breakdown of when each style applies.

One-time trick — "exactly K" from "at most K", as in Subarrays with K Different Integers (LC 992):

Why right - left + 1 counts every subarray ending at right: once the window [left, right] is valid (e.g. "at most K distinct values"), every shorter piece of it that still ends at right is valid too, because shrinking a valid window from the left can only remove values, never add new ones. Say the window currently holds [A, B, C] with left at A (index 0) and right at C (index 2). The subarrays ending at C and contained in this window are [C], [B, C], and [A, B, C] — exactly 3 of them, which is exactly right - left + 1 = 2 - 0 + 1 = 3. So adding right - left + 1 at every step right takes counts every valid subarray ending at that right, for every right in the array, with no nested loop and no double-counting: each subarray has exactly one rightmost index, so it is added exactly once, on the step where right reaches that index.

Why count += right - left + 1 counts subarrays correctly: every time the window expands by moving right forward by one, you aren't just adding one new element — you are creating a whole new batch of subarrays that all end at that new element. If the window from left to right is valid, then any subarray that ends at right and starts anywhere between left and right is also valid. There are exactly right - left + 1 such starting points, so there are exactly right - left + 1 new valid subarrays to count.

If a window expands across an entire array of size N without ever shrinking, the running total of right - left + 1 at each step adds up to 1 + 2 + 3 + ... + N, which is exactly N(N+1)/2 — the total number of subarrays in the array. The at_most trick above applies this same formula at every step, but the while loop's shrinking subtracts out the invalid combinations as it goes, so the running total only ever counts subarrays that are still valid.

Invariant: moving a pointer inward permanently eliminates an entire row or column of impossible combinations — you never have to check them again.

Mental trick: on a sorted array, if array[left] + array[right] > target, even the smallest partner still in play (array[left]) is too big for array[right] — so right can't pair with left or anything between them. Decrement right and you've eliminated that whole set of candidates in O(1). The same squeeze solves Two Sum II - Input Array Is Sorted (LC 167), which wants 1-based indices (add 1 to each index below):

One-directional squeeze — matching a subsequence, as in Is Subsequence (LC 392): the two pointers don't have to move toward each other. Walking t once and only advancing in s on a match is the same "eliminate and never reconsider" idea — once a character of s is matched, that match is locked in and the pointer in s never moves backward:

Invariant: binary search does not require a sorted array. It requires a monotonic predicate — a true/false condition that flips exactly once and stays flipped.

Binary search on the answer: if checking "is X achievable?" is cheap and monotone, binary search X even when nothing in the input is literally sorted (minimum max-load, minimum ship capacity, minimum eating speed…).

Mental trick — keep the answer inside [lo, hi]: start lo at the smallest value that could possibly work and hi at one that surely works. While lo < hi: if mid works, set hi = mid (the answer is mid or smaller); otherwise set lo = mid + 1. When they meet, lo is the answer. Capacity To Ship Packages Within D Days (LC 1011):

Counting without building the structure, as in Kth Smallest Number in Multiplication Table (LC 668): the table has up to m * n cells, far too many to build when m and n are large, but row i holds exactly the multiples of i (i, 2i, 3i, ...), so the count of that row's values at most x is x // i, capped at n since the row only has n columns. Summing that count over every row answers "how many table entries are at most x?" in O(m), so bisect the value x for the smallest one whose count reaches k:

Summary of Key Concepts

• Positions vs. Indices: Binary search for bounds operates on insertion positions (the gaps between elements), not just direct array indices. An array of length $N$ has $N + 1$ possible positions, ranging from $0$ to $N$.
• The Right Boundary (hi): Setting hi = len(nums) allows the algorithm to return $N$, representing the valid position past the end of the array when the target is larger than all elements. Capping hi at len(nums) - 1 truncates this valid boundary.
• Post-Search Access: The final lo pointer can equal len(nums). Evaluating nums[lo] without a bounds check will cause an IndexError.

Solid Rules of Thumb

Rule 1: Always set hi = len(nums) for bounds. Use lo = 0 and hi = len(nums) to ensure the search space covers all $N + 1$ potential insertion positions. Never subtract $1$ from hi unless you are strictly searching a fixed numerical value range rather than array boundaries. (The closed-interval exact-match template, hi = len(nums) - 1 with while lo <= hi, is a different template: it looks for one index, not a boundary position.)

Rule 2: Separate "Position Finding" from "Value Verification".

• For Bounds / Insertion: Treat lo as a coordinate index. Do not assume nums[lo] equals your target. It only points to the boundary element (the first element $\ge$ target for bisect_left, or the first element $>$ target for bisect_right).

Step-by-Step Implementation Guide

1. Initialize the search space: set lo to the start of the position space ($0$) and hi to the end of the position space (len(nums)).
2. Run the standard binary search loop: loop while lo < hi, calculating mid = (lo + hi) // 2.
3. Shift pointers based on the condition:
   • Lower Bound (bisect_left): if nums[mid] >= target, move hi = mid. Otherwise, move lo = mid + 1.
   • First index > target (bisect_right): if nums[mid] > target, move hi = mid. Otherwise, move lo = mid + 1. This is still a first-True search, even though C++ calls it upper_bound; the last index with a value <= target is this position minus 1 (the Upper Bound, or last True, card).
4. Validate before accessing elements: to check whether the target actually exists, see find_exact in Example 2.

Concrete Examples

Example 1: Finding the Lower Bound (Insertion Position)

• Array [1, 3, 5, 7], target 6: returns 3 (pointing to 7). The position is valid, but checking nums[3] gives 7 (not 6), confirming the target isn't in the array.
• Target 8: returns 4 (len(nums)), the position past the end.

Example 2: Exact Value Verification

Invariant: how you arrived at a state doesn't matter — only what resources remain at that state matters (see Principle #3).

Why the recurrence is correct: dp[a] is correct once every dp[a - c] for each coin c is already correct, because the last coin used to reach a is independent of how the remaining amount a - c was paid. The loop computes dp[a] only after every smaller amount is already filled in, so that dependency is always satisfied.

Mental trick — finding the recurrence: think about the last decision, not the first. "What is the final choice in an optimal solution?" usually hands you the recurrence directly: the last item taken or skipped, the last cut position, the last character matched. Coin Change (LC 322):

When to reach for this: "Number of ways to…", "minimum/maximum cost to reach…", "fewest steps to…", or any count/optimum over all ways to build up to a target — these phrasings signal dynamic programming.

Space trick: if dp[i] only ever depends on dp[i-1] (or a fixed window of previous rows), you don't need the full table — keep only the last one or two rows. Climbing Stairs (LC 70):

Workflow: write the top-down version with @lru_cache first — it mirrors the recurrence directly and is nearly bug-free. Convert to bottom-up when you need the space optimization, or when the recursion gets deep: here the depth grows with amount, and in Python the version below raises RecursionError from a few hundred levels, while Coin Change (LC 322) allows amount up to 10^4. The bottom-up coin_change above has no such limit.

Optional follow-up tip: the top-down @lru_cache version and the bottom-up dp array compute the exact same values, in the exact same dependency order, because @lru_cache only returns a cached value once that value has already been fully computed — the cache never serves a half-finished answer. That is why both versions agree on every input.

Invariant: at every recursive call, the state is exactly what it was before the call once the call returns — nothing leaks between sibling branches.

Pruning tricks:

• Sort first, then you can break instead of continue, and skip duplicate branches with if i > start and a[i] == a[i - 1]: continue.
• Check the cheapest constraint first — fail fast before paying the cost of recursing.

Subsets II (LC 90):

The 3 Dimensions of Backtracking, and the One-Way Door Principle

Every backtracking call is really making three independent decisions at once. Naming them separately is what makes a broken backtracking solution debuggable:

1. Decision space — enumerate the branches (the for loop's range).
2. Pruning gate — the if that decides whether a branch is even worth entering (duplicate skip, capacity check, validity check).
3. State mutation & reversal — path.append(x) paired with path.pop(); board[r][c] = 'X' paired with board[r][c] = '.'; visited.add(node) paired with visited.remove(node).

The One-Way Door Principle: every mutation must be a two-way door, one you can walk back through before the next sibling runs; a mutation whose undo can be skipped is a one-way door.

With nums = [2, 3, 5, 6] and target = 8 this returns [[2, 3, 5, 6], [2, 3, 3, 5]] instead of [[2, 6], [3, 5]]. The fix is to test the pruning gate before the mutation (if nums[i] > remaining: break, then path.append(nums[i])), so there is nothing to undo on that exit.

How to audit any backtracking function for a one-way door: for every mutation (append, dict/set insert, grid write, counter increment), trace every exit path out of the recursive call — the normal fall-through, every early return, every continue, every exception — and confirm the matching undo runs on all of them. If even one exit path skips the undo, that mutation is a one-way door and the algorithm is silently wrong, usually in a way that only shows up on inputs where that early-exit branch actually fires.

Invariant: making the locally optimal choice never restricts your ability to reach the globally optimal solution.

How to verify greedy is even legal — the exchange argument: "If I swap my greedy choice for whatever an optimal solution chose instead, does the outcome ever get worse?" If swapping never hurts, greedy is provably correct. If swapping can restrict future flexibility, you need DP instead — greedy is not "DP's lazy cousin," it's a much stronger claim that requires its own proof.

Almost every correct greedy starts with a sort. Ask "sort by what?" first — by end time, by ratio, by deadline. Non-overlapping Intervals (LC 435) asks for the fewest removals, which is len(intervals) minus the count below:

Invariant: elements wait in the stack, in sorted order, until a "dominant" element arrives and evicts them. The instant an element is popped, the element that popped it is the answer for it.

The next-greater pass below is the building block of Next Greater Element I (LC 496):

A monotonic deque is the same idea generalized to sliding windows: it holds the candidates that could still possibly win, in decreasing order, and pops from the front once a candidate ages out of the window. Sliding Window Maximum (LC 239):

Reflexes:

Why BFS finds the shortest path when every edge has the same weight: BFS visits the nodes at distance 1 from the source, then every node at distance 2, then every node at distance 3, and so on, one whole layer at a time. Because every node at distance d is visited before any node at distance d + 1, the first time BFS reaches a node is always by the fewest possible number of edges from the source.

When to reach for this: "fewest edges/steps/moves between X and Y", "shortest path, unweighted" — these phrasings signal plain BFS.

Why Dijkstra needs non-negative weights: Dijkstra repeatedly pops the node with the smallest tentative distance and treats that distance as final. That step is only safe because adding any non-negative edge weight to an already-final distance can never produce something smaller than the next-smallest tentative distance — so no path discovered later can ever beat it. If an edge weight is negative, a longer path found later could still turn out shorter, so that popped distance would no longer be guaranteed final.

Optional follow-up tip: when every edge weight is only 0 or 1, 0-1 BFS gets Dijkstra's correctness at BFS's speed — push a 0-weight edge's neighbor to the front of a deque and a 1-weight edge's neighbor to the back, instead of paying for a heap.

The graph is often implicit — states are nodes, moves are edges, and you never build an adjacency list explicitly. Word Ladder (LC 127), sliding-puzzle, knight's-move problems are all just BFS over an implicit state graph.

Kahn's algorithm turns the topological-sort reflex above into code: track each node's in-degree (how many prerequisites point to it), start a queue with every node that has in-degree 0 (no prerequisites left), and every time a node is processed, decrement its neighbors' in-degree — any neighbor that drops to 0 is now ready and joins the queue. If the queue empties before every node is processed, a cycle exists and no valid order exists. Course Schedule (LC 207):

Invariant: dynamic connectivity without ever storing explicit edges. Every node points toward a single representative (the root) for its group.

Mental trick — merging companies, not employees: you don't link every employee to every other employee in their department. You just merge the two CEOs at the top. Everyone underneath is still "connected" through the chain of parent pointers.

Reverse the timeline: if a problem asks you to delete edges and track connectivity, it's usually easier to process deletions in reverse — start from the fully-deleted graph and add edges back with Union-Find, since Union-Find can merge but never split.

Quick lookup table for "I recognize this shape, what tool do I reach for?"

Invariant: a hash set or hash map turns "does this related value exist anywhere in the input?" into an O(1) lookup, so you can detect the shape of a run, a cycle, or a matching pair in one pass instead of sorting or rescanning.

Mental trick — Hash Set Sequence Builder / Start-of-Sequence Check, as in Longest Consecutive Sequence (LC 128): put every number in a set. Then, for a number x, only start counting a run from x when x - 1 is not in the set. x - 1 not being in the set means no number can extend the run backward past x, so x must be the first number of its run. Checking this for every number guarantees each run is counted exactly once, from its start, in O(n) total — no sorting, no rescanning a run you already counted.

Related trick — Complement Lookup, as in Two Sum (LC 1): scan once, and store each number's index in a hash map as you go. Before inserting the current number, check whether target - current is already a key in the map. If it is, the current number and that earlier number sum to target, found in one pass because the partner was already recorded when it was seen.

Related trick — Seen-Set Cycle Detection, as in Happy Number (LC 202): repeatedly transform the number (sum of squares of its digits) and add every result to a seen-set. If a result repeats, the sequence has entered a cycle and will never reach 1, so the number is not happy. The set remembers every state the sequence has visited, so a repeat is detected in O(1) the moment it happens.

Cross-reference — the classic linked-list framing of this same cycle check: detecting a cycle in a linked list (LC 141, Linked List Cycle) is the same problem as Happy Number above, but it is usually solved without a seen-set. Floyd's cycle detection uses two pointers that move at different speeds instead: a slow pointer moves one node at a time, and a fast pointer moves two nodes at a time. If the list loops, the fast pointer closes the gap to the slow pointer by exactly one node every step, so it must eventually land on the same node as the slow pointer. Use the seen-set version above when O(n) extra space is fine. Use the slow/fast version when the problem needs O(1) space, or is phrased directly as linked-list traversal rather than a sequence of transformed values.

Related trick — Prefix State + First-Occurrence Index, as in Contiguous Array (LC 525): track a running value while scanning once (here, count of 1s minus count of 0s seen so far), and store the first index where each running value occurred in a hash map. If the same running value occurs again at a later index, every element between those two indices added up to zero net change, so that span is a contiguous subarray with an equal number of 0s and 1s — found in one O(n) pass.

Invariant: the best subarray ending exactly at index i either extends the best subarray ending at i-1, or restarts at i alone — whichever running sum is larger.

Mental trick — reset or extend: at every index, ask "does keeping the running sum help, or does starting over here beat it?" The moment the running sum drops below the current element taken alone, nothing before this index can help any future subarray, so drop it and restart from here.

Optional follow-up tip: for the circular version (Maximum Sum Circular Subarray, LC 918), the wrap-around case equals the total sum minus the minimum subarray sum — the same complement-counting idea from Principle 4. Run Kadane once for the maximum, and once more with every sign flipped to find the minimum.

Invariant: if one value appears more than n // 2 times, every other value can be paired off and cancelled against it one-for-one, and the majority value is still the one left standing at the end.

Mental trick — count is a tally of survivors, not occurrences: every time count hits zero, the current candidate has been fully cancelled out by everything seen so far, so whoever is next in line becomes the new candidate. Because the majority value outnumbers everyone else combined, it can never be fully cancelled out before the array ends.

Optional follow-up tip: if the problem does not guarantee a majority element exists, add a second pass that counts candidate's actual occurrences before trusting the result.

Invariant: three regions coexist in place during the whole scan: everything before low is the small bucket, everything from low to cur - 1 is the middle bucket, everything after high is the large bucket, and the only unclassified region is [cur, high].

Mental trick — one swap settles one element forever: when nums[cur] belongs in the small bucket, swap it to the front and grow low. When it belongs in the large bucket, swap it to the back and shrink high without advancing cur — the value just swapped in from the back has not been classified yet. When it belongs in the middle, just advance cur. Every swap places one element in its final region, so the whole array sorts into three buckets in one pass.

Optional follow-up tip: this is three-way partitioning, the same primitive quicksort uses to handle duplicate pivot values without the quadratic slowdown that plain two-way partitioning hits on arrays with many repeated values.

Invariant: when every value is known to come from a fixed range (commonly 1..n or 0..n-1), value v has exactly one correct home index, so repeatedly swapping each value into its home index sorts the whole array in O(n) time with no extra space.

Mental trick — keep swapping the current slot until it is correct, then move on: at each index, if the value sitting there is not already in its own home, swap it into its home and check that same index again. Only advance once the value at the current index actually belongs there. Every swap sends one value to its final position, so no swap is ever undone.

Optional follow-up tip: the same swap-into-place idea finds every duplicate or every missing number in a 1..n-range array (LC 442, LC 448) in O(n) time and O(1) extra space.

Invariant: after one partition step around a pivot, every element to the pivot's left satisfies the ordering condition against the pivot and every element to the right satisfies the opposite, so the pivot's final index alone tells you whether the Kth element is to the left, to the right, or is the pivot itself — and the other side can be discarded without ever being sorted.

Mental trick — discard a whole side, the same way binary search does: after one partition step you know exactly which side the answer lives in, so the next step only recurses into that side. Just like two pointers eliminates a whole row of impossible pairs at once (Principle 1), partitioning eliminates an entire side of the array in one pass, giving average O(n) instead of fully sorting at O(n log n).

Optional follow-up tip: a deterministic pivot (always the first or last element) is correct but hits O(n^2) on sorted input. Randomizing the pivot index is what keeps the average case O(n) in practice.

Invariant: during the merge step of merge sort, every time an element from the right half is placed before elements still waiting in the left half, each of those waiting left-half elements forms exactly one inversion with it — and merge sort already visits every such pair without comparing all O(n^2) pairs directly.

Mental trick — count the pairs, do not enumerate them: brute force checks every pair directly, O(n^2). Merge sort already groups and compares halves in O(n log n); the trick is noticing that the number of left-half elements still waiting when a right-half element gets placed is exactly the number of new inversions that element causes, so that count can be added for free during the merge you were already doing.

Optional follow-up tip: the same "count during the merge" trick, applied to the condition nums[i] > 2 * nums[j] instead of plain inversions, solves Reverse Pairs (LC 493).

Invariant: an n-bit integer is a complete description of one subset of an n-element set — bit i set means element i is included — so looping an integer from 0 to 2^n - 1 visits every subset of the set exactly once.

Mental trick — the integer IS the subset: do not track a separate set structure at all; the bits of the integer already are the membership flags. mask & (1 << i) checks whether element i is in this subset. mask ^ (1 << i) flips element i in or out. mask & (mask - 1) clears the lowest set bit, which is how popcount loops once per 1-bit instead of once per bit position.

Optional follow-up tip: bitmask DP (state = which elements have been used so far, as in the Traveling Salesman subset DP) combines this trick with Principle #3 — the mask itself is the minimal state.

Invariant: rotating an n x n matrix 90 degrees is the same permutation as transposing it (flip across the main diagonal) and then reversing every row — two operations that each only ever swap two cells at a time, so the whole rotation needs no second matrix.

Mental trick — decompose the rotation into two reversible, in-place steps: rather than compute each cell's rotated destination directly, split the rotation into "transpose" (swap matrix[i][j] with matrix[j][i] for every i < j) and "reverse each row", both of which only ever swap two cells at a time, so no extra matrix is ever needed.

Coordinate proof: (i, j) goes to (j, i) under transpose, then reversing row j sends it to (j, n-1-i), which is exactly where a 90-degree clockwise rotation puts it.

Optional follow-up tip: rotating 90 degrees counter-clockwise is the same transpose followed by reversing each column instead of each row (equivalently, reverse each row first and transpose second).

Optional follow-up tip: the same coordinate proof works backward to check any rotation code: pick one cell, follow it through each step by hand, and confirm its final position matches the rotation you intended.

Invariant: after processing the ith element (1-indexed) of a stream, every element seen so far has exactly the same probability, 1/i, of being the one currently held as the sample.

Mental trick — give the newcomer a fair shot, then let the math carry the rest: at step i, the new element should end up being the sample with probability 1/i. Replacing the current sample with probability 1/i, and proving by induction that every earlier element also ends at probability 1/i, is why one pass with O(1) extra space produces a uniformly random sample without knowing the stream's length in advance.

Induction step: an earlier element survives through step i only if it was already the sample before step i, and step i does not replace it. By the induction hypothesis, the probability it was already the sample is 1/(i-1). Step i does not replace it with probability 1 - 1/i. So the probability it survives through step i is (1/(i-1)) * (1 - 1/i), which equals 1/i — the same probability as the new element at step i. This keeps every element's odds equal at every step.

Optional follow-up tip: sampling k elements instead of 1 generalizes the same rule — keep the first k elements, then for the ith element after that, replace a uniformly random slot in the reservoir with probability k/i.

Invariant: every node represents one prefix, and all words sharing that prefix share that node and everything above it, so checking or inserting a word costs one step per character, never one comparison per existing word.

Mental trick — walk one character at a time, creating nodes only where the path does not exist yet: inserting or searching a word of length L costs O(L), completely independent of how many other words are already stored, because a shared prefix is only ever visited once no matter how many words use it.

Optional follow-up tip: a trie beats a hash set whenever the problem needs prefix queries ("every word starting with…", autocomplete, word search on a board) — a hash set only answers "does this exact string exist?", not "does anything start with this?".

Invariant: the doubly linked list's order IS the recency order (most-recently-used at one end, least-recently-used at the other), and the hash map gives O(1) access into that list by key, so both "find by key" and "move to most-recent" are O(1).

Mental trick — neither structure alone is enough, so combine them: a hash map alone gives O(1) lookup but no ordering. A linked list alone gives O(1) reordering but O(n) lookup by key. Pairing them — the map stores key to node, each node carries key and value and sits inside the list — gives O(1) for both operations at once.

Optional follow-up tip: Python's collections.OrderedDict (move_to_end plus popitem(last=False)) implements this exact hash-map-plus-linked-list pairing internally, so it is a legitimate one-line LRU cache in an interview if the interviewer allows standard-library data structures.

Invariant: every node of the tree represents the answer (sum, min, max, …) for one contiguous range, and that range is exactly the union of its two children's ranges, so any range query or point update only ever touches O(log n) nodes instead of the O(n) a prefix sum array would need to rebuild.

Mental trick — trade a little query speed for fast updates: prefix sums answer queries in O(1) but cost O(n) per update. A segment tree trades that O(1) down to O(log n) per query in exchange for O(log n) per update instead of O(n) — the right trade whenever the array changes between queries. Range Sum Query - Mutable (LC 307):

Optional follow-up tip: a sparse table answers range-min/range-max queries in O(1) after an O(n log n) build, but only for arrays that never change — it cannot support updates, which is exactly the case a segment tree is built for.

Invariant: when a match fails at position j in the pattern, the failure function already tells you the longest proper prefix of the pattern that is also a suffix of what you have matched so far, so comparing can resume from there instead of restarting the pattern from index 0.

Mental trick — never re-examine a text character you have already matched: naive string matching can re-scan the same text character up to O(m) times after a failed match, giving O(n * m) overall. The failure function precomputes, for every pattern position, how much of the match can be reused after a mismatch, so the text pointer never moves backward — O(n + m) total.

Optional follow-up tip: the same failure function, read as "the longest prefix of the whole string that is also a suffix of it", directly answers Shortest Palindrome (LC 214) and other prefix/suffix-overlap problems.

Invariant: a window's hash can be updated in O(1) when the window slides by one position, because removing the leftmost character and adding a new rightmost character is a fixed arithmetic adjustment, not a full re-hash of the window.

Mental trick — treat the window as a number in a chosen base, and sliding it is one multiply-and-add: a string is just digits in base B (its character codes). Recomputing that number after a one-character slide is the same O(1) operation as computing (n * 10 + next_digit) mod M while reading a decimal number one digit at a time. That is why a rolling hash finds a pattern match candidate in O(1) per position instead of O(m) per position.

Optional follow-up tip: the same rolling hash, applied to every fixed-length window instead of one specific pattern, finds repeated substrings in one pass — Repeated DNA Sequences (LC 187).

Gotcha — the direct-comparison fallback is load-bearing, and a fixed modulus is not safe against adversarial input: text[i:i + m] == pattern is the step that confirms a hash match is a real match. Skipping it would let a hash collision silently report a match where none exists, because two different windows can share the same hash value under a fixed modulus. A fixed, small modulus like MOD = 10**9 + 7 is also not safe in an adversarial setting: an attacker who knows the modulus in advance can construct input that collides on purpose. Production string-matching code uses a randomized modulus chosen at runtime, or combines two independent hashes (double hashing), so the modulus cannot be guessed in advance.

Invariant: a condition phrased as "exactly V" (exactly K distinct values in the window, exactly K odd numbers, the window's maximum is exactly inside one specific bound) usually has no clean shrinking-window or counting rule on its own — tracking both a lower and an upper boundary of the same quantity at once is awkward. The weaker condition "at most V" almost always does have a clean rule, and every window satisfying "exactly V" is counted once by "at most V" and zero times by the next threshold down, so:

Mental trick — stack two weaker counts and let subtraction isolate the exact one: instead of writing a counter that tracks both "has V been reached" and "has V been exceeded" at the same time, write the simple, one-directional "at most" shrinking window once, then call it twice at adjacent thresholds. The same template generalizes to "between A and B inclusive" with two calls at the two ends of the range instead of one: count(between A and B) = at_most(B) - at_most(A - 1).

Already worked out elsewhere in this cheatsheet, so not repeated here:

• Subarrays With K Different Integers, exactly K (LC 992) — the full at_most(k) shrinking window and the exactly(k) = at_most(k) - at_most(k - 1) call are in the Sliding Window section above ("exactly K" from "at most K").
• Number of Subarrays with Bounded Maximum (LC 795) — the two-sided generalization bounded(left, right) = at_most(right) - at_most(left - 1) is in the Complement Counting section above.

Invariant: a requirement is met the instant its running count equals its quota — checking with == instead of >= means every requirement is counted as fulfilled exactly once, at the exact moment it is fulfilled, no matter how many extra duplicates arrive afterward.

The trick: the secret sauce is the strict == operator:

By checking have[c] == counter_t[c] instead of >=, you ensure that your matched score increments exactly once per unique character type. If you used >=, absorbing extra duplicate characters (e.g., getting a 5th 'A' when you only needed 2) would continuously inflate your matched count. This would trick your algorithm into thinking it had found all the necessary letters (like 'B' and 'C') when in reality, it just found a massive pile of 'A's. The == threshold guarantees you only get credit the exact moment a character's specific quota is fulfilled.

Shortest-window template: this is the shrinking half of the sliding window (Section 1) specialized for "find the shortest window that satisfies every requirement" — it expands right to absorb elements, then shrinks left while every requirement stays satisfied, recording the shortest valid window along the way. Minimum Window Substring (LC 76) is the canonical problem.

Invariant: Section 7's single monotonic deque gives the sliding window's maximum (or minimum) in O(1), but a window validity check that depends on both ends at once — "is max(window) - min(window) still within limit?" — needs both the current maximum and the current minimum live at the same time. Running two independent monotonic deques side by side, one decreasing (max_dq) and one increasing (min_dq), keeps both answers at O(1) without ever falling back to a heap or re-scanning the window.

A heap/priority-queue would also answer "what's the current max?", but a heap cannot cheaply remove an element that has aged out of the window from the middle of the structure — that's O(log n) lazy deletion, or a full rebuild. A monotonic deque's trick (Section 7) is that anything an element invalidates is also everything that element makes irrelevant to evict later, so both the front (the answer) and the back (what to purge first) stay O(1) to reach — twice, once per deque.

Mental trick — two independent bully lines, one shared left pointer: max_dq and min_dq each run Section 7's single-deque algorithm completely independently — an element entering the window gets pushed onto both, popping whatever it bullies out of each. The only thing that connects them is the shrinking step: the window is only valid once both fronts agree it's within limit, and shrinking left must evict stale indices from both deques, not just one — an index can fall out of the window and go stale in one deque before the other, since each deque keeps a different subset of indices alive.

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438):

Complexity: O(n) time — every index is pushed onto each deque exactly once and popped from each deque at most once, so the total work across both deques is O(n), not O(n log n). O(n) space for the two deques of indices in the worst case (a strictly monotonic nums never bullies anything out, so every index stays).

Optional follow-up tip: this same "run Section 7's single monotonic deque twice, once per side" pattern generalizes to any window-validity check that needs two running extremes at once, not just this specific absolute-difference bound.

Invariant: a sentinel is a value that is not in the input. It is added at the start or the end so that the first and last elements follow the same rule as every other element. The loop then needs no separate if for the edges.

Missing Ranges (LC 163) shows the idea. The sorted array nums holds unique integers, and every number from lower to upper that is not in nums must be reported as a range. A gap can exist before the first element, between two elements, or after the last element. Without sentinels, that is three separate cases.

The loop runs len(nums) + 1 times. The extra last iteration compares the last real element with the virtual right anchor upper + 1.

An empty nums also works. The loop runs once with curr = upper + 1, so process_ranges([], 1, 1) returns [[1, 1]].

Trap: forgetting an offset. prev = lower drops a missing lower, and upper instead of upper + 1 drops a missing upper. Both anchors sit one step outside [lower, upper] so that prev + 1 and curr - 1 land exactly on the ends of the range.

Where else the same idea appears:

Complexity: O(n) time, one pass over nums. O(1) extra space, apart from the result list.

Graphs, Union-Find, prefix sums and difference arrays have their own lookup tables in sections 8 and 10.