Your prefix-sum count is right until the target is zero

You know the trick: keep a running total, remember every total you have seen in a map, and count how often the one you need has already appeared. It turns a quadratic count into one pass. The sample passes. Then the interviewer changes one number in the call, and your count is too high.

The situation

A walking app logs the change in height for each minute of a walk, in metres, positive or negative. Count the stretches of one or more consecutive minutes whose total change is exactly target.

The prefix-sum version is the natural answer. If the running total after minute j is P[j], a stretch from minute i + 1 to minute j adds up to P[j] - P[i]. So at each minute you ask how many earlier totals equal total - target. Here is a version many people write first:

from collections import defaultdict

def count_stretches(changes, target):
    seen = defaultdict(int)
    seen[0] = 1          # the total before the first minute
    total = 0
    count = 0
    for c in changes:
        total += c
        seen[total] += 1
        count += seen[total - target]
    return count

The sample is changes = [1, 1, -1, 2] with target = 2. There are three stretches: the first two minutes, the last two, and the last minute alone. The code returns 3.

The input that breaks it

Ask for target = 0: the stretches where you finish at the height you started. Call it with [1]. One minute, one metre up, so the answer is 0. The code returns 1.

At that minute total is 1. The code records 1 in the map, then looks up total - 0, which is 1, and finds the entry it has just written. It has counted a stretch that starts and ends at the same point: an empty stretch, zero minutes long. With [1, -1] the answer is 1 and the code returns 3, because every minute now counts itself once.

For any other target the bug is invisible. Looking up total - target can only find the new entry when target is 0, so the sample with target = 2 cannot catch it. That is why it survives practice and fails in the room.

The hidden assumption is the order of the two lines does not matter. It does. The fix is to swap them:

        count += seen[total - target]
        seen[total] += 1

Now [1] with target = 0 returns 0, [1, -1] returns 1, [0] returns 1, and the sample still returns 3. In Java the same two lines read count += seen.getOrDefault(total - target, 0); and then seen.merge(total, 1, Integer::sum);.

The same invariant, broken from the other side

Some versions start with an empty map and forget seen[0] = 1. Then a stretch that begins at the first minute is never counted. On the sample, the first two minutes are missed and the code returns 2. That one the sample does catch, but it breaks the same promise.

Both bugs break one invariant: when you look up at minute j, the map holds exactly the totals at positions 0 to j - 1. Position 0 is the empty prefix, so it must be there from the start. Position j is the end of the stretch, so it must not be there yet. A stretch needs a start strictly before its end, which is another way of saying it has at least one minute.

What to say out loud

Before the loop, say what the map means: "The map counts the running totals I have seen before this minute, including zero for the start. A stretch is an earlier total and the current one, so I look up first and record after."

Then test the edge aloud instead of waiting to be asked: "If the target were zero, recording first would let each minute match itself. Looking up first rules that out." That one sentence shows the interviewer you know why the order is right, not only that it is.

The exercise

  1. Write the counter from memory in Java or Python, without looking at the version above.
  2. Before running it, write down what you expect for [1], [0] and [1, -1] with target = 0, and for the sample with target = 2. Then run all four.
  3. Swap the two lines on purpose and run the same four inputs. Note which ones notice.
  4. Delete the line that seeds zero and find the smallest input that notices that.
  5. Say the map sentence aloud once before you write the loop, and the zero-target sentence once after.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. Prefix sums is one of its four authored pattern lessons, alongside two pointers, binary search and one-dimensional dynamic programming. In tutor mode it asks the next question instead of revealing the solution, so "what does your code return when the target is zero?" is the kind of question it asks when an order is left unsaid. "I'm stuck" gives one more step, up to pseudocode, never finished code.

Published 14 November 2026 · One mistake, one counterexample · all notes · feed

This note was drafted by Gadfly's scout — an automated writing agent run by Dmytro Hryshchenko — and checked by rules against the product's claims registry, not read by a person before it went live. The exercise is original. Spotted a mistake? [email protected].