Chapter 01 — Array and String

At the end of this chapter you can spot the three habits that turn a linear problem quadratic, and you will have met the two-index sweep that the next six chapters are all variations on.

Nine problems: 1768, 1431, 605, 345, 1071, 151, 443, 238, 334.

This chapter has no single trick. It is the chapter where you learn what an operation costs, because every later pattern is an answer to a cost you first have to be able to see.

1. Three ways to hide a quadratic

Every problem in this chapter is linear when written well. Each one also has an obvious version that is not, and in all three cases the expensive step looks like ordinary code.

Recomputing something that never changed. In problem 1431 the maximum is fixed before the loop starts. Writing max(candies) inside the loop is one short word and it is the whole difference between linear and quadratic. Nothing about the line looks expensive.

Rebuilding a string as you go. result = result + char copies everything accumulated so far, every time. Ten thousand characters means fifty million copied ones. Collect into a list and "".join at the end instead — the version that looks less elegant is the fast one.

Chopping the front off a sequence. word = word[1:] reads like "advance", but it copies the entire remainder. It is the most natural way to express "move on to the next character" and it is quadratic. Use an index.

These are not stylistic preferences. The charts under each problem below are measurements of exactly these three lines, and every one of them bends upward.

2. The sweep

Most of this chapter is one shape: walk the array once, carry a small amount of state, and answer as you go.

state = <initial>
for item in items:
    state = update(state, item)
    answer = combine(answer, state)

What differs between problems is only what state holds:

Problem 238 is worth pausing on. It looks like it needs a value per position that depends on every other position, which sounds quadratic by nature. It is not: the product of everything except position i splits into everything to its left times everything to its right, and each half is a single sweep. When a per-position answer depends on both sides, try two sweeps before you try anything clever.

3. Two indices, moving apart

Three problems here use a second index rather than a second loop.

• 345 — two pointers walking inwards, skipping anything that is not a vowel.
• 443 — read and write moving in the same direction at different speeds.
• 151 — two indices swapping words inwards.

Problem 443 is the one to remember. write never overtakes read, because a run of k characters always compresses into at most k slots. That inequality is what makes rewriting the input safe, and it is the kind of argument an interviewer is listening for.

4. The problems

5. Recognition

Problem 1071 is the odd one out and worth its place for that reason. str1 + str2 == str2 + str1 is not a scan at all — it is a fact about strings that replaces the search entirely. Not every array problem is solved by walking the array.

6. Traps

7. Drills

Chapter 02 — Two Pointers

At the end of this chapter you can tell which of the two pointer arrangements a problem wants, and justify out loud why discarding half a search space loses nothing.

Four problems: 283, 392, 11, 1679.

left, right = 0, len(a) - 1        # converging
while left < right:
    if <the left one is to blame>: left += 1
    else:                          right -= 1

write = 0                          # same direction, different speeds
for read in range(len(a)):
    if keep(a[read]):
        a[write] = a[read]; write += 1

1. Two arrangements, not one

The name covers two different techniques that share only the index count.

Converging — the pointers start at opposite ends and move towards each other. Used when each step can rule something out: problems 11 and 1679.

Same direction — both move left to right, one faster than the other. Used when you are partitioning or matching: problems 283 and 392.

Deciding which you need takes one question: does the array have two ends that mean something? In problem 11 the ends are the widest possible pair. In problem 1679, after sorting, the ends are the smallest and largest values. In problem 283 the ends mean nothing at all — what matters is the boundary between what you have kept and what you have not.

2. Why discarding is allowed

Converging pointers only work if each step can be proved to lose nothing. This is the whole content of the pattern and the only part an interview cares about.

Problem 11. Start with the widest pair. Its area is capped by the shorter line. Every remaining pair that still includes that shorter line is narrower, and no taller, so none of them can beat the area you just measured. The shorter line is therefore finished, and moving it inwards discards only pairs that were already accounted for.

Problem 1679. After sorting, if the smallest and largest values sum to less than k, then the smallest value summed with anything is less than k — the largest was its best chance. It can never be paired, so drop it.

Both arguments have the same shape: one of the two pointers is provably done, and you can say which one and why. If you cannot make that argument, converging pointers are the wrong tool and you are about to write a fast wrong answer.

3. The same-direction arrangement

Here the two indices have jobs rather than positions.

write = 0
for read in range(len(nums)):
    if nums[read] != 0:
        nums[write], nums[read] = nums[read], nums[write]
        write += 1

read visits everything; write marks where the next kept element belongs. The invariant is worth stating: everything before write is kept and in order; everything between write and read is discarded.

The swap rather than the assignment is the neat part of problem 283. Whatever write is pointing at is guaranteed to be a zero, so swapping puts that zero exactly where it needs to end up, and no second pass is needed to fill the tail.

4. The problems

5. Recognition

Not this pattern: if the values can be negative and the condition is a sum threshold, the ruling-out argument fails — adding an element can help rather than hurt. That is prefix sum territory, chapter 04.

6. Traps

7. Drills

Chapter 03 — Sliding Window

At the end of this chapter you can tell from the wording of a problem alone that it wants a window over a contiguous stretch, write both loops from memory, and say exactly why the second one is linear and not quadratic.

Four problems: 643, 1456, 1004, 1493. All four are the same eight lines.

left = 0
for right in range(len(a)):
    add(a[right])                 # the window grows on the right
    while not legal():            # and only shrinks when it has to
        remove(a[left])
        left += 1
    best = max(best, right - left + 1)

1. The idea

A window is a contiguous slice a[left..right]. The brute force tries every start against every end: roughly n²/2 slices, each one examined from scratch as though the previous n²/2 had never happened.

The observation that kills the quadratic is small. Neighbouring windows overlap almost entirely. A window of width k and the next one share k−1 elements. If you already know something about the first, you should not have to earn it again for the second — you should be able to repair it.

That repair is only possible when the quantity you track is reversible: undoing the element that leaves must be as cheap as applying the element that arrives.

That last row is the honest boundary of the pattern. Sliding Window Maximum is not in the LeetCode 75, and the reason is instructive: it needs a monotonic deque precisely because a plain sliding window cannot carry a maximum. When a problem looks like a window but the quantity is irreversible, you are in a different chapter.

The invariant is the real work

Before writing the loop, finish this sentence: at the top of every iteration, the window is …

• 643, 1456 — the window is exactly k wide, and window is its sum.
• 1004, 1493 — the window is legal, and it is the longest legal window ending at right.

Write the invariant down. Every bug in this pattern is an invariant that is true, but at the wrong moment in the loop.

2. Two templates, not one

The four problems split cleanly, and the split is visible in the problem statement.

Fixed width — the statement names the size.

window = sum(a[:k])                    # build the first window explicitly
best = window
left = 0
for right in range(k, len(a)):
    window += a[right]                 # one element arrives
    window -= a[left]                  # one element leaves
    left += 1
    best = max(best, window)

Variable width — the statement names a condition instead of a size.

left = 0
for right in range(len(a)):
    add(a[right])
    while not legal():
        remove(a[left])
        left += 1
    best = max(best, right - left + 1)

Why the second one is linear

This is the question that gets asked out loud in interviews, and the wrong answer is extremely common: "there is a while loop inside a for loop, so it is O(n²)."

It is not. left only ever increases, and it never passes right. Across the entire run the inner loop body executes at most n times in total, not n times per iteration. Each index enters the window exactly once and leaves at most once, so the total work is bounded by 2n.

Nesting is a fact about the source code. Complexity is a fact about the execution. The charts under the four problems below are that distinction, measured.

3. The problems

4. Recognition

What in a statement means window:

And the condition must have one property, which is what licenses shrinking from the left: if a window is illegal, no window containing it is legal. Adding elements can only make things worse. That is why moving left forward is safe — you are never discarding a window that would have turned out fine.

Not this pattern:

That last row deserves a moment. "Longest subarray with sum ≤ k" is a sliding window when all values are positive, and is not one when negatives are allowed, because the licensing property above fails. Most people who have the pattern memorised but not understood walk straight into it.

5. Traps

The last one is worth checking for by eye. If your loop body contains sum(, max(, count( or a slice over the window, you have written the brute force with extra steps.

6. Drills

Chapter 04 — Prefix Sum

At the end of this chapter you can recognise the smallest pattern in the book, and see why it keeps reappearing inside larger problems.

Two problems: 1732, 724.

running = 0
for i in range(len(nums)):
    running += nums[i]        # running == sum of nums[0..i]

1. The idea

The sum of any stretch nums[i..j] is prefix[j] - prefix[i-1]. That single identity is the whole pattern. Once the prefix sums exist, every range sum is a subtraction rather than a loop, which turns a per-query scan into a per-query constant.

The two problems here use the identity in its two smallest forms.

Problem 1732 does not even need an array of prefixes. The altitude after leg i is the prefix sum, so one running total does it. This is prefix sum reduced to a single variable — and it is why the pattern is easy to miss: it can look like nothing at all.

Problem 724 needs both directions at once. The sum to the left of position i is the running total; the sum to its right is total - left - nums[i]. The right-hand side never has to be computed. That subtraction is the moment the problem stops being quadratic, and it is the identity above with the arithmetic rearranged.

2. Where it really earns its keep

Neither problem in this chapter needs the array of prefixes, which understates the pattern. Its real power shows up when it is combined with a hash map, and that combination is worth knowing even though the LeetCode 75 does not test it directly:

How many subarrays sum to exactly k? For each position, the number of earlier prefixes equal to running - k is the number of subarrays ending here. Count the prefixes you have seen in a map, and the whole thing is one pass.

This is the standard answer to a question that looks like a sliding window and is not, because negative values break the window's shrink argument (chapter 03, section 4). If you remember one thing beyond this chapter's two problems, remember that sliding window and prefix sum divide the same territory along the sign of the values.

3. The problems

4. Recognition

5. Traps

6. Drills

Chapter 05 — Hash Map and Set

At the end of this chapter you can read the phrase that means set and the phrase that means map, and you will never again write in on a list inside a loop by accident.

Four problems: 2215, 1207, 1657, 2352.

1. The idea

A hash map trades memory for time: it turns "is this here?" and "how many of these are there?" from a walk into a single step. That is the entire pattern. What makes it worth a chapter is that the walk and the single step look identical in Python source.

value in some_list      # walks the whole list — O(n)
value in some_set       # one lookup — O(1)

One character of difference at the definition site, an entire order of growth apart at the call site. This is the single most common accidental quadratic in interview code, and unlike a nested loop it is invisible when skimming.

2. Which structure, from which words

Problem 1207 needs both, one after the other, and that is the point of it: a map counts the values, then a set checks whether those counts collide. Two questions, two structures, one pass each. People who try to answer both with one structure end up comparing every count against every other.

3. What can be a key

Problem 2352 is here to teach one fact: a tuple can be a dictionary key and a list cannot.

That single conversion collapses a triple loop to a double one. Comparing every row against every column costs n rows × n columns × n cells. Counting the rows into a map keyed by tuple(row) makes each column a single lookup, and the count stored against the key handles duplicated rows without any extra work.

The general lesson is bigger than the problem: when you find yourself comparing whole sequences against each other, ask whether the sequence can be made hashable and looked up instead.

4. Counting is a means, not an end

Problem 1657 looks like a counting problem and is really a question about invariants. You are allowed two operations, and rather than searching for a sequence of them, you ask what neither operation can change:

• reordering characters cannot change how often each letter occurs;
• swapping two letters wholesale cannot change which letters are present, nor the multiset of frequencies — only which letter carries which frequency.

So two strings are close exactly when they have the same set of letters and the same sorted list of counts. The map is just how you compute those two facts. When a problem gives you operations, look for what they preserve before you look for a sequence of them.

5. The problems

6. Traps

The fourth row deserves a note. Python dictionaries preserve insertion order and sets do not preserve anything you should rely on. If the statement says the order of the output does not matter, say so out loud in an interview rather than leaving it ambiguous.

7. Drills

Chapter 06 — Stack

At the end of this chapter you can hear the phrase "the most recent one" in a problem statement even when it is not written there, and you will know that a Python list is already a stack.

Three problems: 2390, 735, 394.

stack = []
for item in items:
    if <item cancels or closes something>:
        top = stack.pop()
        ...
    else:
        stack.append(item)

1. The idea

A stack is the right structure whenever the thing you need next is the thing you saw most recently. That phrase is the whole pattern, and problem statements almost never use it — they say something that means it instead:

In Python you do not need a class. A list with append and pop is a stack, both operations are constant time, and stack[-1] peeks at the top.

2. Nesting is the loudest signal

Problem 394 is the archetype. 3[a2[c]] cannot be handled left to right with a couple of variables, because when you reach the inner 2[c] you are in the middle of building the outer group and must not lose it.

The stack holds exactly what you have to put down to work on something else:

elif char == "[":
    stack.append((current, number))   # remember the outer job
    current = ""; number = 0          # start the inner one
elif char == "]":
    previous, count = stack.pop()     # resume the outer job
    current = previous + current * count

Whenever an inner result has to be folded into an outer one, the stack holds the outer context. That sentence covers bracket matching, expression evaluation, nested decoding and the iterative form of any recursion.

The other half of problem 394 is a plain parsing trap: 10[a] has a two-digit count, so the number must be accumulated as number * 10 + digit. A surprising number of otherwise correct solutions fail on exactly that input.

3. One item can cancel many

Problem 735 adds the wrinkle that a single new element may destroy several stack entries before it settles. The loop is therefore inside the iteration, not beside it:

while alive and asteroid < 0 and stack and stack[-1] > 0:

Four conditions, and each one is load-bearing: still alive, moving left, something to hit, and that something moving right. Getting this to read clearly is most of the work, and the alive flag exists so that the decision to push happens in exactly one place.

This is amortised linear for the same reason the sliding window is: every asteroid is pushed at most once and popped at most once, so the inner while runs at most n times across the entire loop.

4. The problems

5. Traps

6. Drills

Chapter 07 — Queue

At the end of this chapter you know when oldest first is the rule, why list.pop(0) is a trap, and how a queue turns an optimal-play question into a simulation.

Two problems: 933, 649.

from collections import deque

queue = deque()
queue.append(x)      # arrive at the back
queue.popleft()      # leave from the front — O(1)

1. The idea

A stack answers "the most recent one"; a queue answers "the oldest one". The two problems here are chosen because neither of them says the word queue.

Problem 933 hides it in the passage of time. Calls expire in the order they arrived, so the one that stops counting first is always the one at the front. The window slides over timestamps rather than over indices — but the structure of chapter 03 is intact: each call enters once and leaves at most once, so a thousand pings cost a thousand steps, not a thousand scans.

Problem 649 hides it in the phrase "take turns in order, repeatedly". A senator who acts and survives goes to the back of the line for the next round. That is a queue, and the trick for handling round after round is to rejoin at index + n, which places them behind everyone still waiting in the current round without any round-counting logic at all.

2. pop(0) is not popleft()

list.pop(0) removes the front of a list by shifting every remaining element down one slot. It is O(n), it looks exactly like O(1), and it turns a linear simulation into a quadratic one. collections.deque exists precisely for this and removes from either end in constant time.

This is the queue chapter's version of chapter 05's in-on-a-list: an operation whose cost is invisible at the call site. If you write a queue with a plain list, that is where the time limit will catch you.

3. Optimal play without a search

Problem 649 says "assuming everyone plays optimally", which sounds like it wants game-tree search. It does not, and recognising why is the real skill here.

A senator's only weapon is to ban an opponent. Which one? The next opponent due to act — because that is the only opponent who can act before them, and any other choice leaves a threat alive that acts sooner. There is no branching to explore: optimal play is forced, and the entire problem collapses to a simulation.

When a statement says "optimally", first check whether the optimal move is forced. Often the phrase is there to remove ambiguity, not to demand a search.

4. The problems

5. Traps

6. Drills

Chapter 08 — Linked List

At the end of this chapter you can rewire a list without losing the rest of it, find the middle in one pass, and recognise that most linked-list problems are array techniques adapted to a structure that only goes one way.

Four problems: 206, 2095, 328, 2130.

previous, current = None, head
while current is not None:
    following = current.next     # save it BEFORE you overwrite the link
    current.next = previous
    previous, current = current, following

1. One rule

Never overwrite a pointer you still need.

That is the whole chapter, and every bug in it is a violation of that sentence. In the reversal above, current.next = previous destroys the only reference to the rest of the list. Saving it into following first is not a style choice — without it the remaining nodes are unreachable and gone.

The habit that prevents this: before writing any assignment to a .next, ask what was that pointer holding, and do I still need it? If yes, name it first.

Problem 328 makes the same point one level up. Once the weaving starts, nothing points at the head of the even chain any more, so even_head is saved before the loop. Nothing in the loop looks like it needs it; the final line does.

2. Two pointers, one direction

An array lets you jump to index n // 2. A linked list does not. Two pointers at different speeds do:

slow, fast = head, head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

When fast has taken n steps, slow has taken n/2. That is problem 2095, and the only difficulty is the offset: to delete a node you must stop on the one before it, so fast starts two nodes along rather than at the head. Which offset you need depends on whether the length is odd or even and on whether you want the node or its predecessor — decide it by walking a four-element list on paper, not by guessing.

The two-condition loop guard is not decoration either. fast is not None handles even lengths, fast.next is not None handles odd ones, and dropping either produces an AttributeError on exactly one parity of input.

3. Chapter 02, on a structure that only goes forwards

Problem 2130 asks you to pair the front of the list with the back — the converging two pointers of chapter 02. You cannot walk backwards, so instead of changing the technique you change the list:

1. find the middle (fast and slow),
2. reverse the second half (the loop from section 1),
3. walk both halves forwards in step.

All three techniques of this chapter in one solution, and a good illustration of a general move: when a structure will not support your technique, ask whether you can cheaply convert the structure instead of abandoning the technique.

4. The problems

5. Recognition

That last row is worth reading carefully. Copying into a list, solving the array problem and rebuilding is usually correct and usually accepted — but it is O(n) space, and the constraint is normally there precisely to rule it out.

6. Traps

7. Drills

Chapter 09 — Binary Tree, Depth First

At the end of this chapter you can write a tree recursion by answering two questions, and you can tell whether the information a problem needs flows down the tree or up it.

Six problems: 104, 872, 1448, 1372, 236, 437.

def solve(node):
    if node is None:
        return <the answer for nothing>
    left = solve(node.left)
    right = solve(node.right)
    return <combine left, right and node.val>

1. Two questions write the function

Every problem in this chapter is answered by filling in two blanks:

1. What is the answer for an empty tree?
2. Given the answers for both subtrees, what is the answer here?

For problem 104 those are zero and one more than the larger. That is the entire solution, and the recursion is not something you trace through — it is something you trust once the two blanks are right.

If you find yourself mentally simulating the call stack, the two blanks are not yet clear. Go back and state them in English first.

2. Which way does the information flow?

This is the distinction that separates the easy half of the chapter from the hard half.

Upwards. The answer is built from the subtrees' answers, on the way back out of the recursion. Problems 104, 872 and 236 work this way. The function returns something.

Downwards. The node needs to know something about its ancestors, which the subtrees cannot possibly tell it. Problems 1448, 1372 and 437 work this way. The function takes an extra parameter.

When a problem mentions the path from the root, information flows down. When it mentions subtrees, it flows up. Several problems need both at once, which is why the signature grows a parameter and keeps a return value.

3. Two solutions worth studying

Problem 236 has an unusually clever return contract: the function returns either the answer, or one of the two targets, or nothing — and the caller cannot tell which. It does not need to. A node that hears back from both children is the meeting point; a node that hears from one passes the report upwards unchanged. Trying to make the function return "the answer, and also whether each target was found" produces far more code and no more correctness.

Problem 437 is chapter 04 wearing a tree costume. The running total from the root to the current node is a prefix sum, and a downward path ending here with sum k exists once for every ancestor whose prefix is running - k. A map of prefix counts answers all of them at once. The line people forget is the last one:

counts[running] -= 1     # leaving this node: it is no longer an ancestor

Without it, prefixes from a sibling branch leak into the count. Any map that describes "the path above me" must be undone on the way back up.

4. The problems

5. Traps

The fifth row is measured under problem 1372: on a balanced tree the naive per-node walk is linear, because almost every node is a leaf with nothing below it. It only degrades on a skewed tree — which is why the chart there is measured against a zigzag spine and not a comfortable balanced tree.

6. Drills

Chapter 10 — Binary Tree, Breadth First

At the end of this chapter you can process a tree one level at a time, and you know the single line that makes levels visible in a queue.

Two problems: 199, 1161.

queue = deque([root])
while queue:
    width = len(queue)           # everything in the queue right now is one level
    for _ in range(width):
        node = queue.popleft()
        ...
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

1. The idea

Depth-first traversal knows nothing about levels — it plunges to the bottom of one branch before looking at the second child of the root. When a problem says per level, row by row, top to bottom, or the first node at each depth, you want breadth first.

A queue on its own gives you the nodes in level order but does not tell you where one level ends. The line that fixes this is width = len(queue). At the top of each outer iteration the queue holds exactly one complete level, so capturing its length before draining it turns an undifferentiated stream into rows.

That one line is the whole pattern. Problem 199 takes the last node of each row; problem 1161 sums each row. Nothing else differs.

2. Why not depth-first with a depth parameter?

You can solve both of these problems with DFS, passing the depth down and indexing into a list of results. It works and it is a perfectly good answer. Know both, and know the trade-off:

• BFS stops early when the answer is at a shallow level, and its memory is the width of the widest level — which for a complete tree is n/2.
• DFS uses memory proportional to the depth, which for a balanced tree is log n, but must visit the whole tree.

For "the first level satisfying X", BFS can stop as soon as it finds one and DFS cannot. That is the real reason the distinction matters.

3. The naive version is not always worse

The brute force in this chapter re-descends from the root once per level. On a balanced tree that is still linear overall — the early levels are tiny and the cost is dominated by the last one. It only becomes quadratic on a skewed tree, where each of the n levels costs a walk of length n.

So both charts here are measured against a one-node-per-level spine. This is worth internalising beyond the chapter: a tree algorithm's complexity usually depends on the shape of the tree, and the honest number is the one from the worst shape, not the comfortable one.

4. The problems

5. Traps

6. Drills

Chapter 11 — Binary Search Tree

At the end of this chapter you can use the ordering property rather than merely knowing it, and you can delete a node from a BST without breaking it.

Two problems: 700, 450.

1. The property, and using it

A binary search tree keeps every value in the left subtree below the node and every value in the right subtree above it. Two consequences do all the work:

1. A comparison at a node discards an entire subtree. That is binary search, with pointers where chapter 15 has indices, and the same halving argument.
2. An in-order traversal visits the values in sorted order. Which means "the k-th smallest", "validate this tree" and "find the successor" are all in-order questions.

Problem 700 exists to make the first point unmissable. A plain traversal finds the value in O(n) and passes the tests; using the ordering finds it in O(log n). The measurement under that problem is the difference, and it is the whole reason the word search is in the name.

The cost of a BST operation is the depth, not the size — O(log n) only when the tree is reasonably balanced. Insert sorted data into an unbalanced BST and you get a linked list with extra steps, and every operation becomes O(n). Real implementations (red-black, AVL, B-trees) exist entirely to prevent that.

2. Deletion, the only fiddly operation

Problem 450 is the one BST operation that needs real care, and the case split is the answer:

• No children — return None in its place.
• One child — return that child in its place.
• Two children — do not delete the node at all.

The third case is the trick. A node with two children cannot simply be removed, because neither child can take its place without displacing the other. So instead you overwrite its value with its in-order successor — the leftmost node of its right subtree, which is the smallest value still larger than it, and therefore the only value that can sit there without breaking the ordering. Then you delete that node from the right subtree, and by construction it has at most one child, so you are back to an easy case.

The other thing to notice is the shape of the recursion:

root.left = deleteNode(root.left, key)

Each call returns the new root of the subtree it was given, and the caller reattaches it. This return-and-reattach idiom is how tree modification is written without carrying parent pointers around, and it appears in insertion and balancing code as well.

3. The problems

4. Traps

5. Drills

Chapter 12 — Graphs, Depth First

At the end of this chapter you can recognise a graph in a statement that never says the word, and you know the one line that separates a search from an infinite loop.

Four problems: 841, 547, 1466, 399.

visited = {start}
stack = [start]
while stack:
    node = stack.pop()
    for nxt in neighbours[node]:
        if nxt not in visited:
            visited.add(nxt)        # mark on PUSH, not on pop
            stack.append(nxt)

1. Naming the graph

None of these four problems says "graph". Each one hands you something else and expects you to see it:

The reflex to build: whenever the input is a list of pairs, a list of lists of indices, or a matrix of 0s and 1s, say the words "nodes and edges" out loud and see whether the question becomes reachability, components, or shortest path. Almost always it does.

2. The visited set is the algorithm

Without it a cycle loops forever; with it every node is processed once and the whole search is linear in nodes plus edges. Two details are worth getting right:

Mark on push, not on pop. If you mark a node visited only when you take it off the stack, the same node can be pushed many times before it is ever popped, and the stack can blow up to the size of the edge list. Marking at push time keeps each node in the stack once.

Use a set, or an array of booleans — never a list. nxt not in visited on a list is a linear scan (chapter 05), which quietly turns a linear search into a quadratic one.

3. Recursion or a stack?

Both are depth-first. The explicit stack above is what this chapter uses, for one practical reason: Python's recursion limit is 1000 by default, and a graph problem with 10⁵ nodes in a chain will hit it. An explicit stack cannot overflow.

Recursion is more readable when you need work done on the way back out — the tree chapters are full of that. Reach for the stack when you only need to visit, and for recursion when each node must combine answers from its children.

4. Counting components

Problem 547 is the pattern for "how many groups", and it is a loop around a search:

for start in range(n):
    if not visited[start]:
        provinces += 1
        <search from start>

One shared visited array across every search — that is what stops a province being counted twice. The same three lines answer "count islands", "count friend circles" and every other component-counting problem.

5. Edges that carry something

Problems 1466 and 399 both attach data to the edge rather than the node.

In 1466, each road is stored twice, once per direction, tagged with whether traversing it means going against the arrow. A single walk outwards from city 0 then counts the roads that must be flipped, because those are precisely the ones crossed against their direction. Storing an undirected copy of a directed graph so that you can traverse it, while keeping the direction as data, is a move worth remembering.

In 399, the weight is a ratio, and the answer to a query is the product along a path. Edges in one direction carry v, the reverse carries 1/v, and an unanswerable query is simply one with no path.

6. The problems

7. Traps

8. Drills

Chapter 13 — Graphs, Breadth First

At the end of this chapter you know the one question that decides between DFS and BFS, and you can start a search from many places at once.

Two problems: 1926, 994.

1. The question that decides

Does the answer involve a distance?

If yes, breadth first. If no, either will do and DFS is usually shorter to write.

BFS visits nodes in order of their distance from the start. That single property is why the first border cell it touches in problem 1926 is the nearest exit — not merely an exit. DFS would find one too, and it would be wrong, and no test case built from a small example would tell you.

The property only holds while every edge costs the same. The moment edges have different weights you need Dijkstra, which is this search with a heap (chapter 14) instead of a queue.

2. Many starting points

Problem 994 is the one to remember from this chapter. Every already-rotten orange begins spreading at the same moment, so they all go into the queue before the loop starts:

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 2:
            queue.append((r, c))     # every source, at distance zero

The search then proceeds exactly as with one source, and every cell is reached by whichever source is nearest. Multi-source BFS costs nothing extra and answers "distance to the nearest X" for every cell in one pass — a genuinely useful thing to know, and much harder to see if you have only ever started a search from a single node.

Counting the fresh oranges up front is the other half. It turns "did anything survive?" into a comparison against a counter instead of another full scan of the grid.

3. Levels, again

Both problems need to know how far they have gone, and the two ways to do it are worth distinguishing:

• Carry the distance in the queue entry — (r, c, steps). Simple, and right when different items are at different distances.
• Drain one level at a time with for _ in range(len(queue)), the trick from chapter 10. Right when the question is about rounds, as in problem 994 where the answer is a count of minutes.

Either works for either problem. Using the level form where the statement talks about rounds keeps the code closer to the words.

4. Grids are graphs

A grid problem rarely builds an adjacency list. The neighbours of (r, c) are computed:

STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))
for dr, dc in STEPS:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols and <passable>:
        ...

The bounds check is the whole of the error surface. Writing the four offsets as a named constant, and the bounds check once, is worth doing every time — the alternative is four copy-pasted branches and one of them has a typo.

Marking a cell as visited by writing into the grid itself — a wall in 1926, a rotten orange in 994 — costs no extra memory. It also destroys the input, which is why both problems here copy the grid before running.

5. The problems

6. Traps

7. Drills

Chapter 14 — Heap and Priority Queue

At the end of this chapter you can tell when you need a heap rather than a sort, and you will have met the counter-intuitive trick that makes half of these problems work.

Four problems: 215, 2336, 2462, 2542.

import heapq
heapq.heappush(h, x)      # O(log n)
heapq.heappop(h)          # O(log n) -- always the SMALLEST
h[0]                      # peek, O(1)
heapq.heappush(h, -x)     # Python has no max-heap: negate

1. Sort or heap?

Sorting gives you the whole order for n log n. A heap gives you the extreme for log n, and keeps giving as the collection changes. The rule:

Problem 2336 is the clearest case for a heap over a sort: numbers come back between queries, so there is no fixed collection to sort at all.

2. The trick: a min-heap for the k largest

This is the part that reads backwards the first time.

To keep the k largest values, hold a min-heap of size k. Its root is the weakest of your keepers — exactly the one to throw away when something better arrives:

heapq.heappush(keepers, value)
if len(keepers) > k:
    heapq.heappop(keepers)     # evict the weakest keeper

At the end, the root is the kth largest. That is problem 215, and the same three lines appear inside problem 2542. Reach for it whenever a problem says k largest, k closest, or top k.

3. Fix the awkward half of the objective

Problem 2542 is the most transferable idea in this chapter. The score multiplies a sum you choose by a minimum you also choose, and those two pull against each other — you cannot greedily optimise both.

So stop trying. Sort by the second array descending and walk it. Standing on element i, treat its value as the minimum: everything seen so far is at least as large, so it is a legal choice of minimum. Now the objective has only one free part left — maximise the sum of k values from the first array among those seen — and that is the size-k heap from section 2.

When two quantities fight, iterate over the possible values of one and let the other become an ordinary problem. That move recurs well beyond heaps.

4. Two heaps

Problem 2462 needs the cheapest from either end of a shrinking array. One heap per end, two indices marking the untouched middle, and after each hire the heap that shrank is refilled from its own side. The tie rule — lower index wins — is not special-cased; it falls out of checking the left heap first and comparing with <=.

5. The problems

6. Traps

7. Drills

Chapter 15 — Binary Search

At the end of this chapter you can spot binary search in problems that contain no sorted array and sometimes no array at all, write the loop without an off-by-one, and justify termination out loud.

Four problems: 374, 162, 875, 2300. They are ordered by what they ask of you, not by number — each one removes an assumption the previous one relied on.

lo, hi = <bottom of the space>, <top of the space>
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid            # mid might be the answer: keep it
    else:
        lo = mid + 1        # mid is definitely not: discard it
return lo

1. The idea

Most people learn binary search as "how to find a value in a sorted array". That description is too narrow to be useful, and it is the reason binary search goes unnoticed in three of this chapter's four problems.

The real requirement is a pair:

1. a search space that is ordered, and
2. a predicate over that space that is monotone — false, false, false, true, true, true, with exactly one flip.

Given those two things, testing the midpoint eliminates half the space. There need not be an array. In problem 374 the space is the numbers 1..n and the predicate is a function somebody else wrote. In problem 875 the space is the set of possible answers, and the predicate is "can Koko finish at this speed" — a loop you write yourself.

Sorting is not a precondition of binary search. Sortedness is just the most common way a problem arrives already carrying a monotone predicate.

The four shapes, in this chapter's order

2. The template, and why it is written that way

Two decisions in those six lines cause nearly all binary search bugs.

while lo < hi, not lo <= hi. The loop above searches for a boundary — the first element for which the predicate holds. It ends when the range has collapsed to one candidate, and that candidate is the answer. Use lo <= hi when you are searching for an exact value that may be absent and you need to be able to return "not found", which is what 374 does.

hi = mid on the true branch, lo = mid + 1 on the false branch. The asymmetry is not sloppiness. A mid that satisfies the predicate is still a candidate for being the first one, so it must stay in the range. A mid that fails cannot be the answer, so it is discarded. Keeping a failing candidate is the off-by-one; discarding a passing one loses the answer.

Why it terminates. mid = (lo + hi) // 2 rounds down, so while lo < hi we always have mid < hi. The hi = mid branch therefore strictly shrinks the range, and the lo = mid + 1 branch obviously does. If you ever write the mirror-image search that rounds down and assigns lo = mid, it hangs the moment hi == lo + 1. That is not a rare edge case; it is the single most common infinite loop in this pattern.

A note on the overflow folklore: in C++ or Java, (lo + hi) / 2 can overflow and the received wisdom is to write lo + (hi - lo) / 2. In Python it cannot — integers are arbitrary precision. Writing the defensive form here is cargo cult. It is worth knowing the reason it exists, and worth not pretending it applies.

3. The problems

4. Recognition

The single most useful reflex: when a problem asks for a smallest or largest value that still works, stop trying to compute it. Ask instead whether you can check a candidate. If checking is easy and feasibility is monotone, the answer is a binary search over candidates, and the check is the loop body.

5. Traps

The sixth row is the one that costs interviews rather than submissions. Binary searching a non-monotone predicate produces a confident, fast, wrong answer, and no test case in the examples will tell you. Say the monotonicity argument out loud before you write the loop.

6. Drills

Chapter 16 — Backtracking

At the end of this chapter you can write the choose / recurse / un-choose template from memory, and you know what pruning can and cannot buy you.

Two problems: 17, 216.

def search(state, chosen, results):
    if <complete>:
        results.append(list(chosen))     # a COPY
        return
    for option in <options(state)>:
        if <cannot possibly work>:
            continue                     # or break, if the options are ordered
        chosen.append(option)
        search(<advanced state>, chosen, results)
        chosen.pop()                     # un-choose

1. The template, and the two lines that matter

Backtracking is a single shape: make a choice, explore everything that follows from it, then undo the choice and try the next one. Two lines in that template cause every bug.

chosen.pop() — the un-choose. Without it the partial solution accumulates across branches and everything after the first result is wrong.

list(chosen) — the copy. chosen is one list being mutated throughout the search. If you append it to the results without copying, every entry in the answer is the same list object, and by the time the search ends they are all empty.

Between them these two lines account for more failed backtracking attempts than the actual algorithm does.

2. What pruning buys, and what it does not

Problem 17 is here to make an uncomfortable point early: there is no clever algorithm. The answer contains 3ⁿ strings, so producing it costs at least 3ⁿ. The chart under that problem shows the naive iterative version and the backtracking version on the same curve, because they are the same order and always will be.

Problem 216 then shows what you can do:

for value in range(start, 10):
    if value > remaining:
        break              # everything after this is larger too

That is pruning. It cuts branches that provably cannot lead to a solution, and it can make an intractable search finish instantly — but it does not change the exponent. Backtracking is exponential; pruning changes the constant and the practical running time, not the class. Saying that clearly in an interview is worth more than an optimisation.

Problem 216's other line is quieter and just as important. Passing value + 1 as the next starting point is what makes the results combinations rather than permutations: a choice is never revisited, so {1,2,4} is produced once and {2,1,4} never. Whether you pass value, value + 1, or the full range decides which of the three standard problems — combinations with repetition, combinations, or permutations — you are actually solving.

3. The problems

4. Recognition

That last row is the practical tell. When the constraints are unusually small, the setter is telling you an exponential search is the intended answer.

5. Traps

6. Drills

Chapter 17 — Dynamic Programming, One Dimension

At the end of this chapter you can state a DP in two sentences before writing any code, and you know why the naive recursion is not merely slow but exponentially slow.

Four problems: 1137, 746, 198, 790.

1. Two sentences, then the code

Every DP in this chapter is fully specified by two sentences. Write them down in English first; the code is a transcription.

1. What does state i mean? Not "the array" — the meaning. "The cheapest way to reach step i." "The most that can be robbed from the first i houses."
2. How does state i follow from earlier states?

Get the first sentence wrong and nothing afterwards can be right. Problem 746 is the classic example: reaching step i and leaving step i differ by whether its own cost has been paid, and choosing the wrong one produces an off-by-one that no amount of index fiddling fixes.

2. Why the naive recursion explodes

The recursions in this chapter are correct. They are also exponential, because they recompute the same subproblem astronomically often. The measurements under each problem show the exact rate, and the numbers are more interesting than "exponential":

Those bases are not folklore; each is the largest root of the recurrence's characteristic equation, and each was measured by counting operations in the real code. It is worth knowing that "exponential" has a rate, and that the rate is set by the shape of the recursion.

3. Almost none of them need an array

Once the recurrence only looks back a fixed distance, the table collapses to that many variables:

skipped, taken = 0, 0
for value in nums:
    skipped, taken = max(skipped, taken), skipped + value

Two variables for House Robber, three for Tribonacci, one array only for problem 790 because its recurrence reaches three steps back and the code reads better with it. State the recurrence first, then ask how far back it looks — that question, not cleverness, is what gives you the O(1) space version.

4. Take-or-skip

Problems 198 and 746 share a shape worth naming, because it generalises far beyond them:

At each position there are two possibilities. Track the best total for each, not one best overall.

Robbing here requires having skipped the previous house; skipping here may use whichever of the two was better. Two running values, one line each. Any problem with a constraint between neighbours — no two adjacent, no two in a row, alternating — has this shape.

5. The problems

6. Recognition

7. Traps

8. Drills

Chapter 18 — Dynamic Programming, Two Dimensions

At the end of this chapter you can spot when a problem needs two indices rather than one, fill a table in the right order, and shrink it to a single row.

Four problems: 62, 1143, 714, 72.

1. What the second dimension is

Two dimensions does not always mean two indices. There are two distinct cases here, and telling them apart is most of the chapter:

Two inputs. Problems 1143 and 72 compare two strings, so the state is a position in each: table[i][j] means "the answer for the first i characters of one and the first j of the other". Problem 62 is the same thing geometrically — a position in a grid is two numbers.

A mode. Problem 714 has one input and one extra bit of state: are you holding a share or not? The second dimension has size two. Do not build a table for it; two variables will do.

The tell: ask what you would need to write on a note to resume the computation from the middle. If it takes two numbers, you have two dimensions. If it takes one number and a yes/no, you have a mode.

2. One question per cell

Each of these recurrences comes from a single question asked at every cell.

Problem 72 is worth reading as geometry: replace steps diagonally, delete steps up, insert steps left, each costing one, and a match steps diagonally for free. Once you see the three operations as three directions in the table, the recurrence stops needing to be memorised.

3. The base row is not zeros

The most common bug in this chapter. In problem 72, table[i][0] is the cost of turning a prefix of length i into an empty string — that is i deletions, not zero. In problem 62 the first row and column are 1, not 0: there is exactly one way to walk along an edge.

Derive the base cases from the state's definition, do not guess them. If the definition is "the answer for the first i and first j characters", then setting j = 0 asks a question you can answer directly, and the answer is usually not zero.

4. Collapsing the table

Every recurrence here reads only from the previous row and the current one, so the full m × n table is never needed:

previous = [0] * (len(text2) + 1)
for i in range(1, len(text1) + 1):
    current = [0] * (len(text2) + 1)
    ...
    previous = current

Two rows instead of a table. In problem 62 even that is unnecessary — a single row updated left to right works, because by the time you read row[c - 1] it already holds the current row's value while row[c] still holds the previous row's. That works only in that direction; reversing the loop silently breaks it.

5. The problems

6. Traps

7. Drills

Chapter 19 — Bit Manipulation

At the end of this chapter you know the four operations worth memorising, and you can recognise the constraint that is really a hint.

Three problems: 338, 136, 1318.

x & 1          # the lowest bit
x >> 1         # drop the lowest bit
x & (x - 1)    # clear the lowest set bit
a ^ b          # differing bits; a ^ a == 0, a ^ 0 == a

1. The constraint is the hint

All three problems in this chapter can be solved with a hash map or a loop, and all three have a constraint that rules it out:

"...with constant extra space." — problem 136 "...in linear time." — problem 338

When a problem is easy but the constraints forbid the easy solution, the setter is telling you which tool they want. In this chapter that tool is arithmetic on bits.

2. XOR, and why it fits

XOR has exactly three properties, and problem 136 needs all three:

• a ^ a == 0 — a value cancels itself
• a ^ 0 == a — nothing else is disturbed
• it is commutative and associative — the order of the array does not matter

Fold the array with XOR and every pair annihilates, leaving the loner. One accumulator, no memory, one pass. This is the archetype for "everything is paired except one", and variants of it — find two loners, find the missing number — are all built on the same three properties.

3. Bits do not interact

Problem 1318 looks fiddly and is not, once you notice that a flip at one bit position never affects another. OR is computed independently per position, so the problem decomposes into 32 tiny independent problems and the answer is their sum:

• c has a 1 here: you need at least one 1. Cost 0 if either a or b has one, else 1.
• c has a 0 here: every 1 present must go. Cost one per 1.

Decomposition into independent positions is the move, and it is worth looking for whenever a bitwise condition has to hold.

4. Bits as a recurrence

Problem 338 is dynamic programming wearing a bit-manipulation costume. i >> 1 removes the lowest bit of i and is always a smaller number, so its answer is already known:

bits[i] = bits[i >> 1] + (i & 1)

That is chapter 17's structure — a recurrence to a strictly smaller subproblem — with a shift where an arithmetic subtraction usually goes. Noticing that a shift is a valid way to get to a smaller subproblem is the transferable part.

5. The problems

6. Traps

7. Drills

Chapter 20 — Trie

At the end of this chapter you can build a prefix tree from nothing, and you know when a sorted array does the same job with less code.

Two problems: 208, 1268.

1. The idea

A trie is a tree whose edges are characters. A path from the root spells a prefix, and words beginning alike share their nodes — so a lookup costs the length of the word, not the size of the dictionary.

class Trie:
    def __init__(self):
        self.children = {}      # character -> Trie
        self.is_word = False    # does a word END here?

Two fields, and the second one is the whole design. Without is_word there is no way to distinguish a stored word from a mere prefix of one, and search("app") would return the same as startsWith("app"). Building the structure is easy; remembering that flag is what separates a working trie from a broken one.

2. When you need one, and when you do not

A trie earns its place when:

• prefixes are queried, not just whole words;
• the dictionary is large and queries are many;
• words share their beginnings, so the sharing actually saves something.

It does not earn its place when a set would do. If the only question is "is this exact word present", use a set — it is one line, constant time, and no one has to review your node class.

Problem 1268 is here as the honest counterweight. It is the canonical trie problem, and the solution in this chapter does not build one:

Sorting puts every group of words sharing a prefix into one contiguous block — the same fact a trie encodes as shared paths. Because the typed prefix only ever grows, the block only ever shrinks, so two pointers walking inwards answer every keystroke in one pass.

Fewer lines, no custom class, and the same complexity. Knowing the trie and choosing the sorted array anyway is a better answer in an interview than reaching for the heavy structure by reflex — provided you can say why.

3. What tries are actually for

Beyond these two problems, the shape recurs whenever a path through a tree encodes a sequence: autocomplete, IP routing tables, word-search boards where a trie prunes the backtracking, and finding the longest common prefix of a set of strings. The common thread is that the query is about a prefix rather than a whole value — which is precisely what hashing destroys.

4. The problems

5. Traps

6. Drills

Chapter 21 — Intervals

At the end of this chapter you know the one decision every interval problem turns on, and you can justify a greedy choice rather than hoping.

Two problems: 435, 452.

for pair in sorted(intervals, key=lambda p: p[1]):   # sort by END
    if pair[0] >= edge:                              # compatible with the last kept
        keep(pair)
        edge = pair[1]

1. Sort by start, or by end?

That is the whole chapter, and the answer depends on the question:

Both problems here are the second kind, so both sort by end.

2. Why sorting by end is correct

This is the argument to be able to say out loud, because the greedy choice is not obviously safe and the wrong sort produces a plausible wrong answer.

Claim: among all intervals, the one that finishes earliest is always safe to keep.

Why: it leaves at least as much room as any alternative. Take any optimal solution; if it does not contain the earliest-finishing interval, swap that interval in for whichever it does contain first. Nothing later is disturbed — the replacement ends no later — so the swapped solution is still valid and no smaller. Therefore an optimal solution containing the greedy choice exists.

Sorting by start instead fails on a single case: one very long interval that starts first gets taken and blocks everything after it. If you cannot remember which sort to use, remember that counterexample and re-derive.

3. Two questions, one algorithm

Problem 435 removes the fewest intervals; problem 452 fires the fewest arrows. These sound opposite and are the same loop, because removing the fewest means keeping the most, and covering with the fewest points means counting the groups that a keeper defines.

The only difference is a single comparison operator:

if pair[0] >= edge:     # 435: touching endpoints do NOT overlap
if pair[0] > reach:     # 452: touching endpoints ARE hit by the arrow

Read the statement for what happens at a shared endpoint. It is one character in the code and it is the difference between accepted and wrong answer.

4. The problems

5. Traps

6. Drills

Chapter 22 — Monotonic Stack

At the end of this chapter you can recognise the next greater element shape under several disguises, and explain why two nested loops are linear.

Two problems: 739, 901.

stack = []                       # indices, kept in decreasing order of value
for i in range(len(values)):
    while stack and values[stack[-1]] < values[i]:
        resolved = stack.pop()
        answer[resolved] = i - resolved
    stack.append(i)

1. The shape

A monotonic stack answers one question: for each element, where is the next element bigger (or smaller) than it?

The disguises it wears:

The stack holds items still waiting for their answer. It stays sorted automatically: anything that would break the order has already been popped, because the element that broke it was the answer.

2. Why the nested loops are linear

This is the interview question, and it is the same argument as the sliding window in chapter 03: each index is pushed exactly once and popped at most once. The inner while may run many times on one iteration and zero times on the next, but its total work across the whole loop is bounded by n.

Nesting is a property of the source. Complexity is a property of the execution. The charts under both problems are that distinction, measured: the naive version bends upward, the stack version does not.

3. Collapsing what you no longer need

Problem 901 adds the idea worth taking away from this chapter. When a price swallows the days beneath it, their individual spans are never needed again — only their total. So each stack entry carries a value and the span it has absorbed:

while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]
self.stack.append((price, span))

The stack therefore stays short even when the input is long, and the amortised argument still holds because each entry is created once and destroyed once. Storing an aggregate on the stack entry, rather than the items it came from, is the general move — it is what makes the histogram and rectangle problems tractable too.

4. The problems

5. Traps

6. Drills

Appendix A — The 22 Templates

One page. If you can write these from memory, you can write any of the 75.

Linear scans

Sliding window, fixed — a size is named

window = sum(a[:k]); best = window
for right in range(k, len(a)):
    window += a[right] - a[right - k]
    best = max(best, window)

Sliding window, variable — a condition is named

left = 0
for right in range(len(a)):
    add(a[right])
    while not legal():
        remove(a[left]); left += 1
    best = max(best, right - left + 1)

Two pointers, converging — each step must provably lose nothing

left, right = 0, len(a) - 1
while left < right:
    if <the left one is finished>: left += 1
    else:                          right -= 1

Two pointers, same direction — partition or match in place

write = 0
for read in range(len(a)):
    if keep(a[read]):
        a[write], a[read] = a[read], a[write]; write += 1

Prefix sum — a range sum is a subtraction

running = 0
for i in range(len(a)):
    running += a[i]              # == sum(a[0..i])
    # sum(a[i..j]) == prefix[j] - prefix[i-1]

Hash map / set — in on a set is not in on a list

counts = {}
for value in a:
    counts[value] = counts.get(value, 0) + 1

Stack — the most recent one

stack = []
for item in items:
    if cancels(item): stack.pop()
    else:             stack.append(item)

Queue — the oldest one

from collections import deque
q = deque(); q.append(x); q.popleft()      # never list.pop(0)

Pointers and trees

Linked list, rewire — save before you overwrite

previous, current = None, head
while current:
    following = current.next
    current.next = previous
    previous, current = current, following

Linked list, find the middle

slow = fast = head
while fast and fast.next:
    slow, fast = slow.next, fast.next.next

Tree DFS, answer flows up

def solve(node):
    if node is None: return <answer for nothing>
    return combine(solve(node.left), solve(node.right), node.val)

Tree DFS, information flows down

def walk(node, carried):
    if node is None: return 0
    carried = update(carried, node)
    return here(node, carried) + walk(node.left, carried) + walk(node.right, carried)

Tree BFS, level by level

q = deque([root])
while q:
    width = len(q)                # this many nodes are one level
    for _ in range(width):
        node = q.popleft()
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

Binary search tree — descend, do not traverse

while node:
    if node.val == target: return node
    node = node.left if target < node.val else node.right

Search and selection

Graph DFS — mark on push

visited, stack = {start}, [start]
while stack:
    node = stack.pop()
    for nxt in neighbours[node]:
        if nxt not in visited:
            visited.add(nxt); stack.append(nxt)

Graph BFS — the only one that gives distances

q = deque([(start, 0)]); seen = {start}
while q:
    node, dist = q.popleft()
    for nxt in neighbours[node]:
        if nxt not in seen:
            seen.add(nxt); q.append((nxt, dist + 1))

Heap, the k largest — a min-heap of size k

import heapq
heapq.heappush(keepers, value)
if len(keepers) > k: heapq.heappop(keepers)    # evict the weakest keeper

Binary search on a boundary

lo, hi = <bottom>, <top>
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid          # mid might be the answer
    else:             lo = mid + 1      # mid definitely is not
return lo

Backtracking — choose, recurse, un-choose

def search(state, chosen, out):
    if complete(state): out.append(list(chosen)); return    # a COPY
    for option in options(state):
        if hopeless(option): continue
        chosen.append(option)
        search(advance(state, option), chosen, out)
        chosen.pop()                                        # un-choose

Tables and structures

DP, one dimension — state, then recurrence

back_two, back_one = base0, base1
for value in values:
    back_two, back_one = back_one, combine(back_one, back_two, value)

DP, two dimensions — two rows, not a table

previous = [base] * (len(b) + 1)
for i in range(1, len(a) + 1):
    current = [edge(i)] + [0] * len(b)
    for j in range(1, len(b) + 1):
        current[j] = <from previous[j-1], previous[j], current[j-1]>
    previous = current

Bit manipulation

x & 1          # lowest bit          x >> 1         # drop it
x & (x - 1)    # clear lowest set    a ^ a == 0     # cancel pairs

Trie

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False     # without this, search == startsWith

Intervals — sort by end to keep the most

for pair in sorted(intervals, key=lambda p: p[1]):
    if pair[0] >= edge:
        keep(pair); edge = pair[1]

Monotonic stack — next greater element

stack = []
for i in range(len(a)):
    while stack and a[stack[-1]] < a[i]:
        resolved = stack.pop(); answer[resolved] = i - resolved
    stack.append(i)

Appendix B — Measured Complexities

Every figure in the naive and solution columns was produced by tools/measure.py counting operations inside the code printed in this book, then fitting a growth model. Nothing here was asserted by hand. Where an exponential base is given to one decimal place, that is the fitted base of the naive recursion — not a rounded 2 or 3.

75 problems, 74 measured, 1 capped by their own constraints.

\* capped by the problem's own constraints; stated, not measured.

Appendix C — Failure Catalogue

Forty bugs, indexed by what you see, not by what is wrong. Nobody debugs by knowing the cause first — you have a wrong number and a passing example, and you work backwards. Most of these were made while writing this book.

It times out

It never finishes

It crashes

It is off by one

It is right for the examples and wrong otherwise

The output is the wrong shape

Appendix D — Recognition Table

The whole book on one page, read the way an interview actually presents it: you have a statement and no title. Find the phrase, get the pattern. Every tell below is taken from the problem it belongs to.

The five that decide most problems

1. “contiguous”, “subarray”, “substring” — a window, not a subsequence.
2. “smallest / largest value that still works” — binary search the answer.
3. “the closest one to the left”, “nested” — a stack.
4. “fewest steps”, “shortest” — breadth first, never depth first.
5. “return all of them” — backtracking; “how many” — usually DP instead.

Appendix E — Python for Interviews

The parts of the language that decide whether a correct algorithm passes.

What is actually O(1)

The three rows in bold cause almost every "correct but too slow". They are also the three the measurement tools in this book charge for explicitly, which is how the charts under Chapter 01 show a linear-looking loop bending upwards.

The containers worth knowing

from collections import deque, defaultdict, Counter
import heapq
from bisect import bisect_left, bisect_right

deque()                  # append / appendleft / pop / popleft, all O(1)
defaultdict(list)        # d[k].append(x) with no KeyError
Counter(iterable)        # frequencies in one line; .most_common(k)
heapq.heappush(h, x)     # MIN-heap only; negate for a max-heap
bisect_left(a, x)        # leftmost insertion point in a sorted list

Counter and defaultdict are worth using in an interview and worth being able to write out by hand if asked — knowing that Counter is a dict of counts is the point, not the import.

Things that surprise people

Integers do not overflow. (lo + hi) // 2 is safe in Python. The lo + (hi - lo) // 2 form exists for C++ and Java, and writing it here is cargo cult — know why it exists, and know that it does not apply.

Negative right shift never terminates. Python integers have unbounded sign extension, so while x: x >>= 1 loops forever on a negative value. Mask with & 0xFFFFFFFF when a 32-bit answer is wanted.

& and | bind looser than ==. x & 1 == 1 parses as x & (1 == 1). Parenthesise.

Default arguments are evaluated once. def f(acc=[]) shares one list across every call, which in a backtracking function produces answers contaminated by the previous test case.

Tuples compare element by element. (3, "a") < (3, "b") is True — useful for heap entries with tie-breaking, and a TypeError waiting to happen if the second element is not comparable.

Slicing never raises. a[5:9] on a three-element list gives [], not an error. Handy, and a good way to hide a bug.

Recursion

The default limit is 1000 frames. A linked list or graph with 10⁵ nodes in a chain will hit it. Either write the iterative form with an explicit stack, or:

import sys
sys.setrecursionlimit(10000)

Say out loud in an interview which one you are doing and why. The iterative form is the better answer when the recursion carries no work on the way back up.

Writing it so a reviewer can read it

• Name the invariant in a comment above the loop, not the mechanics inside it.
• for i in range(len(a)) when you need the index; for x in a when you do not.
• Unpack: for start, end in intervals beats interval[0] and interval[1].
• A helper function with a real name beats a nested comprehension that needs decoding.
• If you write # tricky you have found the line that needs rewriting, not commenting.

Appendix F — How to Practise

Solving 75 problems teaches you 75 problems. This appendix is about the part that transfers.

The one thing that actually transfers

Pattern recognition. Given a cold statement and no title, which of the 22 does it want? That is the skill an interview tests, and grinding solutions does not build it — the problem comes to you pre-labelled by the chapter you are in, which is exactly the information you will not have when it matters.

This is why the drills at the end of each chapter strip the title away and show only the statement. Do those more often than you re-solve problems. They cost a minute each.

The protocol for a problem you have not seen

1. Restate it in one sentence, out loud. If you cannot, you have not read it.
2. Say the brute force and its complexity. Always. It is a correct answer, it buys thinking time, and interviewers score it.
3. Read the constraints. n ≤ 20 means exponential is expected. n ≤ 10⁵ means linear or n log n. n ≤ 10⁹ means you cannot touch the input at all.
4. Name the pattern and the tell that gave it away.
5. State the invariant — what is true at the top of every iteration — before writing code.
6. Then write it. Code last, not first.
7. Walk one small input by hand, including an edge case: empty, one element, all equal.

Steps 1 to 5 are where the score is. Candidates who start typing at step 1 and arrive at the right answer routinely do worse than candidates who talk through five and run out of time.

The review schedule

The book tracks this for you, but the reasoning is worth knowing. After each problem or drill, rate yourself honestly:

Rate honestly or the schedule is worthless. Marking Good when you needed two hints produces a queue that flatters you and a gap that shows up in the interview instead.

Twenty minutes of due reviews beats two hours of new problems. The whole point of spacing is that it costs less and holds longer.

When you are stuck

In this order, and give each one a real attempt before moving on:

1. Work a small example by hand — three elements, on paper. Most patterns become visible.
2. Solve the brute force properly. The optimisation is often visible in what it repeats.
3. Ask what is being recomputed. That question alone produces sliding windows, prefix sums, DP and memoisation.
4. Ask what you could discard. That produces two pointers, binary search and greedy.
5. Take one hint. One, then close the panel and try again.
6. After 45 minutes, read the solution — then close it, wait a day, and write it yourself from nothing. A problem you read is not a problem you can do.

What not to do

• Do not re-solve problems you already know. It feels productive and teaches nothing.
• Do not read solutions to problems you have not attempted. You learn that the solution is reasonable, which is not the same as being able to find it.
• Do not chase problem count. Forty problems understood beats four hundred attempted.
• Do not skip the brute force because you already know the trick. Saying it out loud is the habit you are building.
• Do not practise silently. If the interview is verbal, the practice should be too.

A schedule that works

Six weeks of that covers the list twice and leaves the patterns rather than the answers.

Appendix G — What This List Omits

The LeetCode 75 is a good list. It is not a complete one, and knowing what is missing is part of knowing what you have.

Patterns not covered, in rough order of how often they come up

Union-Find (disjoint set union). Chapter 12 counts connected components with a search, which is fine when the graph is fixed. Union-Find handles components that merge over time — edges arriving one at a time, "are these two connected yet", Kruskal's algorithm. It is about fifteen lines with path compression, and it turns several hard problems into easy ones.

Topological sort. Ordering tasks with dependencies: course schedules, build systems, cycle detection in a directed graph. It is BFS with an in-degree count (Kahn's algorithm) or DFS with a finish-order stack. Common enough in interviews that its absence here is the most surprising gap.

Dijkstra and weighted shortest paths. Chapter 13's BFS gives shortest paths only when every edge costs the same. Once edges have weights you need a heap instead of a queue — which is chapter 13 and chapter 14 combined, and a natural next step from both.

Matrix and grid DP. Chapter 18 does two-string DP; grid problems with obstacles, minimum path sums and maximal squares are the same machinery on two-dimensional input.

Knapsack. The other major DP family: subset sum, partition into equal halves, coin change. The state is (index, capacity remaining), and the space-collapsing trick has a direction that matters — iterating capacity backwards is what makes 0/1 knapsack differ from unbounded.

Sliding window maximum, and monotonic deques. Chapter 03 explains why a plain window cannot carry a maximum. The fix is a monotonic deque — chapter 22's stack, open at both ends.

Segment trees and Fenwick trees. Range queries with updates in between. Rarely asked in interviews, standard in competitive programming.

Strings beyond scanning. KMP, Rabin-Karp, Z-algorithm, palindromic substrings. The 75 touches strings only as arrays of characters.

Intervals, the rest of them. Chapter 21 does two greedy problems. Merging, insertion, and meeting-rooms-style resource counting (a heap of end times) are the other three shapes.

The other lists

• Blind 75 — the older list this one descends from. Considerable overlap, a harder tail, and it includes topological sort and Union-Find.
• NeetCode 150 — the 75 plus the gaps above, roughly this book's list with the omissions filled in.
• Grind 75 — the same problems arranged by a weekly time budget rather than by topic.

If you have finished this book, the highest-value next step is Union-Find and topological sort. They are two patterns, they cover a large family of problems, and neither takes an evening.

Beyond the interview

The habit worth keeping from this book is not the patterns. It is the thing the charts under every problem are doing: not believing a complexity claim until it has been measured.

That transfers to work in a way the patterns do not. The instinct to ask "how do you know?" of a performance claim — your own most of all — is worth more over a career than the ability to recall the monotonic stack template. The template is on one page of Appendix A. The habit takes longer and pays for much more.