The Problem-Solving Playbook: How to Choose the Technique

This is the last lesson of the path. It teaches no new data structure. It teaches how to choose among the ones you have, and it asks you to prove each choice with a number.

#Why You Need a Playbook

Most people fail a new problem in one of two ways. They freeze because every technique feels possible, or they grab the first familiar one and code for an hour before it fails. A playbook is a short fixed routine that stops both.

#Step One: Read the Constraints

Before you think about techniques, read the limits. They tell you how much work the answer may do. A program can afford only so many simple steps before it is too slow, and the limits on n tell you which growth rates fit.

As a rule of thumb, plain Python can do on the order of ten million simple steps in a second or so. That number is not a measurement and it changes with the machine and with what each step does. Use it only to sort ideas into "fits" and "too slow". The cell below finds the largest n each growth class can afford under that budget.

import math

BUDGET = 10_000_000          # a rule of thumb for simple steps, not a measurement

COST = {
    "O(log n)": lambda n: math.log2(n),
    "O(n)": lambda n: n,
    "O(n log n)": lambda n: n * math.log2(n),
    "O(n²)": lambda n: n * n,
    "O(n³)": lambda n: n ** 3,
    "O(2^n)": lambda n: 2 ** n,
    "O(n!)": lambda n: math.factorial(n),
}


def largest_n(cost):
    """Largest n whose step count stays within the budget (doubling, then halving search)."""
    lo, hi = 2, 2
    while cost(hi) <= BUDGET and hi < 10 ** 12:
        lo, hi = hi, hi * 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if cost(mid) <= BUDGET:
            lo = mid
        else:
            hi = mid
    return lo


for name, cost in COST.items():
    n = largest_n(cost)
    print(f"{name:11} fits up to n = {n:,}" if n < 10 ** 12 else f"{name:11} fits for any n you will meet")
# Output:
# O(log n)    fits for any n you will meet
# O(n)        fits up to n = 10,000,000
# O(n log n)  fits up to n = 526,172
# O(n²)       fits up to n = 3,162
# O(n³)       fits up to n = 215
# O(2^n)      fits up to n = 23
# O(n!)       fits up to n = 10

Read the table as a code for the limit in the statement. If n is at most about 10, try every order of the items (n!). If n is at most about 20, try every subset (2^n), or use a bitmask.

If n is a few hundred, cubic loops fit. If n is a few thousand, quadratic loops fit. If n is around 100,000, you need O(n log n) or better. If n reaches millions, you need one pass.

Two other kinds of limit matter. If values can be as large as 10^9, you cannot build a table with one cell per value. If the answer itself lists many items (all subsets, say), no method can beat the size of that list.

The estimate has assumptions, and you should say them aloud. It assumes each step is simple: a step that copies a list of n values is n steps, not one. It assumes the worst-case input and the average-case hash table. It also ignores constant factors, so a 3n method and a 30n method share one class.

#The Six-Step Method

Use these six steps in order, every time. They work on a whiteboard, in an interview and at your desk.

Step 1 is to restate the problem in your own words. Name the input, the output and the edge cases: empty input, one value, duplicates, negative numbers, ties, and "no answer exists". Ask what to return when there is no answer.

Step 2 is to work two or three examples by hand: a normal one, a tiny one and a tricky one. Your hand method is the first draft of the algorithm. Step 3 is to write the brute force. It is simple, it is correct, and it becomes your test oracle later, the slow trusted answer that you compare the fast one against.

Step 4 is to find the bottleneck. Look at the brute force and ask which question it asks over and over. "Is this value in the list?" asked n times is a repeated search. "What is the smallest value now?" asked n times is a repeated minimum. "What is the sum of this slice?" is a repeated range sum.

Step 5 is to improve by matching the repeated question to a tool. Repeated membership points to a hash set. A repeated minimum points to a heap. A repeated range sum points to prefix sums. A repeated yes-or-no that flips once points to binary search. Step 6 is to test edge cases and compare against the brute force on many small inputs.

#A Worked Example: From Brute Force to One Pass

Problem: given non-negative numbers and a limit, find the length of the longest run of neighbors whose sum is at most the limit. Examples: for [3, 1, 2, 7, 4, 2, 1, 1, 5] with limit 8, the run 4, 2, 1, 1 sums to 8, so the answer is 4. For an empty list the answer is 0. If every number is above the limit the answer is also 0.

def longest_brute(nums, limit):
    """Longest run with sum at most limit. Try every start and extend. O(n²) time, O(1) space."""
    best, ops = 0, 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            ops += 1
            total += nums[j]
            if total > limit:
                break
            best = max(best, j - i + 1)
    return best, ops


def longest_window(nums, limit):
    """Same answer, values must be >= 0. Each index enters and leaves once: O(n) time, O(1) space."""
    best, ops, left, total = 0, 0, 0, 0
    for right, x in enumerate(nums):
        ops += 1
        total += x
        while total > limit:
            total -= nums[left]
            left += 1
            ops += 1
        best = max(best, right - left + 1)
    return best, ops


small = [3, 1, 2, 7, 4, 2, 1, 1, 5]
print(longest_brute(small, 8), longest_window(small, 8))
flat = [1] * 2000
print(longest_brute(flat, 10 ** 9), longest_window(flat, 10 ** 9))
print(longest_brute([], 5), longest_window([], 5))
print(longest_brute([9, 9], 5), longest_window([9, 9], 5))
# Output:
# (4, 26) (4, 15)
# (2000, 2001000) (2000, 2000)
# (0, 0) (0, 0)
# (0, 2) (0, 4)

Each pair is (answer, ops). Both methods agree on every answer. The two ops counts differ, and the second line shows how far.

The cost follows from the same fact. Each index enters the window once and leaves at most once, so the loop does at most 2n steps: O(n) time and O(1) extra space. The brute force does n(n+1)/2 steps when nothing breaks early, which is O(n²), and the 2,001,000 against 2,000 above shows exactly that gap. The method needs the numbers to be non-negative. Remember that, because a later section breaks it on purpose.

#The Decision Flow

A technique is chosen by questions asked in a fixed order, cheapest to check first. Several answers can fit one problem. "Two numbers that add to a target" fits a hash set and also two pointers on sorted data. Pick the one whose conditions your input meets.

1. Is the input sorted, or does a yes/no answer flip exactly once?
      yes -> binary search (on the index or on the answer)
2. Does it ask about pairs, or a contiguous slice?
      pair, repeated lookup      -> hash set or dict
      pair in sorted data        -> two pointers
      slice with non-negative    -> sliding window
      slice, any sign, a sum     -> prefix sums + dict
3. Does it repeat "give me the smallest/largest"?   -> heap
4. Is it a graph (things joined by links)?
      fewest edges               -> BFS
      cheapest, no negatives     -> Dijkstra
      negative edges             -> Bellman-Ford
      ordering with rules        -> topological sort
      are these connected        -> union-find
5. Do choices make smaller copies of the same problem?
      choices overlap            -> dynamic programming
      a local best is provably safe -> greedy
      halves combine             -> divide and conquer
6. Must it list or count every valid configuration?  -> backtracking
7. Is n tiny, or are the items bits and subsets?     -> brute force or bitmask

Question 5 is where most mistakes happen. Two ideas look alike: DP and greedy. Both start from "the best answer is built from smaller best answers". The difference is whether you can trust the first good-looking choice. Greedy trusts it, and DP tries all of them and remembers the results.

def greedy_coins(amount, coins):
    """Always take the biggest coin that fits. Fast, but only correct for some coin sets."""
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1


def dp_coins(amount, coins):
    """best[a] = fewest coins for amount a. O(amount * len(coins)) time, O(amount) space."""
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1


print(greedy_coins(6, [1, 3, 4]), dp_coins(6, [1, 3, 4]))
print(greedy_coins(63, [1, 5, 10, 21, 25]), dp_coins(63, [1, 5, 10, 21, 25]))
print(greedy_coins(41, [1, 5, 10, 25]), dp_coins(41, [1, 5, 10, 25]))
# Output:
# 3 2
# 6 3
# 4 4

The last line shows why greedy tempts people. For the familiar coins 1, 5, 10 and 25 it is right. So the rule is: never trust greedy because it worked on the examples. Either prove it with an exchange argument (the Greedy Algorithms lesson), or hunt for a counterexample on tiny inputs, as above.

#The Pattern Table

Here is every technique from Part 10, with the signal that points to it, its usual cost, and the lesson that teaches it. Costs assume the conditions that lesson states.

#The Invariant Behind Each Pattern

A technique is only as good as its condition. Each row below names the fact that makes the loop correct, and the input that breaks it. Say this sentence out loud before you code, and the most common wrong answers disappear.

#Two More Solved Examples

First problem: count the runs of neighbors, where negative numbers are allowed, whose sum is exactly k. A sliding window is out, because negatives break its invariant. The signal "a slice sum, any sign" says prefix sums plus a dict.

def count_sum_k(nums, k):
    """Runs whose sum is exactly k. Negatives allowed. Prefix sums plus a dict: O(n) expected time, O(n) space."""
    seen = {0: 1}               # prefix total -> how many times it has appeared
    total, count = 0, 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count


def count_sum_k_brute(nums, k):
    """The oracle: check every run. O(n²) time, O(1) space."""
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            count += total == k
    return count


data = [3, 4, -7, 1, 3, 3, 1, -4]
print(count_sum_k(data, 7), count_sum_k_brute(data, 7))
print(count_sum_k([0, 0, 0], 0), count_sum_k_brute([0, 0, 0], 0))
# Output:
# 4 4
# 6 6

Second problem: after each number arrives in a stream, report the 3rd largest so far. The signal "repeated largest, with a small k" says heap. Keep a min-heap holding only the k largest numbers seen. Its smallest member is exactly the k-th largest. A new number only matters if it beats that smallest member.

import heapq


def kth_largest(stream, k):
    """k-th largest so far after each value. A min-heap of size k: O(n log k) time, O(k) space."""
    heap, answers = [], []
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
        answers.append(heap[0] if len(heap) == k else None)
    return answers


print(kth_largest([5, 2, 9, 1, 7, 8], 3))
# Output:
# [None, None, 2, 2, 5, 7]

Each of the n values does at most one heap operation on a heap of size k, which costs O(log k). Sorting after every arrival would cost O(n² log n) in total, so the heap wins whenever k is much smaller than n.

#Lower Bounds as a Compass

A comparison-based search in sorted data needs about log n steps. A comparison-based sort needs about n log n comparisons, a bound the Sorting and Asymptotics lessons explain.

These bounds work like a compass. If your brute force is O(n²) and the lower bound is n log n, there is room to improve. If your method already matches the bound, extra cleverness cannot help, and you should spend the time on correctness instead. The bounds hold for the comparison model. Counting sort beats n log n by not comparing at all, and it pays with a table sized by the value range.

#Debugging With a Tiny Counter and a Stress Test

for n in (500, 1000, 2000, 4000):
    nums = [1] * n
    print(n, longest_brute(nums, 10 ** 9)[1], longest_window(nums, 10 ** 9)[1])
# Output:
# 500 125250 500
# 1000 500500 1000
# 2000 2001000 2000
# 4000 8002000 4000

Each doubling multiplies the brute-force counter by about 4 and the window counter by exactly 2. That is O(n²) against O(n), seen with no stopwatch. Next, a stress test. Suppose a friend applies our window code to lists that may hold negative numbers, which the invariant forbids.

import random


def window_naive(nums, limit):
    """The window idea applied to ANY numbers. It assumes shrinking always lowers the sum."""
    best, left, total = 0, 0, 0
    for right, x in enumerate(nums):
        total += x
        while total > limit and left <= right:
            total -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best


def brute_any(nums, limit):
    """Slow but safe: check every slice, no early break. O(n²) time."""
    best = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total <= limit:
                best = max(best, j - i + 1)
    return best


rng = random.Random(7)
failures = []
for _ in range(2000):
    nums = [rng.randint(-3, 5) for _ in range(rng.randint(1, 6))]
    limit = rng.randint(0, 6)
    if window_naive(nums, limit) != brute_any(nums, limit):
        failures.append((len(nums), nums, limit))
failures.sort()
size, nums, limit = failures[0]
print("failing cases:", len(failures))
print("smallest:", nums, "limit", limit)
print("window says", window_naive(nums, limit), "brute says", brute_any(nums, limit))
# Output:
# failing cases: 240
# smallest: [1, -2] limit 0
# window says 1 brute says 2

The seed (7) makes the run repeatable. 240 of 2,000 random cases fail, and sorting by size gives the shortest counterexample, which is small enough to trace by hand. A stress test is cheap to write, so write it whenever you have a brute force. Keep the inputs small, so that a failing case is easy to read.

#Common Traps

• Reading the limits too late. A clever O(n²) solution to an n = 100,000 problem is wrong before it is written.
• Trusting greedy because three examples passed, instead of searching for a counterexample.
• Using a sliding window or two pointers on data that is unsorted or has negatives, where the invariant does not hold.
• Running Dijkstra with a negative edge, or forgetting that an undirected negative edge is already a negative cycle.
• Off-by-one errors in binary search. Decide what lo and hi mean (inclusive or not) and keep the loop consistent.
• Forgetting a disconnected graph. A traversal from one vertex sees only its own component.
• Hidden linear work inside a loop: x in some_list, list.pop(0), list.insert(0, x), slicing, or joining strings with +=. Each costs O(n) per call.
• Forgetting the undo step in backtracking, so choices leak into the next branch.
• Comparing floats with ==, and forgetting that Python recursion stops near 1,000 levels by default.
• Skipping the empty input, one value and all-equal values. Most hidden test cases are exactly these.

#How This Shows Up in Real Systems

The same questions, asked about constraints and cost, run inside systems you use. For example, a database chooses between reading a whole table and using an index (a B-tree in many databases) partly by estimating how many rows a query will touch. That is the constraints step, done by the machine.

Search engines keep an inverted index, a dict from each word to the documents that contain it, so a query is a few lookups and a merge rather than a scan of every page. Build tools and package managers apply topological sort to order work, and report a circular dependency when the order comes out short.

In machine learning code the bottleneck is often a hidden quadratic loop, such as comparing every row with every other row. The fix is the same as here: name the repeated question and give it a structure that answers it fast.

#Common Mistakes

#Try It: Five Mixed Problems

#Recap

Read the constraints first: they give the target cost, under the stated assumptions of simple steps and worst-case input. Then follow the six steps: restate, examples, brute force, bottleneck, improve, test edge cases. The brute force is your oracle, and the bottleneck is the repeated question that a technique answers.

Choose by a fixed order of questions: sorted or monotone, pair or slice, repeated minimum, graph, smaller copies of the same problem, enumeration, tiny n. Every technique has an invariant and an input that breaks it, so state the invariant before you code. DP and greedy look alike, so reject greedy with a counterexample or prove it.

Lower bounds tell you when to stop. Debug with an operation counter, a doubling test and a seeded stress test. Check the traps: late constraints, hidden linear work, shared rows in a grid, slices in a loop, and the empty input.