# LeetCode Bible

Patterns edition

Learning to derive, explain, and implement algorithms in Rust

Edition 1.0 | 6 October 2026

This book is a working guide to solving unfamiliar algorithm problems independently. It explains the observations that make techniques useful, the conditions that make them correct, and the changes that make them fail. Read it with a notebook and an editor. The exercises are part of the book.

The patterns edition covers the main interview algorithm families and selected practice problems. It does not contain every LeetCode problem or reproduce the platform's problem statements. Problem links lead to the original statements. The companion repository provides implementation references; consult them after your attempt.

The book's Rust functions are standalone teaching implementations. Their Option return values and slice-based interfaces may differ from LeetCode's required submission signatures. Adapt the interface without changing the algorithm's contract.

The explanations, examples, practice sequence, and exercises here were written for this book. Research citations distinguish evidence about learning from practical recommendations. No number of completed problems guarantees mastery.

Book text: CC BY-SA 4.0. Original code examples and build tools: MIT. See the source package for license texts, attribution, and contribution instructions. Referenced third-party materials retain their own licenses. This is an independent educational project, unaffiliated with LeetCode.


## 1 How to use this book

The goal is a skill you can repeat: read a problem you've never seen, find an approach, make it fast enough, explain why it works, and write the code without anyone handing you the key idea.

Study in two modes. In learning mode, read a chapter, study a worked example, and solve a related problem, with help if you need it. In test mode, hide the tags and notes, mix topics you've studied, and try a problem you haven't seen. Keep track of the two separately. Solving a problem after a hint is progress, but it's not the same as solving it alone.

For each problem you're learning from, follow these steps:

1. Restate the input, the output, the limits, and any unclear cases.
2. Work a small example by hand.
3. Describe a simple solution that's clearly correct, and its cost.
4. Find exactly which work it repeats or doesn't need.
5. Look for a fact about the input that removes that work.
6. Say what your solution keeps true at each step, and why each step is safe.
7. Write the code, trace it by hand, and test it.
8. Close the explanation and rebuild the reasoning yourself.
9. Come back a few days later and use the idea on a different problem.

Start with 20–30 minutes of real effort before taking a hint, and adjust for your experience and the problem. Keep going as long as you're still coming up with new ideas. When a technique is completely new to you, study a worked example first. These time limits and review gaps are coaching advice, not tested rules, and strong competitors disagree about when to read the solution [S4].

When you review, write out the reasoning before you look at code. Try reviewing after a day or two, then a week, then a few weeks, and adjust to how well you remember. Experiments show that practicing recall after a delay helps memory, though the classic study used prose, not code [S6].

In a 60-minute session, try 10 minutes recalling old problems, 30 minutes on a new one, 15 minutes explaining or rebuilding a solution, and 5 minutes writing down the idea you missed. Once you know several techniques, mix them in one session. Mixing topics helps in math experiments; that it helps with choosing algorithms is a reasonable guess, not a tested result [S7].

**Keep a progress log.** For each problem, write down: whether you solved it alone or with help, your first wrong assumption, the idea you missed, what the solution keeps true, your coding mistake, and a variation to try next. Write what you can actually do, such as "explained why the left pointer never moves back", not a vague confidence score.

## 2 Derive and justify a solution

Every speedup should fix a specific problem in a slow solution that already works. "Too slow" isn't specific enough. Ask: does it search old elements again and again? Recompute a sum that overlaps the last one? Explore different paths that lead to the same place? Keep options that can never beat another option?

Take the problem of finding two values that add up to a target. Checking every pair is O(n²). But for each value x, the real question is "have I seen target − x before?" A hash map answers that without searching. The arithmetic gives you the key to look up, and the lookup tells you to use a hash map.

Now take the largest sum of a subarray. If the running sum so far is negative, adding it to anything that comes next only makes that smaller. Starting fresh is always at least as good. To justify dropping an option like this, compare it with the alternative under every possible future. If it's never better, you can drop it.

To show a loop is correct, name something it keeps true, then check three things:

1. **It starts true** before the first step.
2. **Each step keeps it true.**
3. **When the loop ends,** that fact gives you the answer.

"The window is valid" isn't enough to prove you found the best answer. You also have to explain why the windows you skipped couldn't have been better.

For recursion, say exactly what one call takes and returns. Assume smaller calls do their job, and show how their results give you this call's answer. For a greedy choice, show that swapping in your choice never makes the answer worse. For dynamic programming, show that your state holds everything the rest of the problem needs, that your transitions cover every case, and that you fill the table in an order where each value's inputs are ready.

Count the cost from what the code actually does. A loop inside a loop isn't always O(n²). If a pointer moves forward at most n times over the whole run, those moves add up to O(n). In the other direction, slicing, copying, hashing a long string, or copying a path adds work you can't see from the loops.

| Growth | What it usually means |
| --- | --- |
| O(n) | Each element gets a fixed amount of work in total. |
| O(n log n) | Sorting, or a logarithmic update for each item. |
| O(n squared) | Every pair, or n states with n choices each. |
| O(2 to the n) | Include or skip each item; only works for small n. |
| O(n factorial) | Every order of the items. |
| O(V + E) | Visit each node and each edge of a graph a fixed number of times. |

The limits in a problem rule out some approaches, but they don't pick one for you. No single operation count works as a cutoff across languages, machines, and judges. Remember to count the size of the output and the recursion stack too.

## 3 Reasoning moves that unlock problems

These questions turn "which technique is this?" into something concrete you can check. Each one suggests an idea to try. None of them replaces checking your assumptions or showing the solution is correct.

### Ask what the rest of the problem needs to know

Two different histories can share a state only if everything that can happen next is the same for both. To find whether you can reach a cell in a grid, you only need the current cell. But if doors need keys, you also need which keys you hold. To plan purchases, you may need the remaining budget and your position, but not the order of earlier purchases.

Try this sentence: "If I tell you these variables, can you solve the rest without knowing how I got here?" If not, find the missing variable. If so, look for repeated states and save their answers. A good state is information you've safely forgotten.

### Name the question your loop keeps asking

Before you pick a data structure, say the question in plain words: "Have I seen this value's partner?", "What's the earliest index with this prefix sum?", "Which task finishes first?", or "How many earlier values are below this one?"

Those questions point to a hash map, a hash map that keeps the earliest index, a heap, and a sorted counting structure. Naming the question also separates problems that look alike: "is it there", "how many", "what rank", and "what's smallest" are different questions.

### Change how you represent the input

A different representation can reveal a pattern that the story hides. To find runs with equal numbers of zeros and ones, turn each 0 into −1. A balanced run then sums to zero. Turn allowed moves into graph edges. Turn time intervals into start and end events.

In [LC 525 Contiguous Array][p525], a repeated prefix sum of the converted list marks a balanced run, and keeping the earliest index of each sum gives the longest one. The discovery is the conversion plus the prefix sum lookup. "Use a hash map" alone misses it.

### Fix one part and solve the rest

3Sum fixes one value, then solves Two Sum on the rest. Counting triangles from sorted side lengths can fix the longest side, then count pairs. Fixing a boundary, a center, the last value, or how many items you pick can turn a tangled problem into a simpler one.

Count the outer loop too. An O(n) method run for each of n fixed values costs O(n²). And don't fix something that destroys the structure the rest of the method relies on.

### Ask "does this value work?" before "what's the best value?"

Finding the best value directly can be hard when checking one value is easy. Replace "what's the smallest capacity?" with "does this capacity work?" Then show that once a capacity works, every larger one does too.

The real work is usually the check: a greedy simulation, a graph search under a limit, or a DP. Binary search on the answer only cuts down how many checks you run. If the check is slow, or a larger value can fail after a smaller one works, this won't help.

### Compare two options against the same future

To justify dropping option A for option B, imagine the same future for both. If B is always at least as good and at least as possible, you can drop A.

This one argument explains several techniques. In longest increasing subsequence, keep the smaller ending value for each length. In sliding window maximum, a newer, larger value pushes out older, smaller ones. In shortest subarray with sum at least K, a later prefix sum that's no larger replaces an earlier one. If two options trade off, such as one costing less and the other leaving more resources, neither wins; keep both, or add to the state.

### Run time backward, or choose the last step first

Some data structures handle adding easily but deleting badly. If you know every operation in advance, running them in reverse turns deletions into additions. This needs the whole history up front; it doesn't help when operations arrive one at a time.

Choosing the last step first is a similar trick. In [LC 312 Burst Balloons][p312], pick which balloon in a range bursts last. Its neighbors outside the range are then fixed, so the left and right parts become independent problems. Ask whether choosing the last event gives you fixed boundaries.

### Count what each element contributes

Instead of building every subarray and adding up its value, ask how many subarrays include each element. To total the sums of every subarray, index i appears in (i + 1) × (n − i) of them: that's the number of ways to pick a left end and a right end around it.

In [LC 907 Sum of Subarray Minimums][p907], count the subarrays where each element is the minimum. The nearest smaller element on each side marks the boundaries. With equal values, use `<` on one side and `<=` on the other, so each subarray is counted once. The hard part moves to deciding which element "owns" each subarray.

### Count the opposite, or subtract two easier counts

Sometimes what you want is hard to count, but everything and the unwanted part are easy. Another useful formula: exactly(k) = at_most(k) − at_most(k − 1).

To count subarrays with exactly k distinct values, count those with at most k using a sliding window, and subtract those with at most k − 1. The formula is simple, but the at-most count still needs its own correct sliding window. Watch the cases k = 0 and k − 1 < 0.

### Process events in an order that settles things

Sorting can turn a shifting rule into steady one-way progress. Say each query is a point and asks for the smallest interval containing it. Sort the points. Add intervals once their start is reached, and drop them once their end is passed. A min-heap picks the shortest interval left. Then put the answers back in the original query order.

[LC 1851 Minimum Interval to Include Each Query][p1851] works this way. Ask: "Can I reorder the work so each option enters once and leaves once?" That requires knowing every query up front.

### Split a huge search into two halves

If trying all subsets is too slow but n is still moderate, list the subset sums of each half separately. Sort one half's sums, and for each sum in the other half, binary search for a good partner. That cuts 2ⁿ down to about 2^(n/2), at the cost of much more memory.

Any extra rule has to survive the split. If you must pick exactly half the elements, group each half's sums by how many elements they use, and only combine matching group sizes. [LC 1755 Closest Subsequence Sum][p1755] and [LC 2035 Partition Array Into Two Arrays to Minimize Sum Difference][p2035] show the difference. If the numbers are small, a DP over possible sums may be better.

### Find a limit, then reach it

To prove an answer is the best, first show that nothing can beat some bound. Then build an answer that reaches it. Capacity, odd/even counts, the most frequent item, or a bottleneck can give you the bound.

Be careful: a bound isn't always reachable. An arrangement can pass a count-based bound and still break a rule between neighbors. Until you build a valid answer, the bound is only a bound. Scheduling formulas need the same checking as code.

### Try to break your own idea with a tiny example

Before you code a greedy rule, try three or four items that pull in different directions. To test a sliding window on sums, include a negative number. To test a count, include duplicates and zeros. To test a graph state, revisit a node with different resources. To test edge cases, try an empty input, one item, all-equal values, and no answer.

When an input breaks your idea, keep shrinking it while it still fails. A six-element example often shows the missing assumption far more clearly than a random hundred-element one. Building counterexamples is a skill: each one tells you what your next idea must remember or prove.

### Recognizing isn't the same as deriving

It's fine to recognize a familiar pattern right away. You don't need to reinvent known algorithms in an interview. What matters is that you can explain why the pattern fits, and adapt it when a rule changes.

If a solution feels like a trick, find the first step you can't justify. Did you assume that once a check passes, it keeps passing? Did you drop an option without showing it could never win? Did you pick a DP state without checking it holds everything the future needs? Fix that step, and the code usually follows.

## 4 A map of useful observations

Use this table to come up with ideas. Before you pick a technique, check that the condition in the middle column holds.

| What you notice | What must be true | Technique to try |
| --- | --- | --- |
| You keep asking about earlier values | A small key holds everything that matters | Hash map or set |
| Many ranges redo the same addition | A range's total can be worked out from two prefixes | Prefix sums |
| One comparison rules out a whole group | The ruled-out options can't satisfy or beat the answer | Two pointers or binary search |
| Neighboring windows share most elements | Updating a window is cheap, and moving each end is safe | Sliding window |
| Only a few best options matter | A dropped option can never come back into play | Heap, or keep only the options that can still win |
| Some items wait for a later event to settle them | Items get settled or beaten in a predictable order | Monotonic stack or deque |
| Different paths lead to the same situation | A small state captures every choice still to come | Memoization or DP |
| Choices lead from state to state | You can define the states and the moves exactly | BFS or DFS |
| Some tasks must come before others | The "before" rules never form a loop | Topological sort |
| Groups keep merging | Groups only grow, or you can run time backward | Union-find |
| A local choice still allows a best answer | Swapping in your choice never makes things worse | Greedy |
| Many overlapping range queries while values change | The ranges' values combine in any grouping | Fenwick tree or segment tree |

These ideas combine. A scheduler might sort jobs by arrival time, sweep forward through time, keep available jobs in a heap, and pick one with a greedy rule. Each part has its own job and its own reason for being correct. Calling the whole thing "a heap problem" hides that.

Patterns also overlap. A DFS that saves its answers is dynamic programming. A monotonic deque can maintain a sliding window. A shortest-path problem on a graph without cycles can be solved with DP. Learn what each technique does and why it works first; the labels just help you organize them.

## 5 Hashing and sufficient summaries

Use a hash map when your loop keeps asking about things it has already seen: whether a value appeared, how often, at which index, or the best value tied to a key. Work out the key from the question. Two Sum looks up each number's partner. Anagrams use letter counts as the key. Counting subarrays with a given sum looks up an earlier prefix sum.

For Two Sum, go left to right. Before index i, the hash map holds an index for every value before i. Look up the partner before you add the current value, so a number can't pair with itself. Repeated values are fine: with target 6, `[3, 3]` uses two different positions.

```rust
pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    use std::collections::HashMap;
    let mut seen = HashMap::<i64, usize>::new();
    for (i, &x) in nums.iter().enumerate() {
        let x = i64::from(x);
        if let Some(&j) = seen.get(&(i64::from(target) - x)) {
            return Some((j, i));
        }
        seen.insert(x, i);
    }
    None
}
```

Hash map lookups take O(1) time on average, so this takes O(n) time and O(n) space. Converting to `i64` before subtracting avoids overflow. When a value repeats, the map overwrites its older index, which is fine here because any earlier copy works. But if you wanted the longest matching range, you'd need the earliest index, so overwriting would be wrong.

**What changes the method:** returning all pairs changes the output size and how you handle duplicates. Returning a count needs frequencies. Keeping the original order can rule out sorting. If the key is a string of length m, building and hashing it costs O(m).

To group anagrams of lowercase English words, use a tuple of 26 letter counts as the key. Order doesn't matter, but counts do: a set of letters would treat "abb" and "ab" as the same. For other characters, decide on the key explicitly.

Practice: [LC 1 Two Sum][p1], [LC 242 Valid Anagram][p242], [LC 49 Group Anagrams][p49], [LC 128 Longest Consecutive Sequence][p128]. In the last one, only start counting a run at a value whose predecessor isn't in the set. Otherwise you rescan the same runs, and it can become O(n²).

**Check your understanding:** What can the hash map safely forget? Why look up before you insert? What changes when the question asks for the earliest, latest, longest, or total count?

## 6 Prefix sums and algebraic transformations

Prefix sums let you get the sum of any range with one subtraction. Set P[0] = 0 and P[i + 1] = P[i] + a[i]. Then the sum of a[l] through a[r − 1] is P[r] − P[l]. For `[2, 4, 1]`, P is `[0, 2, 6, 7]`, and the sum of the last two numbers is 7 − 2 = 5. The leading zero stands for "nothing added yet", so ranges that start at index 0 need no special case.

For many range-sum queries on a list that doesn't change, this turns O(length) work per query into O(1), after O(n) time and space to build P. To find subarrays that sum to k, rearrange P[r] − P[l] = k into P[l] = P[r] − k. Now you're counting earlier prefix sums with a specific value, which a hash map does.

```rust
pub fn count_sum(nums: &[i32], k: i64) -> i64 {
    use std::collections::HashMap;
    let mut counts = HashMap::from([(0_i64, 1_i64)]);
    let (mut prefix, mut answer) = (0_i64, 0_i64);
    for &x in nums {
        prefix += i64::from(x);
        if let Some(needed) = prefix.checked_sub(k) {
            answer += counts.get(&needed).copied().unwrap_or(0);
        }
        *counts.entry(prefix).or_insert(0) += 1;
    }
    answer
}
```

Before each lookup, `counts` holds the prefix sums strictly before the current position. Looking up before inserting means that, when k is zero, you don't count an empty subarray. For `[1, -1, 1]` and k = 1, the answer is 3. A set instead of counts would lose how many times each prefix sum appeared.

This works with negative numbers, unlike a sliding window. It takes O(n) time on average and O(n) space. The code assumes the sums and the count fit in `i64`.

Prefix sums work for more than addition. For XOR, a range is P[r] XOR P[l]. A running minimum can't give you the minimum of any range, though, because there's no way to "subtract" a minimum. Products need care with zeros, overflow, and division.

A difference array works the other way. To add x to every element in a range from l up to (not including) r, add x at index l and subtract x at index r. One prefix sum pass at the end rebuilds every value. This helps when you can collect all the updates before you need any answer.

Practice: [LC 303 Range Sum Query Immutable][p303], [LC 560 Subarray Sum Equals K][p560], [LC 974 Subarray Sums Divisible by K][p974], [LC 1109 Corporate Flight Bookings][p1109], [LC 238 Product of Array Except Self][p238]. For divisibility, make negative remainders positive, and make sure the divisor isn't zero.

**Check your understanding:** Why does the hash map start with one empty prefix? What do you need to store to count ranges, and what to find the longest one? Why do single-value updates make a plain prefix sum array expensive to keep up to date?

## 7 Two pointers and safe elimination

Two pointers work when you can show that moving one pointer never skips an answer. Having two pointers in your code doesn't prove anything by itself; the reason for each move does.

In a sorted list, suppose `a[left] + a[right]` is less than the target. Every other partner for `a[left]` is at most `a[right]`, so every sum with `a[left]` is too small. So `left` can move forward. If the sum is too large, every other partner for `a[right]` is at least `a[left]`, so `right` can move back. Each move rules out a whole row of pairs at once. The pointers move at most n times in total, so it's O(n).

Sorting an unsorted list first costs O(n log n), and you may need to remember the original indexes. If the question is about neighbors in the original order, sorting changes the problem, so you can't always do it.

To remove duplicates from a sorted list, use a read pointer and a write pointer. Everything before `write` holds the distinct values seen so far, in order. A new value extends that part; a duplicate is skipped. What's left after `write` doesn't matter.

3Sum fixes one value, then runs the sorted two-pointer search on the rest. After sorting, that's O(n²). Skipping repeated fixed values and repeated pointer values avoids duplicate triples. The goal is unique triples of values; a different output rule would need different duplicate handling.

**A different reason:** in Container With Most Water, the shorter wall limits the height. Moving the taller wall inward makes the container narrower without raising that limit, so it can't help. Move the shorter wall instead. This reason is different from the sorted-sum one.

Fast and slow pointers rely on yet another fact. In a cycle of length c, the fast pointer gains one step on the slow one each move, so they meet. Finding where the cycle starts needs one more argument about distances. Don't treat every two-pointer problem as one template.

Practice: [LC 167 Two Sum II][p167], [LC 26 Remove Duplicates from Sorted Array][p26], [LC 15 3Sum][p15], [LC 11 Container With Most Water][p11], [LC 141 Linked List Cycle][p141], [LC 142 Linked List Cycle II][p142].

**Check your understanding:** Name every pair that one pointer move rules out. Would that still be safe if the list weren't sorted? Does your reasoning allow equal values, and what happens with duplicates?

## 8 Sliding windows and monotone validity

A sliding window reuses work between neighboring ranges. For a window of fixed size k, add the number that enters and subtract the one that leaves. That gives the sum of every k-length range in O(n) time and O(1) extra space, even with negative numbers.

A window that grows and shrinks needs more: a reason each end can move forward and never come back. Say every number is positive and you want the shortest range with sum at least a target. Moving `right` raises the sum, and moving `left` lowers it. Whenever the sum is big enough, record the length and shrink from the left. Once a start position has found a valid window, a later end can't give that start a shorter one.

```rust
pub fn min_len_positive(nums: &[i32], target: i64) -> Option<usize> {
    assert!(target > 0 && nums.iter().all(|&x| x > 0));
    let (mut left, mut sum) = (0_usize, 0_i64);
    let mut best = None;
    for (right, &x) in nums.iter().enumerate() {
        sum += i64::from(x);
        while sum >= target {
            let len = right - left + 1;
            best = Some(best.map_or(len, |old: usize| old.min(len)));
            sum -= i64::from(nums[left]);
            left += 1;
        }
    }
    best
}
```

Each number enters once and leaves at most once, so both loops together cost O(n). `sum` always equals the window's sum. And for every start that `left` has moved past, `best` already includes its shortest valid window. An empty list returns `None`.

For `[2, 3, 1, 2, 4, 3]` and target 7, the first valid window has length 4. Later, shrinking `[2, 4, 3]` gives `[4, 3]`, which improves the answer to 2. Draw both pointers as they move: neither ever goes back.

This breaks on `[1, -1, 5]` with target 5. After the whole list reaches 5, removing 1 drops the sum to 4, so the window stops shrinking and misses `[5]`. Negative numbers don't break every sliding window. They break this one, because "a bigger window has a bigger sum" no longer holds.

For the longest substring without repeated characters, track character counts and shrink until the repeat is gone. Adding characters can't remove a repeat, but removing enough characters can. For the minimum window containing a set of characters, track how many of each you still need. Shrink while the window still covers everything, and record the answer before the window stops covering.

Practice: [LC 643 Maximum Average Subarray I][p643], [LC 209 Minimum Size Subarray Sum][p209], [LC 3 Longest Substring Without Repeating Characters][p3], [LC 424 Longest Repeating Character Replacement][p424], [LC 76 Minimum Window Substring][p76]. LC 424 has a clever optimization that keeps a stale count. Skip it until you can prove the simpler version works.

**Check your understanding:** Is the window fixed or growing and shrinking? Why does growing a window keep it valid, or keep it invalid? When should you record the answer: before shrinking, while shrinking, or after?

## 9 Binary search over a boundary

Binary search needs two things: a sorted search space, and a safe way to rule out half of it. The most reliable form finds the first True. Write a yes/no test that answers False for a while and then True from some point on. Keep a range of candidates from `lo` up to (not including) `hi`. If the middle answers True, the first True is there or earlier, so set `hi = mid`. If False, it's later, so set `lo = mid + 1`.

```rust
pub fn first_true<F>(n: usize, mut predicate: F) -> usize
where
    F: FnMut(usize) -> bool,
{
    let (mut lo, mut hi) = (0, n);
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if predicate(mid) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    lo
}
```

If nothing answers True, the result is n. The code never tests n itself. Everything below `lo` is known False, and everything from `hi` on is known True. Each step shrinks the range. The caller has to supply a test that really does go False, then True, and never back.

To find where a value goes in a sorted list, test `a[i] >= target`. To binary search on the answer, first turn "find the best" into a yes/no question. In Koko Eating Bananas, ask whether a given speed finishes in time. A faster speed never takes longer, so the answers go False, then True. Search for the smallest speed that works, after checking that your upper bound always works.

The cost is O(log R × C), where R is the size of the range you search and C is the cost of one test. Calling it O(log n) hides a full scan if each test looks at every element. Use 64-bit numbers when adding up hours, and round up the division without overflowing.

Finding a peak and searching a rotated sorted list use related ideas, but their values don't go False-then-True across the whole list. Learn those arguments separately. And sorted input doesn't always call for binary search.

Practice: [LC 704 Binary Search][p704], [LC 35 Search Insert Position][p35], [LC 34 Find First and Last Position][p34], [LC 875 Koko Eating Bananas][p875], [LC 1011 Capacity To Ship Packages Within D Days][p1011], [LC 33 Search in Rotated Sorted Array][p33].

**Check your understanding:** What exactly is the yes/no question? Why does a True answer stay True for larger values? What does it return if every answer is False? Why can't the loop repeat the same range? See [S9] for more on binary search boundaries and searching on the answer.

## 10 Stacks and monotonic deques

A stack holds unfinished work where the newest item is handled first: brackets waiting to close, an expression being evaluated, recursive calls, or items waiting for a later event. In valid parentheses, each closing bracket must match the most recent bracket still open. Counting brackets can't tell whether the types nest correctly.

In Daily Temperatures, keep the indexes of days still waiting for a warmer day. Their temperatures never rise from the bottom of the stack to the top. When a strictly warmer day arrives, it answers the days at the top. It's their first warmer day, because every day in between failed to answer them. Each index is pushed once and popped once, so it's O(n) time and O(n) space.

Equal values matter. For "next strictly greater", an equal value doesn't answer a waiting index. For "next greater or equal", it does. The comparison in a monotonic stack is exactly the problem's rule.

A monotonic deque adds a way for items to expire from the front. For the maximum of each fixed-size window, keep indexes in time order, with values decreasing from front to back. Remove expired indexes from the front. Before adding a new value, remove smaller or equal values from the back. The new value is at least as big and stays longer, so they can never win again. The front is the current maximum. You could keep equal values instead, as long as you handle expiry correctly.

Shortest Subarray with Sum at Least K combines prefix sums and a monotonic deque. For prefix positions j < i, the range sum is P[i] − P[j]. Keep the prefix sums in the deque in increasing order. If a later prefix sum is no larger than an earlier one, the later start gives at least as big a sum and a shorter range, so drop the earlier one. At the front, whenever a range reaches k, record it and drop that start: any later end would only make it longer.

That explains both ends of the deque. It also explains why the positive-numbers sliding window from Chapter 8 doesn't work with negative numbers.

Practice: [LC 20 Valid Parentheses][p20], [LC 155 Min Stack][p155], [LC 739 Daily Temperatures][p739], [LC 496 Next Greater Element I][p496], [LC 239 Sliding Window Maximum][p239], [LC 862 Shortest Subarray with Sum at Least K][p862], [LC 84 Largest Rectangle in Histogram][p84].

**Check your understanding:** Was an item removed because it expired, got answered, or could never win? Give a different reason for each kind of removal. For the histogram problem, say exactly which bar stops each height from extending further.

## 11 Heaps and the candidate frontier

A heap gives you the smallest (or largest) item from a changing group, quickly. It doesn't keep everything sorted. Decide which item you need to look at next, then pick a min-heap or a max-heap.

To keep the k largest values of a stream, a new value can only replace the smallest one you're holding. So use a min-heap of at most k items. After t values, it holds the largest min(k, t) of them, counting duplicates.

```rust
pub fn kth_largest(nums: &[i32], k: usize) -> Option<i32> {
    use std::cmp::Reverse;
    use std::collections::BinaryHeap;
    if k == 0 || k > nums.len() {
        return None;
    }
    let mut best = BinaryHeap::with_capacity(k + 1);
    for &x in nums {
        best.push(Reverse(x));
        if best.len() > k {
            best.pop();
        }
    }
    best.peek().map(|x| x.0)
}
```

After a push there are at most k + 1 items. Popping the smallest leaves exactly the best k. A value you dropped can never beat the ones you kept, as long as values only get added. If values could be deleted, a dropped value might matter again, and this reasoning would break.

It takes O(n log k) time and O(k) extra space. For a one-time answer on a fixed list, sorting or quickselect may be better. A heap shines when you need answers again and again as data arrives. Rust's `BinaryHeap` is a max-heap; wrapping values in `Reverse` flips it [S10].

To merge k sorted lists, the heap holds the first unused item of each list that isn't empty. Everything left in a list is at least that list's first item. So the smallest first item is the smallest item left overall. Pop it, and move only its list forward. For N items in total, that's O(N log k) time and O(k) space.

Two heaps can track a running median. Every value in the lower half is at most every value in the upper half, and the two sizes differ by at most one. You need both rules.

Practice: [LC 215 Kth Largest Element in an Array][p215], [LC 703 Kth Largest Element in a Stream][p703], [LC 347 Top K Frequent Elements][p347], [LC 23 Merge k Sorted Lists][p23], [LC 295 Find Median from Data Stream][p295].

**Check your understanding:** Why a min-heap and not a max-heap, or the other way around? Is each item in the heap a final answer or a candidate waiting its turn? Could something you dropped become useful again after a deletion or a priority change?

## 12 Sorting intervals and greedy choices

Sorting often makes a problem easier to reason about. Sorting intervals by start puts possible overlaps next to each other. Sorting jobs by end time can reveal a safe choice. Sorting coordinates turns "closest" questions into questions about neighbors.

To merge intervals, go through them in order of start, and keep the merged result so far. Only the last merged interval can be extended by the next one. Whether touching intervals overlap depends on the problem. Closed intervals like [1, 2] and [2, 3] merge. But for bookings from start up to (not including) end, a booking ending at time 2 frees the room before one starting at time 2.

To fit the most intervals with no overlaps, always pick the one that ends earliest. Why is that safe? Take a best schedule that starts with a different interval, which ends later. Swap in the earliest-ending one. It leaves at least as much room for everything after it, so the schedule is just as big. Repeat for the rest. Showing a swap never hurts like this is called an exchange argument.

```rust
pub fn max_nonoverlap(intervals: &mut [(i32, i32)]) -> usize {
    assert!(intervals.iter().all(|&(s, e)| s < e));
    intervals.sort_unstable_by_key(|&(s, e)| (e, s));
    let (mut last_end, mut count) = (None, 0);
    for &(start, end) in intervals.iter() {
        if last_end.is_none_or(|prev| start >= prev) {
            count += 1;
            last_end = Some(end);
        }
    }
    count
}
```

This treats intervals as running from start up to (not including) end, and maximizes the count. If intervals have different values, swapping in an earlier-ending one can lose value. Weighted scheduling needs DP instead: sort, then for each interval find the last one that fits before it.

To count meeting rooms, sweep through starts and ends while counting how many meetings are running, or keep a min-heap of end times. Decide what happens when a start and an end tie. A heap tells you which room frees up first; it doesn't prove a greedy choice is right on its own.

Practice: [LC 56 Merge Intervals][p56], [LC 57 Insert Interval][p57], [LC 435 Non-overlapping Intervals][p435], [LC 452 Minimum Number of Arrows to Burst Balloons][p452], [LC 55 Jump Game][p55], [LC 45 Jump Game II][p45], [LC 1235 Maximum Profit in Job Scheduling][p1235].

**Check your understanding:** Can you swap your choice into a best solution without making it worse? What makes that swap safe? Build the smallest example where the swap fails once the goal changes.

## 13 Linked lists and recursive trees

Most linked list problems are about changing links without losing your way. To reverse a list, keep two parts: the part already reversed, and the part not yet touched. Save `next` before you overwrite it. Otherwise you lose the only link to the rest of the list. All the pointer moves exist to keep the rest of the list reachable.

Use a dummy head node when the first node might change. When merging sorted lists, the output so far holds the smallest items used, and each list's head is its smallest unused item. For cycles, finding that a cycle exists is a different problem from finding where it starts.

Tree recursion gets easier when each call has a small, clear job. For height, an empty tree has height 0, and a node returns one plus its taller child's height. To check balance, a call can return a height or a "not balanced" signal. That way no ancestor recomputes a height.

For the diameter, separate what a call returns to its parent from the best answer found anywhere. The parent can only extend one branch downward, so return max(left_height, right_height) + 1. But a path whose highest node is the current node can use both children, so its length in edges is left_height + right_height. Every path has one highest node, so checking this at every node covers every path.

To validate a binary search tree, a node must satisfy rules from every ancestor, not only its parent. Pass down a lower and upper limit. Or show that an inorder traversal is strictly increasing, given no duplicates. Use "no limit" for a missing limit, not a made-up number that could rule out a real value.

The traversal order follows what depends on what. Preorder handles a node before its children. Postorder combines the children's answers. Inorder visits a BST in sorted order. Level order uses a queue and handles nodes by distance from the root. Visiting n nodes costs O(n). Recursion goes as deep as the tree's height, which is n for a chain and can overflow the call stack.

Practice: [LC 206 Reverse Linked List][p206], [LC 21 Merge Two Sorted Lists][p21], [LC 19 Remove Nth Node From End][p19], [LC 104 Maximum Depth of Binary Tree][p104], [LC 110 Balanced Binary Tree][p110], [LC 98 Validate Binary Search Tree][p98], [LC 543 Diameter of Binary Tree][p543], [LC 236 Lowest Common Ancestor][p236].

**Check your understanding:** What exactly does one call return? What information goes down the tree, and what comes back up? Can the parent extend the branch you return, or is it a finished path?

## 14 Backtracking and the search tree

Backtracking tries every choice while building up one partial answer. Define four things: the current state, the choices available, when to stop, and how to undo a choice. Each recursive call is one point in the tree of choices, not necessarily one item of the input.

For subsets, decide at each position whether to include that item. There are 2ⁿ subsets, and copying them all out takes O(n × 2ⁿ) time. For permutations of n distinct values, picking any unused value gives n! results and O(n × n!) work.

What stays true: the current path holds exactly the choices made on the way down to this call, and the "used" state matches it. When a recursive call returns, undo your change, so the next sibling starts from the same state.

Pruning skips branches that can't lead to a valid or better answer. If every value is positive and you're aiming for a sum, going over the target means adding more can't help. With negative values, that pruning would be wrong. When optimizing, if even the best possible finish of a branch can't beat your current answer, skip it.

With duplicate values in the input, two paths can give the same output. To generate unique permutations from a sorted list, skip a value when an equal value right before it hasn't been used on the current path. That picks one order among equal values. Skipping every duplicate would wrongly drop results that use a value twice.

Saving answers (memoization) helps when different branches reach the same state and you only need one answer per state. It helps less when the output must list every path, because then the paths themselves matter. Make sure caching still produces the output the problem asks for.

Practice: [LC 78 Subsets][p78], [LC 46 Permutations][p46], [LC 47 Permutations II][p47], [LC 39 Combination Sum][p39], [LC 22 Generate Parentheses][p22], [LC 79 Word Search][p79], [LC 51 N-Queens][p51].

**Check your understanding:** Which change has to be undone? Is the branch you prune impossible, or just unlikely? Are two paths that reach the same state interchangeable for the output you need?

## 15 Graph modeling and traversal

A graph is a set of states and the moves allowed between them. Sometimes you get it as a list of edges. Other times it's hidden in a grid, a lock, word changes, or a sequence of actions. Defining the state correctly is often harder than writing the BFS.

DFS goes deep down one branch first. It's good for "can I reach it?", for finding connected groups, and for learning about structure. BFS handles states in order of how many edges they are from the start. When every edge costs the same, the first time BFS reaches a node gives its shortest distance. Mark a node as seen when you add it to the queue, so it isn't added twice.

```rust
pub fn bfs_dist(adj: &[Vec<usize>], start: usize) -> Vec<Option<usize>> {
    use std::collections::VecDeque;
    assert!(start < adj.len());
    let mut dist = vec![None; adj.len()];
    let mut queue = VecDeque::from([start]);
    dist[start] = Some(0);
    while let Some(u) = queue.pop_front() {
        let next_distance = dist[u].unwrap() + 1;
        for &v in &adj[u] {
            if dist[v].is_none() {
                dist[v] = Some(next_distance);
                queue.push_back(v);
            }
        }
    }
    dist
}
```

The node numbers must be valid indexes. This takes O(V + E) time and O(V) extra space, not counting the adjacency list. `None` means unreachable. To find the distance to the nearest of several sources, put all of them in the queue at distance 0 and run one BFS.

A "seen" set only works if its key is the full state. In a grid with keys to collect, position alone isn't enough: reaching the same cell with different keys changes where you can go next. The state might be (row, column, keys held). Two different paths can share a state only when their futures and costs are the same.

For a grid, decide what counts as a neighbor: four directions or eight, the edges of the grid, blocked cells, and whether you can revisit cells. Flood fill asks "can I reach it?" Shortest route asks "how far?" A DFS that happens to reach the target first usually doesn't find the shortest route.

To find a cycle in an undirected graph, ignore the edge back to the node you came from, and look for any other neighbor you've already seen. Repeated edges between the same two nodes need extra care. In a directed graph, track whether a node is "in progress" or "done", or use topological sort. A single "seen" flag isn't enough for every cycle check.

Practice: [LC 200 Number of Islands][p200], [LC 133 Clone Graph][p133], [LC 994 Rotting Oranges][p994], [LC 127 Word Ladder][p127], [LC 752 Open the Lock][p752], [LC 864 Shortest Path to Get All Keys][p864].

**Check your understanding:** What are the nodes? What makes a move allowed? Is reaching the same place with different resources the same state? Does every move cost the same?

## 16 Dependencies and merging components

Topological sort handles "this must come before that". A node is ready once everything it depends on is done. Start a queue with the nodes that depend on nothing. Take one, and lower the count for each node that depends on it. Every node you take has nothing left blocking it.

If you take fewer than V nodes, the rest contain a cycle. There can be several valid orders. If the problem asks for the alphabetically smallest order, use a min-heap instead of a queue; otherwise, a plain queue gives a valid order.

The same order supports DP. For the longest path in a graph with no cycles, push each node's best answer along its outgoing edges once everything before it is settled. The graph doesn't have to look like a network: in a grid, "move to a bigger neighbor" makes a graph with no cycles.

Union-find answers a different question: as edges are added, which elements are in the same connected group? Each group has a root. `find` follows parent links up to the root, and `union` links two roots. With path compression and union by size, each operation takes nearly O(1) time on average. The exact bound is O(α(n)), where α grows so slowly it's below 5 for any real input [S12].

What stays true: two elements have the same root exactly when the edges added so far connect them. The parent links inside a group are bookkeeping, not the graph's real edges. The root has no special meaning unless you choose to store something there.

Plain union-find only handles groups that grow. It can't undo a merge. If you know every operation in advance, you can sometimes run time backward so deletions become additions. Otherwise you need extra machinery to roll back. And union-find doesn't capture one-way reachability in a directed graph.

Practice: [LC 207 Course Schedule][p207], [LC 210 Course Schedule II][p210], [LC 329 Longest Increasing Path in a Matrix][p329], [LC 684 Redundant Connection][p684], [LC 721 Accounts Merge][p721], [LC 547 Number of Provinces][p547].

**Check your understanding:** Is the relation one-way ("before") or two-way ("connected")? Can groups split later? What extra data, like a group's size, must you combine when groups merge?

## 17 Weighted shortest paths

Pick a shortest-path method based on the edge costs. If every edge costs the same, use BFS. If edges cost only 0 or 1, use 0-1 BFS with a deque. If no edge is negative, use Dijkstra's algorithm. In a graph with no cycles, process nodes in topological order, even with negative edges. With negative edges in general, use something like Bellman–Ford, and watch for negative cycles.

Dijkstra's algorithm keeps a best-known distance for every node, and always settles the unsettled node with the smallest one. Why is that distance final? Any other route would pass through an unsettled node that's already at least as far. Edges never cost less than zero, so the rest of that route can't bring the total back down [S11].

With a binary heap, when you find a shorter route to a node, push a new entry instead of updating the old one. When you pop an entry, skip it if it no longer matches the node's best distance. Don't mark a node as done when you first push it: a later route may still improve it.

For a typical adjacency-list version, a safe bound is O((V + E) log(V + E)) time and O(V + E) extra space, counting the extra heap entries. Tighter bounds you may have seen make extra assumptions about the graph. Give the bound for the version you actually wrote.

Here's why the first route found isn't always final. Take edges S→A costing 10, S→B costing 1, and B→A costing 1. The first route to A costs 10, but the shortest costs 2.

Extra limits can make the state bigger. If you may use only a few edges, reaching a node cheaply with no edges left isn't better than reaching it at more cost with edges to spare. Track enough information, such as (node, edges used). "At most k stops" means at most k + 1 edges.

Practice: [LC 743 Network Delay Time][p743], [LC 1631 Path With Minimum Effort][p1631], [LC 1368 Minimum Cost to Make at Least One Valid Path in a Grid][p1368], [LC 787 Cheapest Flights Within K Stops][p787]. In Path With Minimum Effort, a route's cost is its largest single step, not the sum. Check that extending a route still never makes its cost go down.

**Check your understanding:** What does a distance measure here? Why is a popped node's distance final? Does the state include every resource that changes where you can go next? Is a node unreachable, or just not improved yet?

## 18 Dynamic programming from sufficient state

Dynamic programming (DP) saves the answers to subproblems that come up again and again. Start with a recursive solution that's correct. Then ask which parts of the history decide the choices left and their value. Those parts are your state.

In House Robber, let best(i) be the largest total from the first i houses with no two neighbors picked. A valid pick either skips the last house, giving best(i − 1), or takes it, giving best(i − 2) + value[i − 1]. These two cases cover every pick, and they don't overlap.

```rust
pub fn rob(values: &[i32]) -> i64 {
    assert!(values.iter().all(|&x| x >= 0));
    let (mut two_back, mut one_back) = (0_i64, 0_i64);
    for &value in values {
        let current = one_back.max(two_back + i64::from(value));
        two_back = one_back;
        one_back = current;
    }
    one_back
}
```

Before each house, `one_back` is the best total for the houses so far, and `two_back` is the best without the last one. The update is the recurrence, line for line. It takes O(n) time and O(1) space. Write out the full table before you shrink it to two variables; saving memory too early hides what depends on what.

Every DP explanation should say five things: what a state means, the transitions, the base cases, the order you fill it in, and where the answer is. "Use a 2D array" says none of them.

States you can't reach need a value that can't be mistaken for a real answer. In a minimum-cost DP, starting every state at zero invents free solutions. Use `None`, or a carefully handled infinity. Don't add costs to an infinity value without thinking about overflow.

Top-down DP with memoization computes only the states you reach, and often reads like the recurrence. Bottom-up DP fills the table in an explicit order and avoids deep recursion. Both need the same state. If the recurrence has a cycle, memoization alone won't solve it; you may need a different formulation or algorithm.

The cost is roughly the number of states times the work per state, plus reading the input and writing the output. With position and budget as the state, there might be O(nB) states. If each tries B choices, that's O(nB²).

Practice: [LC 70 Climbing Stairs][p70], [LC 198 House Robber][p198], [LC 746 Min Cost Climbing Stairs][p746], [LC 322 Coin Change][p322], [LC 139 Word Break][p139].

**Check your understanding:** Can two histories with the same state have different choices ahead? If so, the state is missing something. Does each transition lead to a smaller subproblem that's already solved?

## 19 Dynamic programming families

This chapter covers the DP shapes that come up most, and the details that tell them apart.

**Two sequences.** For two sequences, a good state is a pair of prefix lengths. Longest Common Subsequence asks for the best answer using the first i items of one and the first j of the other. If the last items match, extend the answer for the shorter prefixes. If not, skip one of the last items. Edit Distance uses the same kind of grid, but with different moves and base cases. Two tables that look alike don't have the same recurrence.

**0/1 subset sum.** Let `reachable[s]` say whether some subset of the items so far adds up to s. Update the sums from high to low, so each item is used at most once. Going from low to high lets an item reuse itself, which solves a different problem where items are unlimited.

**Counting coin combinations.** Put the loop over coins outside the loop over sums. That counts each combination once, in a fixed order. Putting the sums outside and trying every coin last usually counts ordered sequences instead. Decide what you're counting before you pick the loop order.

**Interval DP.** Define what happens inside a range from l to r, then pick a split point or a last action. Choosing the last action can fix its neighbors and separate the subproblems. Choosing the first action may leave messy interactions. Make sure something, such as the range's length, shrinks in every recursive call.

**Tree DP.** A child may need to return several answers, one for each choice the parent might make. In House Robber III, return the best total when the current node is taken, and when it's skipped. Taking it forces both children to be skipped. Skipping it lets each child pick whichever is better.

**Bitmask DP.** A small integer encodes which items are used or visited. For a route through every node, the state might be (used set, last node). That's O(n × 2ⁿ) states and up to O(n² × 2ⁿ) work, so n must be small.

**Longest increasing subsequence.** There's an O(n²) DP and an O(n log n) method. The faster one stores the smallest possible last value for each length. Those values don't have to form one real subsequence together; they record the best chances to extend. For the same length, a smaller last value always beats a larger one.

Practice: [LC 1143 Longest Common Subsequence][p1143], [LC 72 Edit Distance][p72], [LC 416 Partition Equal Subset Sum][p416], [LC 518 Coin Change II][p518], [LC 494 Target Sum][p494], [LC 312 Burst Balloons][p312], [LC 337 House Robber III][p337], [LC 300 Longest Increasing Subsequence][p300].

**Check your understanding:** Are you finding the best answer, counting, or checking whether one exists? Does order matter? Can an item be reused? Which value would an in-place update overwrite too early?

## 20 Tries and string structure

A trie stores words so that shared prefixes are stored once. Each edge is one character, and a marker says where a complete word ends. After following a prefix, the current node stands for exactly the stored words that start with it.

Looking up a word of m characters takes O(m) time when finding a child is O(1). Space depends on all the stored prefixes and how you store children. A fixed array of 26 children is fast but uses more space. A hash map handles any characters, at some extra cost.

A search with wildcards has to try every child at a wildcard, so it can visit many nodes. It isn't O(m) in general. Combining a trie with backtracking on a grid lets many words share their prefix checks. You still have to undo the grid's "visited" marks between branches.

String matching algorithms reuse what already matched. In KMP, the prefix function records, for each prefix, the longest part that's both a proper prefix and a suffix. After a mismatch, it tells you how much of the match you can keep without rechecking the text. Trace how it falls back before you memorize the code.

Rolling hashes let you compare substrings quickly, but equal hashes don't prove equal strings. Either rule out collisions, or check each match directly. An explanation of correctness has to account for collisions.

Palindrome problems often get simpler if you think from the center. Expanding around each character and each gap between characters handles odd and even lengths in O(n²) time with O(1) extra space. Other limits may call for DP or a specialized linear algorithm. Check whether the task is to find, count, or split into palindromes.

Practice: [LC 208 Implement Trie][p208], [LC 211 Design Add and Search Words][p211], [LC 212 Word Search II][p212], [LC 28 Find the Index of the First Occurrence in a String][p28], [LC 5 Longest Palindromic Substring][p5], [LC 131 Palindrome Partitioning][p131].

**Check your understanding:** What is one character here: a byte, a Unicode code point, or what a reader sees as one letter? Is a prefix also a complete word? What can you keep after a mismatch? Does a hash match need checking?

## 21 Bits mathematics and small state spaces

Bit tricks help when a problem has a matching property. XOR cancels pairs: x XOR x = 0, and x XOR 0 = x. In Single Number, every value that appears twice cancels out, leaving the one that appears once. That relies on the problem's promise that everything else appears exactly twice.

A bitmask can stand for a subset of a small set: bit i is 1 when item i is in. Setting, clearing, and testing bits give you set operations. Trying every mask still takes exponential time; a compact representation doesn't reduce the number of subsets.

`x & (x - 1)` clears the lowest 1 bit of a positive unsigned integer. In Rust, be careful with zero and subtraction. Shifts must stay within the integer's width. Shifting signed numbers right, or letting arithmetic overflow, can change the result you meant.

Math can often replace simulation. Euclid's algorithm uses gcd(a, b) = gcd(b, a mod b) for positive b. Fast exponentiation squares repeatedly, using the exponent's binary digits. Modular arithmetic groups numbers by remainder, but decide how to handle negative remainders.

For counting problems, decide the model first. Does order matter? Can items repeat? Can you tell the items apart? A binomial coefficient counts choices where order doesn't matter; permutations count arrangements. The wrong model can give a neat formula for the wrong thing.

Number sizes matter no matter how fast the algorithm is. An O(n) algorithm can still overflow when adding n values or multiplying two coordinates. Convert to a wider type before the operation, not after. When the answer is wanted modulo M, apply the modulo where the math allows it. Division needs a modular inverse, which doesn't always exist.

Practice: [LC 136 Single Number][p136], [LC 191 Number of 1 Bits][p191], [LC 338 Counting Bits][p338], [LC 50 Pow][p50], [LC 78 Subsets][p78], [LC 201 Bitwise AND of Numbers Range][p201].

**Check your understanding:** Which formula makes the trick work? Which promise about the input does it rely on? Would values appearing three times instead of twice break it?

## 22 Range queries under updates

Prefix sums are perfect when values don't change, but one update changes every later prefix sum. A Fenwick tree stores overlapping blocks of sums, so both a single update and a prefix sum query take O(log n). It uses indexes starting at 1, so the lowest 1 bit of an index gives the size of its block.

To get a prefix sum, add the block ending at the current index, then clear the index's lowest 1 bit, and repeat. Those blocks exactly cover the prefix. To add to one position, walk up through the blocks that contain it. Index 0 needs special care: an update loop that starts at 0 and adds the lowest 1 bit never moves.

A segment tree splits the index range in half again and again. Each node stores a summary of its range, and a query combines the summaries of a few non-overlapping ranges. The combining operation must give the same result however you group it, and you need a neutral value for empty parts. Sum uses 0, minimum uses infinity, and maximum uses negative infinity.

A standard segment tree handles single updates and range queries in O(log n) time, using O(n) space. Lazy propagation adds range updates by recording updates to apply later. You also need correct rules for combining pending updates and applying them to a summary. "Store a lazy value" isn't a complete design.

Coordinate compression replaces values with their rank when only their order matters. It keeps comparisons, not distances. If your algorithm uses the actual gaps between values, keep those separately.

Before reaching for an advanced structure, check whether you know all queries in advance, whether the data ever changes, or whether you only need a few operations. Sorting the queries, prefix sums, or a monotonic deque may solve a simpler version with much less code.

Practice: [LC 307 Range Sum Query Mutable][p307], [LC 315 Count of Smaller Numbers After Self][p315], [LC 327 Count of Range Sum][p327], [LC 218 The Skyline Problem][p218]. The last three can be solved several ways; compare what each way keeps track of.

**Check your understanding:** What does one node store? Why can the pieces of a query be combined in that order? Does an update set a value or add to it? Does compression keep what your operation needs?

## 23 Data structure design and composed invariants

Design problems ask you to support a set of operations, each within a cost. Write the list of operations and costs first. An LRU cache needs: look up a key, mark it as most recently used, insert, and evict the least recently used entry. A hash map finds entries. A doubly linked list keeps the order and lets you remove or insert an entry in O(1) once you've found it.

What must stay true covers both structures at once. Every key in the map has exactly one node in the list, every node has exactly one map entry, and the list order matches how recently each key was used. Updating one structure without the other is a bug, even if each looks fine on its own.

A randomized set combines a list, so you can pick a random index, with a hash map from each value to its index. To delete, move the last value into the deleted spot, update the moved value's index, and pop the end. The map and list must always agree on every value's index. Forgetting to update the moved value's index breaks later deletions.

A min stack can store, with each value, the minimum of everything at or below it. That keeps repeated minimum values correct after one is popped. A queue built from two stacks takes O(1) time per operation on average, because each element moves between the stacks at most once.

In Rust, storing nodes in a vector and linking them by index is often simpler than shared mutable pointers. If you reuse slots, you may need a version number so that old handles are caught. Pick a representation that supports the operations and their costs; code that's easy to write doesn't replace the cost argument.

Practice: [LC 146 LRU Cache][p146], [LC 380 Insert Delete GetRandom O1][p380], [LC 155 Min Stack][p155], [LC 232 Implement Queue using Stacks][p232], [LC 981 Time Based Key Value Store][p981].

**Check your understanding:** What ties the structures together? What happens when you insert a key that already exists? What happens when the structure is empty, or its capacity is zero? Is each cost worst-case, average, or averaged over many operations?

## 24 Rust as an implementation tool

When something goes wrong, you want to know whether it's the algorithm or the Rust. So first state the algorithm in plain words. Then pick ownership, number types, and collections that do exactly that.

| Need | Usual Rust type | Remember |
| --- | --- | --- |
| State indexed by position | `Vec<T>` | Indexes are `usize`; subtracting can underflow. |
| "Is it there?" or counts | `HashSet` or `HashMap` | A lookup also costs building and hashing the key. |
| Keys in sorted order | `BTreeSet` or `BTreeMap` | Use when you need ordered queries. |
| First in, first out (BFS) | `VecDeque` | `pop_front` doesn't shift the other elements. |
| Last in, first out (stack) | `Vec` | `push` and `pop` are the stack. |
| Changing maximum | `BinaryHeap` | Iterating it doesn't give sorted order. |
| Changing minimum | `BinaryHeap<Reverse<T>>` | With tuples, the later fields break ties. |
| Missing or unreachable | `Option<T>` | Keeps "nothing" separate from a real zero. |

The standard library documentation describes each collection's guarantees and tradeoffs [S13]. For heap direction and ordering, see [S10].

Use `i64` for sums of `i32` values when the limits call for it. Convert before adding or multiplying: an `i32` product converted to `i64` afterward has already overflowed. `usize` suits valid indexes, but not −1 as a "not found" marker. Ranges that include the start and exclude the end often remove the need for that marker.

Rust strings are UTF-8. If the input is promised to be ASCII, `s.as_bytes()` gives easy indexed characters. For Unicode code points, collect `s.chars()` if you need indexes; that allocates, and still doesn't match what a reader sees as one letter. Say which alphabet you assume instead of quietly treating bytes as characters [S14].

Borrow checker errors often point to overlapping reads and writes. Copy a small value out of a map or heap before you change the collection. For counts, `entry(key).or_insert(0)` updates in place. Don't clone whole graphs or paths just to silence a borrow error, unless you count that cost.

Deep recursion in Rust can overflow the stack on a long chain. Your own stack gives more predictable memory for deep graph searches. LeetCode's tree problems in Rust use `Rc<RefCell<TreeNode>>`; for algorithms you control, adjacency lists indexed by number can be simpler. Neither changes why the algorithm is correct.

When testing, separate three things: it compiles, it passes the examples, and the algorithm is right. When you can, write a slow but obviously correct version for small inputs. Generate small cases, compare the answers, and study the smallest one that disagrees. Tests hunt for counterexamples; the reasoning about what stays true explains why every valid input works.

## 25 Similar looking problems with different rules

The fastest way to misuse a pattern is to forget the condition that made it work. Use these pairs as deliberate comparisons. Before you study the second solution, explain which assumption changed.

| First problem or condition | What changes | What to rethink |
| --- | --- | --- |
| Shortest window with positive numbers, LC 209 | Negative numbers allowed, LC 862 | A bigger window no longer means a bigger sum; use prefix sums with a monotonic deque |
| Range sums on a fixed list, LC 303 | Values change, LC 307 | Prefix sums computed once versus a structure you can update |
| Any matching pair, LC 1 | Unique triples, LC 15 | Trying values, handling duplicates, and two pointers on a sorted list |
| Shortest path, every edge the same cost | Different costs, none negative, LC 743 | BFS order versus Dijkstra's closest-first order |
| Cheapest route with no limits | Limited stops, LC 787 | The node alone versus the node plus the stops left |
| Most intervals, LC 435 | Intervals have rewards, LC 1235 | "Earliest end first" no longer protects the total reward |
| Each item at most once, LC 416 | Coins can be reused, LC 518 | What the state means, and which direction to update |
| Coin combinations, LC 518 | Ordered sums, LC 377 | Whether different orders count as different answers |
| Subsequence, LC 1143 | Contiguous substring, LC 718 | Skipping is allowed in one recurrence and not the other |
| Reachability in a grid, LC 200 | Keys change your moves, LC 864 | Position alone no longer captures the state |
| Kth largest, values only added, LC 703 | Values can be deleted | A dropped value may matter again |
| Two strings that look equal | Their hashes match | Equal hashes need a plan for collisions |

These pairs are for comparing ideas. They don't all differ in only one detail, so read both problems in full, including the output format and limits.

What you claim stays true must be specific enough to prove the result. "The stack is sorted" doesn't explain why popped items aren't needed. "The DP stores the best answer" doesn't say what the subproblem is. "Every settled distance is the shortest" needs the graph's assumptions and a rule for when to settle.

Test each technique you learn in three ways: change what the input can contain, change what you're asked for, and change which operations are allowed. Positive to negative, "does one exist" to "how many", and adding to deleting each expose a different hidden assumption.

## 26 A curriculum built around dependencies

This is a suggested order, not a proven one. Move on when you can explain and code the core ideas, and keep revisiting earlier topics in mixed practice. A hard problem is a later checkpoint, not something you must solve before reading on.

| Stage | Learn and practice | You're ready when you can |
| --- | --- | --- |
| A | Cost, arrays, hash maps, sorting; LC 1, 242, 49, 121 | Write a brute force and remove a repeated lookup or scan. |
| B | Prefix sums, two pointers, sliding window; LC 303, 560, 167, 209, 3 | Explain why moving each pointer is safe, and when it isn't. |
| C | Binary search, stacks, heaps; LC 35, 875, 20, 739, 215 | State exactly what the search or the stack keeps true. |
| D | Linked lists, trees, backtracking; LC 206, 104, 98, 78, 46 | Say what one recursive call does, and undo choices between branches. |
| E | Graphs, BFS, DFS, topological sort; LC 200, 994, 207 | Define the full state and explain the visiting order. |
| F | DP and greedy proofs; LC 198, 322, 416, 1143, 435 | Write a recurrence, or show a greedy swap never hurts. |
| G | Combinations and changed assumptions; LC 239, 862, 743, 787 | Explain why a simpler familiar technique isn't enough. |
| H | Optional extras: tries, range queries, bitmasks, advanced strings | Point to the operation or limit that needs the extra machinery. |

For each topic, pick one clear starter problem, one variation, and one problem tried without its topic label. The starter teaches the idea. The variation changes a condition. The unlabeled one tests whether you can pick the idea yourself.

A first pass: LC 1, 242, 49, 121, 303, 560, 167, 209, 3, 35, 875, 20, 739, 215, 206, 104, 78, 200, 198, and 435. That's a starting point, not a quota. If you're missing a prerequisite, study it directly. If a problem feels routine, move on to a variation.

Once you know several topics, mix them. Keep some test problems unseen: don't read their solutions in advance. Familiar problems measure what you remember; unfamiliar ones show whether you can apply it. Track how much of a hint you needed, whether you could explain why it works, whether your code worked, and whether your approach survives a changed assumption.

Other study plans are useful lists. NeetCode groups problems by topic and builds in review [S1]. Grind 75 explains how it picks and mixes problems [S2]. Sean Prashad's list gives tips for choosing an approach [S3]. Follow one main plan and borrow problems from others to fill specific gaps.

## 27 Transfer exercises

These exercises test the book's ideas in new settings. They don't name the technique on purpose, so work from the problem statement. Chapter 28 has hints and answers; keep it closed while you try.

**Exercise A: Parcel ledger.** A ledger has n integer balance changes, positive or negative. Count the runs of one or more neighboring entries whose total is exactly t. For `[2, -2, 2]` and t = 2, return 3. Assume every sum and the count fit in `i64`. Aim for O(n) time on average.

**Exercise B: Radio buffer.** Packets with positive sizes arrive in order. Find the fewest neighboring packets whose total is at least a positive capacity c, or report that none exist. For `[4, 1, 2, 6]` and c = 7, return 2. Then decide whether your method still works if sizes can be negative.

**Exercise C: Exhibit scores.** Scores arrive one at a time, with repeats. Once at least k have arrived, report the kth-largest score so far after each arrival. For k = 3 and arrivals `[8, 2, 8, 5]`, the last two reports are 2 and 5. Keep only O(k) values. Explain what breaks if old scores can be deleted.

**Exercise D: Printer capacity.** A machine handles jobs of positive sizes in the given order. Each day it handles a run of neighboring jobs totaling at most capacity c, and jobs can't be split. Find the smallest capacity that finishes within d days, where 1 <= d <= n. For `[3, 2, 4, 1]` and d = 2, return 5. Explain your yes/no test and your search range.

**Exercise E: Gallery visits.** Each exhibit runs from its start time up to (not including) its end time, with start < end. Pick the most exhibits with no overlaps. For [0, 4), [1, 2), [2, 3), [3, 5), return 3. Then give each exhibit a reward, and explain whether the same rule gets the most reward.

**Exercise F: Maintenance corridor.** Rooms form a graph where every hallway goes both ways and has the same length. Some rooms have maintenance stations. For every room, find the fewest hallways to any station, or report that none can be reached. In the path 0-1-2-3-4 with stations at 0 and 4, return `[0, 1, 2, 1, 0]`.

**Exercise G: Cooling schedule.** Each day offers a reward of zero or more, but taking one day's reward means you can't take the next day's. Find the largest total. For `[4, 7, 2, 9]`, return 16. Then change the rule so taking a reward blocks the next two days, and work out the new recurrence.

**Exercise H: Museum door.** A graph has doors that need particular keys. You pick up keys at rooms and keep them. Find the fewest moves from a start room to a target. Explain why marking only the room as visited can throw away a route you need. Assume at most six different keys.

For each exercise, write down five things: a brute force, the key idea, what stays true (or the recurrence), the cost, and a counterexample to a tempting wrong approach. Getting the example right is only the start.

## 28 Hints and transfer exercise answers

**A, hint:** compare two running totals. The difference of two prefix sums is a range's sum. Keep a hash map counting earlier prefix sums, and look up `current_prefix - t` before adding the current prefix. Start with the empty prefix counted once. O(n) time on average and O(n) space. In the example, the three answers are each 2 on its own and the whole ledger. A sliding window doesn't work here, because entries can be negative.

**B, hint:** look at how dropping the oldest packet changes the total. With positive sizes, grow the window to the right, and shrink from the left while it's big enough. Record each valid window before removing its left packet. O(n) time and O(1) extra space. The window `[1, 2, 6]` shrinks to `[2, 6]`. Negative sizes break this: `[1, -1, 5]` with capacity 5 shows the failure.

**C, hint:** which kept score is easiest for a new one to replace? Keep the largest k scores in a min-heap. Once it holds k scores, its top is the kth largest. Each arrival costs O(log k) time, with O(k) space. If any score can be deleted, a score you dropped might become the answer again, so keeping only k isn't enough.

**D, hint:** first check whether one given capacity works. Fill each day with as many jobs in a row as fit. That uses the fewest days for that capacity: no valid first day can end later, and the same holds for each day after. If a capacity works, every larger one does too. Search from the largest job up to the total of all jobs. Each check is O(n), so binary search on the answer costs O(n log R), where R is the number of capacities in that range. Capacity 5 allows [3, 2] and [4, 1].

**E, hint:** leave as much time free for later as you can. Always pick the compatible exhibit that ends earliest. Swapping this choice into any best schedule never makes it smaller, and the same holds for each later pick. Sorting dominates, at O(n log n). With rewards, the swap no longer protects the total: [0, 4) worth 100 beats three short exhibits worth 1 each. Use a DP instead: for each exhibit, compare skipping it with taking it plus the best schedule that ends before it starts.

**F, hint:** let every station start searching at once. Put every station in the BFS queue at distance 0. The first time BFS reaches a room gives its distance to the nearest station, because each layer is one hallway further. O(V + E) time and O(V) space, not counting the graph. Running a separate BFS from each station repeats work. Rooms with no station in their part of the graph stay unreachable.

**G, hint:** sort the answers by what happens on the last day. For the first i days, best(i) = max(best(i − 1), reward[i − 1] + best(i − 2)), with best(j) = 0 for j <= 0. If taking a reward blocks two days, change i − 2 to i − 3. Both take O(n) time, and O(1) space once you see what each value depends on. Greedily taking the bigger of each neighboring pair can miss a better total.

**H, hint:** reaching the same room twice may allow different moves next. Use (room, keys held) as the state, with the keys stored as a bitmask, and run BFS because every move costs one. Entering a room adds its key to the mask; going through a locked door needs its key. There are at most V × 2^K states. Scanning the edges for each mask gives O((V + E) × 2^K) time and O(V × 2^K) space for distances. A room you reached before picking up a key must be reachable again once you have it.

These exercises reuse familiar ideas on purpose. The point is to rebuild and justify the approach without being told the technique. Solving one reworded problem doesn't prove you can apply an idea everywhere.

## 29 Review pages and contribution method

Fill in this worksheet after a real attempt at a problem. On later reviews, keep the answers covered until you've tried to recall them.

| Field | Your notes |
| --- | --- |
| Problem and date | |
| Solved alone, or with help | |
| Simple solution that works | |
| Repeated or unneeded work | |
| Idea that removes it | |
| Assumptions it needs | |
| State, or what stays true | |
| Why each step keeps it correct | |
| Time and space cost | |
| Smallest example that breaks my first idea | |
| Coding mistake | |
| Variation to try next | |
| How the later review went | |

To add a new explanation to this guide, include: the exact problem, how to work out the solution, what stays true (or the recurrence), the cost and its assumptions, where the method breaks, and a practice link. Link to the original problem statements and respect their licenses. Show another approach only when it teaches a different decision, and compare the approaches instead of just listing code.

Keep the problem list separate from what you've mastered. A solution existing in the repository doesn't mean you understand it, and passing an example doesn't prove a solution is correct. A version covering every problem should keep the different valid approaches, and mark which explanations were reviewed and which were generated.

When you add a group of problems, test the explanation against an example that works and one that breaks it. When you add a new exercise, check its examples, edge cases, and reference solution against a simple separate solution on small inputs. A reworded story still needs an exact problem statement.

## 30 Advanced families and when they become useful

The main chapters cover the foundation. This chapter lists more advanced topics, and when each becomes worth learning. It's a map for further study; a table can't teach a technique on its own.

| Topic | When to look at it | Key idea, or what you must prove |
| --- | --- | --- |
| Divide and conquer | Pairs that cross between two halves can be handled quickly | Solve each half, and count every pair that crosses the split. |
| Merge sort counting | Count pairs (i, j) where the values satisfy an inequality | Sorted halves let one forward scan count the crossing pairs before merging. |
| Sweep line | Which items are active changes at sorted times or positions | Process events in order, decide how ties work, and keep the set of active items. |
| Meet in the middle | All subsets is too many, but half the subsets fits | Combine compatible halves without losing any rule. |
| Digit DP | Count numbers up to a huge bound with rules on their digits | Track the position, whether you're still matching the bound, and enough digit history. |
| State machine DP | Each step depends on a small mode, like holding a stock | Define the allowed moves, and whether updates use yesterday's or today's values. |
| Rerooting DP | You need a tree answer for every possible root | Combine what comes from the children and from the parent's side, without counting anything twice. |
| Binary lifting | Many "kth ancestor" or jump queries | Precompute jumps of 1, 2, 4, 8, … and combine them using the distance's binary digits. |
| Euler tour | Turn "is it in this subtree?" into a range query | Entry and exit times give each subtree one continuous range. |
| Minimum spanning tree | Connect every node with the least total edge weight | Use a cut or swap argument. Shortest routes are a different goal. |
| Strongly connected components | Treat each directed cycle as one unit | Merge nodes that can reach each other, which leaves a graph with no cycles. |
| Bridges and articulation points | Find edges or nodes whose removal disconnects the graph | Low-link values track what a DFS subtree can reach without its parent edge. |
| Eulerian path | Use every edge exactly once | Check degree and connectivity conditions. Edges and nodes are different questions. |
| All-pairs shortest paths | Many start-to-end queries on a small graph | Floyd–Warshall allows one more middle node per round; O(V³). |
| Max flow and matching | Assignments with capacities, or routes that can't share edges | Reverse edges let you undo earlier choices; prove the problem maps onto flow. |
| 0-1 BFS | Every edge costs exactly 0 or 1 | Push 0-cost moves to the front of a deque and 1-cost moves to the back. |
| KMP and the Z function | Strings with repeated prefix matches | Reuse what already matched instead of restarting at every position. |
| Manacher's algorithm | Palindrome lengths at every center in O(n) | Reuse mirrored information inside a known palindrome, then extend. |
| Sparse table | Range minimum (or similar) on a list that never changes | Precompute blocks of length 2ᵏ; overlapping blocks are fine for minimum and maximum. |
| DP speedups using order or convexity | A recurrence has extra structure | Prove the property you rely on; a familiar DP shape isn't enough. |
| Game DP | Two players take turns, each playing their best | Say what the current player's value means and how a move switches whose turn it is. |
| Geometry | The problem is about orientation, containment, or position in space | Define exact tests, the special cases, and how much numeric precision you need. |

In digit DP, leading zeros may mean "no digit chosen yet" rather than real zeros. Track whether the digits so far exactly match the bound; once you're below it, later digits are free. The memoization key must include everything that affects which digits can come next.

In game DP, storing a score difference often makes alternating turns simple. Your advantage is what you gain from a move minus your opponent's best advantage afterward. That only works for games where one player's gain is the other's loss. Don't use it for cooperative games.

A minimum spanning tree doesn't give shortest paths. The graph might have a short direct route that the tree leaves out. Ask whether you're adding up each chosen edge once, or adding up the cost of travelling a route.

In divide and conquer, count the work to combine the halves. Merge sort counting is usually O(n log n), but combining in O(n²) wipes out the gain. When counting pairs like a[i] > 2 × a[j], convert to a wider type before multiplying, and keep the original order of indexes through the split.

Advanced practice, when you need it: [LC 493 Reverse Pairs][p493], [LC 1851 Minimum Interval to Include Each Query][p1851], [LC 1755 Closest Subsequence Sum][p1755], [LC 2035 Partition Array Into Two Arrays to Minimize Sum Difference][p2035], [LC 2376 Count Special Integers][p2376], [LC 309 Best Time to Buy and Sell Stock with Cooldown][p309], [LC 834 Sum of Distances in Tree][p834], [LC 1483 Kth Ancestor of a Tree Node][p1483], [LC 1584 Min Cost to Connect All Points][p1584], [LC 1192 Critical Connections in a Network][p1192], [LC 332 Reconstruct Itinerary][p332], [LC 486 Predict the Winner][p486], [LC 1392 Longest Happy Prefix][p1392].

Before you code an unfamiliar advanced technique, read a full explanation of it. CP-Algorithms [S16] covers most of them. Learn the fact that makes the technique correct, and keep a simple correct version around to compare against on small inputs.

## 31 Sources and further reading

The explanations in this guide are written for it, covering standard techniques. The sources below offer study plans, formal algorithm references, language documentation, and research on learning. None of them proves that a certain number of patterns is enough, or guarantees an interview result.

**S1. NeetCode, How to Prepare for Coding Interviews.** A practical guide that stresses fundamentals, practicing problems grouped by pattern, and repetition. Its advice isn't from a controlled study. <https://blog.neetcode.io/p/prepare-coding-interviews>

**S2. Yangshun Tay, Grind 75 FAQ.** Explains how the list picks questions, covers topics, and mixes them. A useful study plan, though no single list is enough for everyone. <https://www.techinterviewhandbook.org/grind75/faq>

**S3. Sean Prashad, Leetcode Patterns.** A free list of practice problems with tips for choosing an approach. Treat each tip as an idea to check, not a rule. <https://seanprashad.com/leetcode-patterns/>

**S4. USACO Guide, How to Practice.** Collects different advice from competitive programmers on difficulty, when to read solutions, coding, and productive effort. <https://usaco.guide/general/practicing>

**S5. Margulieux, Morrison, and Decker, 2020. Reducing withdrawal and failure rates in introductory programming with subgoal labeled worked examples.** In a semester-long study of 265 students, worked examples with labeled steps raised early quiz scores and reduced failures and withdrawals. Average exam scores didn't improve significantly. So step-by-step explanations help, but this doesn't show lasting mastery. <https://doi.org/10.1186/s40594-020-00222-7>

**S6. Roediger and Karpicke, 2006. Test-Enhanced Learning.** Practicing recall helped people remember prose passages later better than rereading did. Applying this to rebuilding algorithms is a reasonable guess, not a tested result. <https://learninglab.psych.purdue.edu/downloads/2006/2006_Roediger_Karpicke_PsychSci.pdf>

**S7. Rohrer, Dedrick, Hartwig, and Cheung, 2020, published online 2019. A Randomized Controlled Trial of Interleaved Mathematics Practice.** Across 54 seventh-grade classes, mixing problem types in practice raised scores on a later test. The subject was school math, not LeetCode. <https://files.eric.ed.gov/fulltext/ED595322.pdf>

**S8. Gick and Holyoak, 1983. Schema Induction and Analogical Transfer.** Comparing similar examples helped people pull out the shared idea, which helped them apply it to new problems. That's why this guide compares problems side by side. <https://doi.org/10.1016/0010-0285(83)90002-6>

**S9. CP-Algorithms, Binary Search.** Covers yes/no tests that flip once, what the search boundaries keep true, and binary search on the answer. <https://cp-algorithms.com/num_methods/binary_search.html>

**S10. Rust standard library, BinaryHeap.** Documents ordering, `Reverse`, the operations, and their costs. <https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html>

**S11. CP-Algorithms, Dijkstra.** Explains why edges must not be negative, and why each settled distance is final. <https://cp-algorithms.com/graph/dijkstra.html>

**S12. CP-Algorithms, Disjoint Set Union.** Explains roots, path compression, union by size or rank, and the average cost per operation. <https://cp-algorithms.com/data_structures/disjoint_set_union.html>

**S13. Rust standard library, Collections.** Describes when to use each collection and what its operations cost. <https://doc.rust-lang.org/std/collections/index.html>

**S14. The Rust Programming Language, Storing UTF-8 Encoded Text with Strings.** Explains bytes, characters, indexing, and how strings are stored. <https://doc.rust-lang.org/book/ch08-02-strings.html>

**S15. AlgoMonster, algorithm selection flowchart and curriculum.** A source of prompts for choosing a technique. The flowchart suggests approaches to try; it doesn't prove any of them correct. <https://algo.monster/flowchart>

**S16. CP-Algorithms, algorithm reference index.** A directory of advanced graph, string, math, and data structure techniques. Read each technique's assumptions and proof before using it. <https://cp-algorithms.com/>

The study methods in Chapters 1 and 26 are this guide's recommendations, informed by these sources. Comparing related problems comes from S8; explaining each step comes from S5. Whether the advice works for you shows up in one place: solving problems on your own, days later.

## 32 Selected problem index

Every LeetCode problem mentioned in this guide, linked to its statement on LeetCode. The numbers are LeetCode's, not an order to solve them in. Try each problem before you open its solution.

| ID | Original problem statement |
| --- | --- |
| 1 | [Two Sum][p1] |
| 3 | [Longest Substring Without Repeating Characters][p3] |
| 5 | [Longest Palindromic Substring][p5] |
| 11 | [Container With Most Water][p11] |
| 15 | [3Sum][p15] |
| 19 | [Remove Nth Node From End of List][p19] |
| 20 | [Valid Parentheses][p20] |
| 21 | [Merge Two Sorted Lists][p21] |
| 22 | [Generate Parentheses][p22] |
| 23 | [Merge k Sorted Lists][p23] |
| 26 | [Remove Duplicates from Sorted Array][p26] |
| 28 | [Find the Index of the First Occurrence in a String][p28] |
| 33 | [Search in Rotated Sorted Array][p33] |
| 34 | [Find First and Last Position of Element in Sorted Array][p34] |
| 35 | [Search Insert Position][p35] |
| 39 | [Combination Sum][p39] |
| 45 | [Jump Game II][p45] |
| 46 | [Permutations][p46] |
| 47 | [Permutations II][p47] |
| 49 | [Group Anagrams][p49] |
| 50 | [Pow(x, n)][p50] |
| 51 | [N-Queens][p51] |
| 55 | [Jump Game][p55] |
| 56 | [Merge Intervals][p56] |
| 57 | [Insert Interval][p57] |
| 70 | [Climbing Stairs][p70] |
| 72 | [Edit Distance][p72] |
| 76 | [Minimum Window Substring][p76] |
| 78 | [Subsets][p78] |
| 79 | [Word Search][p79] |
| 84 | [Largest Rectangle in Histogram][p84] |
| 98 | [Validate Binary Search Tree][p98] |
| 104 | [Maximum Depth of Binary Tree][p104] |
| 110 | [Balanced Binary Tree][p110] |
| 127 | [Word Ladder][p127] |
| 128 | [Longest Consecutive Sequence][p128] |
| 131 | [Palindrome Partitioning][p131] |
| 133 | [Clone Graph][p133] |
| 136 | [Single Number][p136] |
| 139 | [Word Break][p139] |
| 141 | [Linked List Cycle][p141] |
| 142 | [Linked List Cycle II][p142] |
| 146 | [LRU Cache][p146] |
| 155 | [Min Stack][p155] |
| 167 | [Two Sum II - Input Array Is Sorted][p167] |
| 191 | [Number of 1 Bits][p191] |
| 198 | [House Robber][p198] |
| 200 | [Number of Islands][p200] |
| 201 | [Bitwise AND of Numbers Range][p201] |
| 206 | [Reverse Linked List][p206] |
| 207 | [Course Schedule][p207] |
| 208 | [Implement Trie (Prefix Tree)][p208] |
| 209 | [Minimum Size Subarray Sum][p209] |
| 210 | [Course Schedule II][p210] |
| 211 | [Design Add and Search Words Data Structure][p211] |
| 212 | [Word Search II][p212] |
| 215 | [Kth Largest Element in an Array][p215] |
| 218 | [The Skyline Problem][p218] |
| 232 | [Implement Queue using Stacks][p232] |
| 236 | [Lowest Common Ancestor of a Binary Tree][p236] |
| 238 | [Product of Array Except Self][p238] |
| 239 | [Sliding Window Maximum][p239] |
| 242 | [Valid Anagram][p242] |
| 295 | [Find Median from Data Stream][p295] |
| 300 | [Longest Increasing Subsequence][p300] |
| 303 | [Range Sum Query - Immutable][p303] |
| 307 | [Range Sum Query - Mutable][p307] |
| 309 | [Best Time to Buy and Sell Stock with Cooldown][p309] |
| 312 | [Burst Balloons][p312] |
| 315 | [Count of Smaller Numbers After Self][p315] |
| 322 | [Coin Change][p322] |
| 327 | [Count of Range Sum][p327] |
| 329 | [Longest Increasing Path in a Matrix][p329] |
| 332 | [Reconstruct Itinerary][p332] |
| 337 | [House Robber III][p337] |
| 338 | [Counting Bits][p338] |
| 347 | [Top K Frequent Elements][p347] |
| 377 | [Combination Sum IV][p377] |
| 380 | [Insert Delete GetRandom O(1)][p380] |
| 416 | [Partition Equal Subset Sum][p416] |
| 424 | [Longest Repeating Character Replacement][p424] |
| 435 | [Non-overlapping Intervals][p435] |
| 452 | [Minimum Number of Arrows to Burst Balloons][p452] |
| 486 | [Predict the Winner][p486] |
| 493 | [Reverse Pairs][p493] |
| 494 | [Target Sum][p494] |
| 496 | [Next Greater Element I][p496] |
| 518 | [Coin Change II][p518] |
| 525 | [Contiguous Array][p525] |
| 543 | [Diameter of Binary Tree][p543] |
| 547 | [Number of Provinces][p547] |
| 560 | [Subarray Sum Equals K][p560] |
| 643 | [Maximum Average Subarray I][p643] |
| 684 | [Redundant Connection][p684] |
| 703 | [Kth Largest Element in a Stream][p703] |
| 704 | [Binary Search][p704] |
| 718 | [Maximum Length of Repeated Subarray][p718] |
| 721 | [Accounts Merge][p721] |
| 739 | [Daily Temperatures][p739] |
| 743 | [Network Delay Time][p743] |
| 746 | [Min Cost Climbing Stairs][p746] |
| 752 | [Open the Lock][p752] |
| 787 | [Cheapest Flights Within K Stops][p787] |
| 834 | [Sum of Distances in Tree][p834] |
| 862 | [Shortest Subarray with Sum at Least K][p862] |
| 864 | [Shortest Path to Get All Keys][p864] |
| 875 | [Koko Eating Bananas][p875] |
| 907 | [Sum of Subarray Minimums][p907] |
| 974 | [Subarray Sums Divisible by K][p974] |
| 981 | [Time Based Key-Value Store][p981] |
| 994 | [Rotting Oranges][p994] |
| 1011 | [Capacity To Ship Packages Within D Days][p1011] |
| 1109 | [Corporate Flight Bookings][p1109] |
| 1143 | [Longest Common Subsequence][p1143] |
| 1192 | [Critical Connections in a Network][p1192] |
| 1235 | [Maximum Profit in Job Scheduling][p1235] |
| 1368 | [Minimum Cost to Make at Least One Valid Path in a Grid][p1368] |
| 1392 | [Longest Happy Prefix][p1392] |
| 1483 | [Kth Ancestor of a Tree Node][p1483] |
| 1584 | [Min Cost to Connect All Points][p1584] |
| 1631 | [Path With Minimum Effort][p1631] |
| 1755 | [Closest Subsequence Sum][p1755] |
| 1851 | [Minimum Interval to Include Each Query][p1851] |
| 2035 | [Partition Array Into Two Arrays to Minimize Sum Difference][p2035] |
| 2376 | [Count Special Integers][p2376] |

[p1]: https://leetcode.com/problems/two-sum/
[p3]: https://leetcode.com/problems/longest-substring-without-repeating-characters/
[p5]: https://leetcode.com/problems/longest-palindromic-substring/
[p11]: https://leetcode.com/problems/container-with-most-water/
[p15]: https://leetcode.com/problems/3sum/
[p19]: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
[p20]: https://leetcode.com/problems/valid-parentheses/
[p21]: https://leetcode.com/problems/merge-two-sorted-lists/
[p22]: https://leetcode.com/problems/generate-parentheses/
[p23]: https://leetcode.com/problems/merge-k-sorted-lists/
[p26]: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
[p28]: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
[p33]: https://leetcode.com/problems/search-in-rotated-sorted-array/
[p34]: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[p35]: https://leetcode.com/problems/search-insert-position/
[p39]: https://leetcode.com/problems/combination-sum/
[p45]: https://leetcode.com/problems/jump-game-ii/
[p46]: https://leetcode.com/problems/permutations/
[p47]: https://leetcode.com/problems/permutations-ii/
[p49]: https://leetcode.com/problems/group-anagrams/
[p50]: https://leetcode.com/problems/powx-n/
[p51]: https://leetcode.com/problems/n-queens/
[p55]: https://leetcode.com/problems/jump-game/
[p56]: https://leetcode.com/problems/merge-intervals/
[p57]: https://leetcode.com/problems/insert-interval/
[p70]: https://leetcode.com/problems/climbing-stairs/
[p72]: https://leetcode.com/problems/edit-distance/
[p76]: https://leetcode.com/problems/minimum-window-substring/
[p78]: https://leetcode.com/problems/subsets/
[p79]: https://leetcode.com/problems/word-search/
[p84]: https://leetcode.com/problems/largest-rectangle-in-histogram/
[p98]: https://leetcode.com/problems/validate-binary-search-tree/
[p104]: https://leetcode.com/problems/maximum-depth-of-binary-tree/
[p110]: https://leetcode.com/problems/balanced-binary-tree/
[p127]: https://leetcode.com/problems/word-ladder/
[p128]: https://leetcode.com/problems/longest-consecutive-sequence/
[p131]: https://leetcode.com/problems/palindrome-partitioning/
[p133]: https://leetcode.com/problems/clone-graph/
[p136]: https://leetcode.com/problems/single-number/
[p139]: https://leetcode.com/problems/word-break/
[p141]: https://leetcode.com/problems/linked-list-cycle/
[p142]: https://leetcode.com/problems/linked-list-cycle-ii/
[p146]: https://leetcode.com/problems/lru-cache/
[p155]: https://leetcode.com/problems/min-stack/
[p167]: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
[p191]: https://leetcode.com/problems/number-of-1-bits/
[p198]: https://leetcode.com/problems/house-robber/
[p200]: https://leetcode.com/problems/number-of-islands/
[p201]: https://leetcode.com/problems/bitwise-and-of-numbers-range/
[p206]: https://leetcode.com/problems/reverse-linked-list/
[p207]: https://leetcode.com/problems/course-schedule/
[p208]: https://leetcode.com/problems/implement-trie-prefix-tree/
[p209]: https://leetcode.com/problems/minimum-size-subarray-sum/
[p210]: https://leetcode.com/problems/course-schedule-ii/
[p211]: https://leetcode.com/problems/design-add-and-search-words-data-structure/
[p212]: https://leetcode.com/problems/word-search-ii/
[p215]: https://leetcode.com/problems/kth-largest-element-in-an-array/
[p218]: https://leetcode.com/problems/the-skyline-problem/
[p232]: https://leetcode.com/problems/implement-queue-using-stacks/
[p236]: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
[p238]: https://leetcode.com/problems/product-of-array-except-self/
[p239]: https://leetcode.com/problems/sliding-window-maximum/
[p242]: https://leetcode.com/problems/valid-anagram/
[p295]: https://leetcode.com/problems/find-median-from-data-stream/
[p300]: https://leetcode.com/problems/longest-increasing-subsequence/
[p303]: https://leetcode.com/problems/range-sum-query-immutable/
[p307]: https://leetcode.com/problems/range-sum-query-mutable/
[p309]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[p312]: https://leetcode.com/problems/burst-balloons/
[p315]: https://leetcode.com/problems/count-of-smaller-numbers-after-self/
[p322]: https://leetcode.com/problems/coin-change/
[p327]: https://leetcode.com/problems/count-of-range-sum/
[p329]: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
[p332]: https://leetcode.com/problems/reconstruct-itinerary/
[p337]: https://leetcode.com/problems/house-robber-iii/
[p338]: https://leetcode.com/problems/counting-bits/
[p347]: https://leetcode.com/problems/top-k-frequent-elements/
[p377]: https://leetcode.com/problems/combination-sum-iv/
[p380]: https://leetcode.com/problems/insert-delete-getrandom-o1/
[p416]: https://leetcode.com/problems/partition-equal-subset-sum/
[p424]: https://leetcode.com/problems/longest-repeating-character-replacement/
[p435]: https://leetcode.com/problems/non-overlapping-intervals/
[p452]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
[p486]: https://leetcode.com/problems/predict-the-winner/
[p493]: https://leetcode.com/problems/reverse-pairs/
[p494]: https://leetcode.com/problems/target-sum/
[p496]: https://leetcode.com/problems/next-greater-element-i/
[p518]: https://leetcode.com/problems/coin-change-ii/
[p525]: https://leetcode.com/problems/contiguous-array/
[p543]: https://leetcode.com/problems/diameter-of-binary-tree/
[p547]: https://leetcode.com/problems/number-of-provinces/
[p560]: https://leetcode.com/problems/subarray-sum-equals-k/
[p643]: https://leetcode.com/problems/maximum-average-subarray-i/
[p684]: https://leetcode.com/problems/redundant-connection/
[p703]: https://leetcode.com/problems/kth-largest-element-in-a-stream/
[p704]: https://leetcode.com/problems/binary-search/
[p718]: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
[p721]: https://leetcode.com/problems/accounts-merge/
[p739]: https://leetcode.com/problems/daily-temperatures/
[p743]: https://leetcode.com/problems/network-delay-time/
[p746]: https://leetcode.com/problems/min-cost-climbing-stairs/
[p752]: https://leetcode.com/problems/open-the-lock/
[p787]: https://leetcode.com/problems/cheapest-flights-within-k-stops/
[p834]: https://leetcode.com/problems/sum-of-distances-in-tree/
[p862]: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
[p864]: https://leetcode.com/problems/shortest-path-to-get-all-keys/
[p875]: https://leetcode.com/problems/koko-eating-bananas/
[p907]: https://leetcode.com/problems/sum-of-subarray-minimums/
[p974]: https://leetcode.com/problems/subarray-sums-divisible-by-k/
[p981]: https://leetcode.com/problems/time-based-key-value-store/
[p994]: https://leetcode.com/problems/rotting-oranges/
[p1011]: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
[p1109]: https://leetcode.com/problems/corporate-flight-bookings/
[p1143]: https://leetcode.com/problems/longest-common-subsequence/
[p1192]: https://leetcode.com/problems/critical-connections-in-a-network/
[p1235]: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
[p1368]: https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/
[p1392]: https://leetcode.com/problems/longest-happy-prefix/
[p1483]: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/
[p1584]: https://leetcode.com/problems/min-cost-to-connect-all-points/
[p1631]: https://leetcode.com/problems/path-with-minimum-effort/
[p1755]: https://leetcode.com/problems/closest-subsequence-sum/
[p1851]: https://leetcode.com/problems/minimum-interval-to-include-each-query/
[p2035]: https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/
[p2376]: https://leetcode.com/problems/count-special-integers/

[S1]: https://blog.neetcode.io/p/prepare-coding-interviews
[S2]: https://www.techinterviewhandbook.org/grind75/faq
[S3]: https://seanprashad.com/leetcode-patterns/
[S4]: https://usaco.guide/general/practicing
[S5]: https://doi.org/10.1186/s40594-020-00222-7
[S6]: https://learninglab.psych.purdue.edu/downloads/2006/2006_Roediger_Karpicke_PsychSci.pdf
[S7]: https://files.eric.ed.gov/fulltext/ED595322.pdf
[S8]: https://doi.org/10.1016/0010-0285(83)90002-6
[S9]: https://cp-algorithms.com/num_methods/binary_search.html
[S10]: https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
[S11]: https://cp-algorithms.com/graph/dijkstra.html
[S12]: https://cp-algorithms.com/data_structures/disjoint_set_union.html
[S13]: https://doc.rust-lang.org/std/collections/index.html
[S14]: https://doc.rust-lang.org/book/ch08-02-strings.html
[S15]: https://algo.monster/flowchart
[S16]: https://cp-algorithms.com/