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. Here we turn measuring into a method: a five-step loop you can run on any problem, from an interview whiteboard to a 3 a.m. production incident. Here's the whole plan in one line. Solve it the dumb way, measure it, find the work you're repeating, delete that work, then re-check the cost. And the one thing 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. You'll also 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. Brute force is where every hard problem starts, and it does two jobs nothing else can. First, it pins down what "correct" even means — you can't 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), then a different second (n−1 choices). The pair (i, j) is the same as (j, i), so 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 it as the picture. The outer loop picks a. The inner loop picks every b to its right — that's what the a + 1 does, and it's why we only fill the triangle and never re-check a pair. The if tests the one thing we care about. It is obviously, boringly correct. That is its whole value right now. Ship the boring version first, and you now have a truth you can measure and a truth you can test against.

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 from the Big-O chapter). The inner body runs once per pair, so the operation count is n(n−1)/2. Drop the constant and the lower term and it's O(n²). But a formula 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, and the same signature shows up on the clock. I timed the real function in the worst case, on this laptop. Your absolute numbers will differ; the shape will not:

Now the trap that ends careers quietly. At n = 1,000 this brute force finishes in ~19 ms — instant, ships, "works on my laptop." Push it to a million items and the squared growth means about 250,000× the work of n=2,000. Extrapolated from the measured times, that's roughly 5.5 hours for one call. The demo was fine. Production is on fire. Nothing changed but n.

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 spot all three:

• 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 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.

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 something, you stop searching and start remembering. In code, "remember, and look up instantly" is a dict — the hash table from Volume 1 that answers "is X in here, and where?" in roughly one step, O(1), no matter how full it gets. (That's a whole technique of its own; the hashing chapter is devoted to it.) So we walk the list once. At each element x we ask the dict a single question — "have I already seen target − x?" — and if not, 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.

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, because 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. That's not a shave. It's a change of curve, from the exploding red to the gentle blue.

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, on 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. Remember 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.

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. That's the operating system. And notice: the rest of Volume 3 is just a toolbox for step 4. Divide & conquer (ch36), hashing (ch37), two pointers and sliding windows (ch38), greedy (ch39), dynamic programming (ch40), backtracking (ch41) — each one is a specific way to delete a specific kind of waste. You don't memorize which to use. You find the waste, and the technique that kills that waste is the one you reach for. Steps 2 and 5 — count the operations — are the same skill from chapters 31 and 32, and they're what keep you from lying to yourself. 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. 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. →