35Brute force, then spot the waste

In Chapter 34 we finished building the yardstick: count the operations, watch them grow, respect the constant. By the end of it we could look at almost any loop and say what it costs. But a yardstick only measures. It never tells you what to build. So in this chapter we turn measuring into a method — a five-step loop you can run on any problem. It works on an interview whiteboard, and it works in a 3 a.m. production incident. Here's the whole plan in one breath. Solve it the dumb way, measure it, find the work you're repeating, delete that work, then re-check the cost. And the one question we keep asking the whole way through is where am I doing work I've already done? By the end you'll have a reflex that fires before you write a single clever line. And you'll see why that loop, not raw cleverness, is the real difference between someone who codes and someone who engineers.

01Start with brute force. It is step one, not shame.

Let's start with the move everyone's a little embarrassed to make. Brute force means exactly what it sounds like: try every possibility and check each one. It has a bad reputation it does not deserve — because brute force is where every hard problem starts, and it does two irreplaceable jobs. First, it pins down what "correct" even means — you cannot optimize an answer you can't yet produce. Second, it hands you a baseline complexity: the number to beat. Skip it and you're optimizing in the dark.

Watch how it plays out on the problem we'll ride all chapter — two-sum. Given a list of numbers and a target, find two of them that add up to the target. Concretely: your playlist has tracks of length [200, 90, 150, 60] seconds, and you want two that exactly fill a 240-second (4:00) slot. The brute-force reading is literal: look at every pair and test its sum. How many pairs are there? Pick the first element (n choices), pick a different second (n−1 choices), and since the pair (i, j) is the same as (j, i), divide by two. That's n(n−1)/2 pairs — a number we counted, not looked up. For n = 4 that's exactly 6 pairs.

def two_sum_brute(nums, target):
    n = len(nums)
    for a in range(n):                       # pick the first element
        for b in range(a + 1, n):            # pick a LATER second element
            if nums[a] + nums[b] == target:  # test this pair's sum
                return (a, b)                # done the instant we find one
    return None                              # no pair adds up

Read the code as the picture we just drew. The outer loop picks a, and the inner loop picks every b to its right. That "to its right" is the a + 1, and it's why we only fill the triangle and never re-check a pair. The if then tests the one thing we actually care about, the sum. This version is obviously, boringly correct, and right now that is its whole value. Ship the boring version first, because you now have a truth you can measure and a truth you can test every clever version against.

Before trusting any formula, run the machine by hand once. The playlist is [200, 90, 150, 60] and the target is 240. Walk the pairs in exactly the order the loops produce them. First 200+90 = 290, then 200+150 = 350, then 200+60 = 260, and then 90+150 = 240, a hit. The loop returns on its fourth check, so the two pairs after it, 90+60 = 150 and 150+60 = 210, never run. Add those up and you've verified the formula too: 4 checks done plus 2 skipped is exactly the 6 pairs we counted for n = 4. That habit of auditing the machine with a four-item input will save you more hours than any tool you ever install.

But notice why it stopped at check 4: the answer happened to sit near the front. That's the best case, and you can't count on luck. Point the target somewhere impossible, say 999, which no pair reaches, and the loop grinds through all 6 pairs before it gives up. That's the worst case: no pair exists, so nothing lets it quit early. From here on we measure the worst case, because it's the guarantee that holds no matter which input shows up. Best case flatters you. Worst case protects you.

We have a correct answer. But "correct" isn't "good." How expensive is this, really — and where does it hurt? →

02Measure the baseline — count, then feel the growth

Deriving the cost is just reading the loops, the skill we built in the Big-O chapter. The inner body runs exactly once per pair, so the operation count is n(n−1)/2. Drop the constant and the lower term and the label is O(n²). But a formula on its own is abstract, so let's make the growth land in your gut by running it. I counted the exact inner-loop checks in the worst case, where no pair exists and it scans everything:

Every 10× more input is 100× more work — that's the signature of squaring. The same signature shows up on the clock. I timed the real function (worst case, on this laptop — your absolute numbers will differ, the shape will not):

Now for the trap that ends careers quietly. It's a trap precisely because nothing looks wrong at first, or for months. At n = 1,000 this brute force finishes in ~19 ms. It feels instant, it ships, and everyone says it "works on my laptop." Then someone pushes it to a million items. The squared growth means about 250,000× the work of the n=2,000 run. Extrapolated from the measured times, that is roughly 5.5 hours for one single call. The demo was fine. Production is on fire. And the only thing that changed between the working demo and the burning production was n.

That 5.5-hour figure isn't a scare tactic, and you can re-derive it from the table above. At n = 2,000 the measured time was 79 ms. A million items is 500× more input, and squared growth turns 500× into 500² = 250,000× the work. So the estimate is 79 ms × 250,000 = 19,750,000 ms, which is 19,750 seconds. Divide by 3,600 and you get about 5.5 hours. Notice what we just did there, because it's a professional skill. We extrapolated from a small measurement using the growth law, instead of waiting hours to measure the big case directly. The complexity class is what makes that prediction trustworthy: it tells you the shape of the curve, so a few cheap points pin down the expensive ones.

you type
# ---------- brute_toolkit.py ----------
from itertools import combinations, permutations, product
from math import comb, perm, factorial

nums, target = [200, 90, 150, 60], 240

print("the brute force, as one loop over combinations")
for a, b in combinations(nums, 2):
    print(f"  {a:>3} + {b:>3} = {a + b:>3}   {'MATCH' if a + b == target else ''}")

print("\nthe three generators, on three letters")
print("  combinations('ABC', 2)", list(combinations("ABC", 2)))
print("  permutations('ABC', 2)", list(permutations("ABC", 2)))
print("  product('AB', '12')   ", list(product("AB", "12")))
print("  product('01', repeat=3)", ["".join(t) for t in product("01", repeat=3)])

print("\ncount BEFORE you generate -- comb() is arithmetic, not a loop")
for n in (4, 1_000, 1_000_000):
    print(f"  n={n:<9} comb(n,2)={comb(n, 2):<20,} perm(n,2)={perm(n, 2):,}")

def human(secs):                             # seconds -> the unit a human can feel
    for size, name in ((.001, "ms"), (1, "seconds"), (60, "minutes"),
                       (3600, "hours"), (31_557_600, "years")):
        if secs < size * 1000 or name == "years":
            return f"{secs / size:,.1f} {name}"

print("\nthe explosion, in real numbers -- at a billion checks per second")
for n in (10, 15, 20):
    print(f"  all orders of {n}: {factorial(n):>25,}  = {human(factorial(n) / 1e9)}")

$ python brute_toolkit.py

you see
the brute force, as one loop over combinations
  200 +  90 = 290
  200 + 150 = 350
  200 +  60 = 260
   90 + 150 = 240   MATCH
   90 +  60 = 150
  150 +  60 = 210

the three generators, on three letters
  combinations('ABC', 2) [('A', 'B'), ('A', 'C'), ('B', 'C')]
  permutations('ABC', 2) [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
  product('AB', '12')    [('A', '1'), ('A', '2'), ('B', '1'), ('B', '2')]
  product('01', repeat=3) ['000', '001', '010', '011', '100', '101', '110', '111']

count BEFORE you generate -- comb() is arithmetic, not a loop
  n=4         comb(n,2)=6                    perm(n,2)=12
  n=1000      comb(n,2)=499,500              perm(n,2)=999,000
  n=1000000   comb(n,2)=499,999,500,000      perm(n,2)=999,999,000,000

the explosion, in real numbers -- at a billion checks per second
  all orders of 10:                 3,628,800  = 3.6 ms
  all orders of 15:         1,307,674,368,000  = 21.8 minutes
  all orders of 20: 2,432,902,008,176,640,000  = 77.1 years

So the baseline is quadratic and it will detonate. Good — now the single most valuable question in all of engineering. →

03The one question: where is the wasted work?

Here is the mental move that turns a coder into an engineer. You look at the brute force and ask: where am I doing work I've already done, or don't need to do? Wasted work hides in three shapes, and you learn to smell all three:

So what are the three shapes? First, recomputing — working out the same value again when you could have kept the first answer. Second, re-scanning — walking over data you've already walked over, hunting for something a moment's memory would have handed you. Third, exploring dead ends — doing work on possibilities you could have ruled out before you started. Almost every slow algorithm is guilty of one of these, and often you can name which one just by squinting at the loops. Two-sum, as we're about to see, is a textbook case of the second.

• Recomputing — calculating the same value over and over (you'll kill this with memoization / dynamic programming in ch40).
• Re-scanning — sweeping through data you already looked at (killed with hashing, ch37, and two-pointers, ch38).
• Ignoring structure — the data is sorted, or bounded, or monotonic, and you're not exploiting it (killed with binary search, ch43, and more).

Point the question at two-sum. For each element x, brute force computes what it needs (need = target − x) and then re-scans the whole rest of the list hunting for that number. But look at what the scan is searching through: numbers we already walked past. We had them in our hands one step ago and we threw them away, so now we walk the list again, and again, and again. The wasted work is the re-scan. The inner loop is a search for a value we've already seen.

How much work is actually wasted? Slide it and see. The brute force does n(n−1)/2 comparisons. A solution that looked at each element just once would do n. The gap between those two bars is the redundant work, and it's almost the entire bar.

It's worth asking why n is the number to aim for and not something even smaller. Any correct solution has to at least look at every element once, because a number it never reads could be half of the answer. So n steps is the honest floor for this problem, and it makes the waste measurable. At n = 1,000 the brute force performs 1,000 × 999 / 2 = 499,500 comparisons, while the floor is 1,000 looks. Do the division: 499 out of every 500 comparisons are redundant, which is 99.8% of the bar. We're not hunting a small trim here. Nearly everything the loop does is re-checking something it already had. Knowing the floor also tells you when to stop optimizing, because once you touch it, there is nothing left to delete.

And here's the part that should grow on you: that waste fraction isn't fixed, it climbs with n. The useful work is always n looks. The total is n(n−1)/2. So the fraction that actually earns its keep is 2/(n−1). At n = 1,000 that's 2/999, about 0.2% useful and 99.8% wasted, exactly the split we just found. Push to a million and it's 2/999,999, under two ten-thousandths of a percent useful. The bigger the job, the larger the share of it that is pure redundancy. That isn't a reason to despair. It's the opportunity, sitting right there waiting to be deleted.

That question is the whole solution. The fix is the most human idea in computing: write it down. →

04Kill it with a technique — remember what you've seen

When you keep re-searching for the same thing, you stop searching and start remembering. In code, "remember, and look up instantly" is a dict. That's the hash table from Volume 1. It answers "is X in here, and where?" in roughly one step, O(1), no matter how full it gets. (That's a whole technique on its own, and the hashing chapter is devoted to it.) So we walk the list once, and at each element x we ask the dict a single question: "have I already seen target − x?" If the answer is no, we drop x into the dict and move on. The inner scan doesn't get faster. It disappears.

def two_sum_fast(nums, target):
    seen = {}                        # value -> the index we saw it at
    for i, x in enumerate(nums):     # ONE pass, no inner loop
        need = target - x            # the partner that would complete the pair
        if need in seen:             # already met it? O(1) dict lookup
            return (seen[need], i)   # found the pair
        seen[x] = i                  # otherwise, remember x for later
    return None

Line by line: seen is the memory — a value mapped to where we found it. The single loop takes each x in turn. need is the number that would complete the pair. need in seen is the move: instead of re-scanning, we ask the dict, and it answers in one hop. If the partner is there, we're done; if not, we record x so a future element can find us. Every past element is already written down, so no element ever gets looked at twice. Run it on the playlist and watch the memory fill until it pays off:

i=0 x=200 need=40  40 in seen? no   -> remember  seen={200:0}
i=1 x=90  need=150 150 in seen? no  -> remember  seen={200:0, 90:1}
i=2 x=150 need=90  90 in seen? YES  -> return (1, 2)     # 90 + 150 = 240

Three steps and it stops. Step 0 remembers 200. Step 1 remembers 90. Step 2 needs 90, and 90 is already written down at index 1, so it returns instantly. The list of 90 and 150 was never scanned twice. The dict just recognized the partner the moment it walked by. Step it in full in trace T31.

Now do for the fast version exactly what we did for the brute force: count its actual work. Step 0 asks the dict "is 40 in here?" (because 240 − 200 = 40), gets no, and writes 200 down. Step 1 asks for 150 (240 − 90), no, writes 90. Step 2 asks for 90 (240 − 150) — and there it is. That's 3 lookups and 2 writes, 5 operations, against brute force's 4 checks on the very same list. On four items the hash version is actually a hair more work. The win isn't here — it's in the curve. At n = 4 the two run neck and neck, but n(n−1)/2 pulls away from n the instant n grows.

One worry should nag you: could the one-pass version ever miss a pair the brute force would find? Here's the argument that it can't. Say the answer is the pair at positions i and j, with i earlier. When the loop reaches j, every element before j is already in the dict, because we recorded each one as we passed it. The element at i is before j, so it's in there, and the lookup finds it. That property, "at step j, everything earlier is remembered," holds on every single step of the loop. An always-true statement like that is called an invariant, and finding one is how engineers trust code they can't exhaustively test.

The re-scan is gone and the answer's still correct. But "feels faster" is a feeling. Prove it. →

05Re-check the complexity — did it actually get better?

Never trust a "faster" version until you've re-derived its cost. Clever code fools people constantly. So count again. The fast version has one loop over n elements. Each iteration does a fixed amount of work: one subtraction, one dict lookup, maybe one dict insert, all O(1) on average (Volume 1's hash table). One times n is O(n). We traded n(n−1)/2 for n. Not a shave — a change of curve, from the exploding red to the gentle blue.

Two honest words in that count deserve a spotlight: on average. A dict lookup is O(1) in the typical case, but hash tables do have a worst case. When many keys land in the same bucket, a single lookup can degrade toward O(n) as it wades through the collisions. Python's hash functions are engineered so ordinary data spreads out evenly, and in practice you will almost never see that degradation. But "O(n) total" is a claim about the average case, not a law of nature. We say that out loud instead of hiding it, because a cost model you can't state honestly will eventually burn you. The hashing chapter (ch37) opens that box completely.

And because it's a curve change, the win doesn't just exist — it grows with n. I measured both versions on the same inputs (worst case, this laptop; treat the exact milliseconds as approximate):

Look at that speedup column climbing. It isn't a fixed "10× faster" — the multiplier itself doubles as n doubles, because O(n²) vs O(n) means the ratio is n/2. That million-element call that would've taken ~5.5 hours by brute force? The hash version finishes it in well under a tenth of a second. Same laptop, same problem, different curve. Turn the knob below and watch the wall-clock cross from milliseconds into years:

There's an honest cost, and a 1% engineer names it out loud: the dict holds up to n entries, so we spent O(n) extra memory to buy O(n) time. That's the space–time tradeoff (ch33) — hashing and memoization both pay memory to delete work. Almost always worth it. Not free.

Make the memory cost concrete, so "O(n) extra" isn't just a symbol on a page. For the million-item case, seen can grow to a million entries. In CPython that means tens of megabytes for the hash table alone, plus more for the integer objects it points at. On a laptop with gigabytes free, trading that for 5.5 hours of saved compute is the easiest deal you'll ever sign. But the tradeoff has a direction, and it can flip. On a microcontroller with kilobytes of RAM, or with data too big for one machine, the memory side of the ledger suddenly rules. That's why we name both costs every time instead of crowning a universal winner.

"""three_ways.py -- one problem, three algorithms, one op counter each."""
import random, time
from itertools import combinations
from math import comb, log2

def two_sum_brute(nums, target):            # O(n^2) time, O(1) extra space
    ops = 0
    for i, j in combinations(range(len(nums)), 2):
        ops += 1                            # one pair tested = one op
        if nums[i] + nums[j] == target:
            return (nums[i], nums[j]), ops
    return None, ops

def two_sum_two_pointer(nums, target):      # O(n log n) to sort, then O(n) to walk
    a = sorted(nums)                        # <- the real bill lives on this line
    ops, lo, hi = 0, 0, len(a) - 1
    while lo < hi:
        ops += 1                            # one look at the two ends
        s = a[lo] + a[hi]
        if s == target:
            return (a[lo], a[hi]), ops
        if s < target: lo += 1              # too small: the low end is hopeless
        else:          hi -= 1              # too big:  the high end is hopeless
    return None, ops

def two_sum_hash(nums, target):             # O(n) time, O(n) extra space
    ops, seen = 0, set()
    for x in nums:
        ops += 1                            # one probe + one insert
        if target - x in seen:
            return (target - x, x), ops
        seen.add(x)
    return None, ops

class Counted(int):                         # an int that reports every comparison
    cmps = 0
    def __lt__(self, other):
        Counted.cmps += 1
        return int(self) < int(other)

random.seed(35)
nums = random.sample(range(1, 100_000), 2_000)
n = len(nums)
present = nums[11] + nums[1_987]            # a pair that exists, deliberately far apart
absent  = 1                                 # no two positive values sum to 1

for name, target in (("pair EXISTS", present), ("pair ABSENT (worst case)", absent)):
    print(f"\n{name}   n = {n},  target = {target:,}")
    for fn in (two_sum_brute, two_sum_two_pointer, two_sum_hash):
        t0 = time.perf_counter()
        pair, ops = fn(nums, target)
        dt = (time.perf_counter() - t0) * 1000
        print(f"  {fn.__name__:<20} ops {ops:>9,}   {dt:>7.2f} ms   pair {pair}")

Counted.cmps = 0
sorted(Counted(x) for x in nums)            # what did sorted() actually spend?
print(f"\nthe sort the two-pointer version needs: {Counted.cmps:,} comparisons"
      f"  (n*log2(n) = {n * log2(n):,.0f})")
print(f"brute-force worst case = comb(n,2) = {comb(n, 2):,} pair tests")

agree = 0                                   # the oracle: 2,000 random cross-checks
for _ in range(2_000):
    xs = random.sample(range(1, 60), random.randint(2, 12))
    t = random.randint(2, 118)
    answers = [fn(xs, t)[0] for fn in (two_sum_brute, two_sum_two_pointer, two_sum_hash)]
    found = [a is not None for a in answers]
    assert len(set(found)) == 1, (xs, t, answers)          # all three, or none
    assert all(sum(a) == t for a in answers if a), (xs, t) # and any pair returned is real
    agree += 1
print(f"oracle: {agree:,} random cases, all three agree on existence, 0 mismatches")


# ---------- what it printed here (your milliseconds will differ; the counts will not) ----------
#
# pair EXISTS   n = 2000,  target = 75,643
#   two_sum_brute        ops    23,910      1.29 ms   pair (8102, 67541)
#   two_sum_two_pointer  ops       710      0.17 ms   pair (6166, 69477)
#   two_sum_hash         ops       764      0.06 ms   pair (16631, 59012)
#
# pair ABSENT (worst case)   n = 2000,  target = 1
#   two_sum_brute        ops 1,999,000    120.64 ms   pair None
#   two_sum_two_pointer  ops     1,999      0.31 ms   pair None
#   two_sum_hash         ops     2,000      0.18 ms   pair None
#
# the sort the two-pointer version needs: 19,293 comparisons  (n*log2(n) = 21,932)
# brute-force worst case = comb(n,2) = 1,999,000 pair tests
# oracle: 2,000 random cases, all three agree on existence, 0 mismatches
#
#
# ---------- the four answers ----------
#
# 1. WHICH LEVER DID EACH ONE PULL?
#    Versions two and three changed f(n): 1,999,000 pair tests became 1,999 looks and
#    2,000 probes. Nothing about the loop body got faster -- there are simply ~1,000x
#    fewer trips through it. A micro-optimised brute force would still lose, because
#    a constant cannot close a gap that grows with n.
#
# 2. WHY THE TWO-POINTER WALK IS NOT THE WINNER.
#    Its walk is 1,999 steps, cheaper than the hash version's 2,000. But the walk is
#    only legal on sorted data, and sorted() spent 19,293 comparisons buying that --
#    ten times the walk itself, and O(n log n), not O(n). Honest total:
#      brute        1,999,000 ops        O(n^2)
#      two-pointer  19,293 + 1,999       O(n log n)   <- the sort dominates
#      hash         2,000 ops            O(n)
#    Two pointers win when the data ARRIVES sorted, or when you needed it sorted
#    anyway. Sorting just for this is paying n log n to avoid a dict.
#
# 3. WHAT VERSION THREE COSTS.
#    The set holds up to n values. At n = 1,000,000 that is tens of megabytes -- free
#    on a laptop, fatal on a microcontroller with kilobytes of RAM, and awkward when
#    the data does not fit on one machine. Version two's O(1) space is its one real
#    advantage: it allocates nothing at all. Name both costs; do not crown a winner.
#
# 4. THE PROPERTY, NOT THE OUTPUT.
#    Look at the "pair EXISTS" run: (8102, 67541), (6166, 69477), (16631, 59012).
#    Three different pairs -- and all three sum to 75,643. Asserting equal outputs
#    would fail on correct code. The property that IS true of all three:
#      * they agree on whether a pair exists at all, and
#      * any pair returned really does sum to the target.
#    Test the property, not the answer. That is the whole idea behind
#    property-based testing, and it is what makes an optimisation you cannot
#    eyeball safe to ship.

Two-sum was one problem. But that sequence — dumb, measure, spot, delete, re-check — wasn't about two-sum at all. It's the loop. →

06The loop is the whole game

Step back and name what we just did, because you'll do it in every chapter from here on. It's a five-step cycle, and it never changes:

That's it, and it really is the whole operating system for the rest of this book. Notice what that means for the rest of Volume 3: it is just a toolbox for step 4. Divide & conquer (ch36), hashing (ch37), two pointers and sliding windows (ch38), greedy (ch39), dynamic programming (ch40), and backtracking (ch41) are all coming. Each one is a specific way to delete a specific kind of waste, nothing more. So you don't sit down and memorize which one to use in advance. You find the waste, and the technique that kills that waste is the one you reach for. Steps 2 and 5, the counting steps, are the same skill from chapters 31 and 32. They exist to keep you from lying to yourself about the improvement. Play the whole loop live in the Algorithms Lab.

The transfer out of code is real and it's daily. Binary-search your debugging: don't read all 400 commits, bisect them. Hash your memory: don't re-derive a phone number every time, write it down for instant recall. Greedy your errands: nearest stop first. Don't re-solve what you've solved. The loop — "what am I doing over and over that I could do once?" — is a way of seeing, and it works on spreadsheets, supply chains, and your own calendar.

for _ in range(200_000):                      # throw random cases at both
    nums = [randint(-20, 20) for _ in range(randint(0, 8))]
    target = randint(-40, 40)
    assert (brute(nums, target) is None) == (fast(nums, target) is None)   # oracle: both agree WHETHER a pair exists (the two may pick different valid indices)
# ran clean: 0 mismatches

Step 4 needs techniques. The first and most powerful one is a single idea: what if, instead of one big problem, you had two half-sized ones — and each of those split again? The next chapter is the power of halving. →