skip to content

In prefix-sum counting with a hash map, why must the empty prefix (total 0) be seeded first?

level: middleimportance: must knowfreq 68%

answer

  1. Which stretches have no left neighbour
  2. There is a position the loop never visits
  3. The undercount only goes one direction
  4. Think index -1, running total 0
  5. Count of one, not a marker

basics

~20 s

Without a seeded entry for total 0, every qualifying stretch that begins at the first element is lost. Those stretches need the running total from before any element was read, and the only way the map can offer it is to record total 0 once up front.

solid answer

~50 s

The pattern pairs the running total at a stretch's end with the running total just BEFORE its start. For a stretch starting at index 0 that "just before" position is the empty prefix, whose total is 0 — a position the loop never visits, because the loop starts by adding the first element. Seeding `seen[0] = 1` puts that phantom position into the map so it can be matched like any other. The symptom of forgetting it is subtle and directional: the answer is too low, never too high, and only by the number of qualifying stretches anchored at index 0 — so small hand-checked inputs often still pass. The seed also has to be a count of one, not a marker, because the empty prefix is one real position that can be the left edge of exactly one stretch per matching end.

code

pseudocode · 14 lines
pseudocode
count = 0
sum = 0
seen = empty map        // maps running total -> occurrences

for i in 0..length(a)-1:
    sum = sum + a[i]
    if seen contains (sum - target):
        count = count + seen[sum - target]
    if seen contains sum:
        seen[sum] = seen[sum] + 1
    else:
        seen[sum] = 1

return count

go deeper

for a junior

Remember that a stretch beginning at the first element still needs something to pair with, and that something is a phantom position before the input with running total 0. Say why the answer comes out too low without it.

for a middle

Explain the loop invariant: at the moment of each lookup the map holds exactly the running totals of earlier positions plus the empty prefix. Derive both the seed and the query-before-record ordering from it.

for a senior

Show how you would catch this in review or testing. The failure is directional and small, so name the specific test shape — an input whose only qualifying stretch starts at element 0 — rather than trusting spot checks.

for a principal

Treat it as a class of defect rather than one line: silent, direction-consistent undercounts survive code review and light tests. Argue for property-based or invariant checks on aggregation code where the wrong answer still looks plausible.

## The bug, and why it hides Here is the loop that counts contiguous billing periods totalling `target`, with one line missing. Every position `i` in the scan represents the running total AFTER reading element `i`. The algorithm matches the total at a stretch's end against the total just before the stretch's start. For a stretch that starts at element 0, "just before the start" is the position before the scan began: the empty prefix, total 0. The loop never produces that position, so unless you put it into the map by hand, it can never be matched. The result is an undercount that is easy to miss: - It is always in one direction — too low, never too high. - It is exactly the number of qualifying stretches that begin at element 0, which is usually zero or one. - Any test input whose answer does not include a stretch from the very start passes cleanly. That combination is why this is the single most-asked follow-up on the pattern: the code looks right, reviews clean, and is quietly wrong on a whole class of inputs. ## Why the seed is a count of 1 The map stores multiplicities: how many earlier positions carried each running total. The empty prefix is one position, so it contributes exactly one. Seeding it with a larger number double-counts; seeding it with a boolean marker breaks the arithmetic in the accumulate step, which adds `seen[key]` rather than adding one. ## The sibling ordering bug There is a second, independent ordering requirement inside the loop: query BEFORE you record. If you insert the current running total first and then look up `sum - target`, the case `target == 0` makes the current position match itself, and you count an empty stretch at every index — an overcount of exactly n. Both rules exist for the same reason: the map must contain only positions strictly to the LEFT of the current one, plus the empty prefix. So the invariant, stated once and worth saying out loud in an interview: *when the lookup for index `i` happens, the map holds exactly the multiset of running totals for the positions before index `i`, including the empty prefix.* The seed establishes it, the query-then-record order preserves it. ## The same seed in the other variants Every member of this pattern family needs the equivalent of the seed, just spelled differently: - Counting stretches with a given total: `seen[0] = 1`. - Longest stretch with a given total: `first[0] = -1`, the index of the empty prefix, so a stretch starting at element 0 measures as `i - (-1) = i + 1` rather than `i`. Seeding with 0 there produces an off-by-one that shortens exactly the answers anchored at the start. - Counting stretches whose total divides evenly by some modulus: the bucket for remainder 0 starts at one, for the same reason. Notice how the seed's VALUE changes with what the map stores — a count of one when counting, an index of -1 when measuring length. Candidates who memorise "put 0 in the map" without knowing which quantity they are seeding get the length variant wrong. ## How to defend it under questioning Do not say "you always have to add it, that's the trick." Say what it is: a phantom position at index -1 whose running total is 0, present so that stretches anchored at the beginning have a left edge to pair with. That framing also tells you immediately what to seed in a variant you have never seen, which is exactly what the interviewer is testing.

  • Inside the same loop, why must the lookup happen before the current running total is recorded?
    Because the map must contain only positions strictly left of the current one. Record first and, when the target is zero, the current position matches itself and you count an empty stretch at every index — an overcount of exactly n. Query-then-record preserves the invariant that the map holds the running totals of all earlier positions plus the empty prefix, which is precisely the set of legal left edges.
  • The longest-stretch variant seeds the map with -1 instead of 1. Why the different value?
    Because the map stores a different quantity. When counting, the value is a multiplicity and the empty prefix contributes one occurrence. When measuring length, the value is the index at which a total first appeared, and the empty prefix sits at index -1. Seeding it with 0 there reports every stretch anchored at the start as one element too short.
  • How would you write a test that catches a missing seed, given that most inputs still pass?
    Make the answer depend on a stretch that begins at the very first element: a short input whose entire prefix hits the target, such as deltas that reach the target on day one and then move away from it. Add a case where the whole input is the only qualifying stretch. Both fail loudly without the seed and are unaffected by any other bug in the loop.

saying these in an interview costs you the question

  • Calls the seed a magic line without naming index -1
  • Seeds the map after the loop's first iteration
  • Records the running total before querying, counting empty stretches
  • Seeds a boolean marker instead of a count of one
  • Uses index 0 rather than -1 in the longest-stretch variant

context

resolving links…