How does a running total plus a map of seen totals count zero-net stretches in a signed ledger?

## The scenario An audit walks a ledger of signed daily balance deltas — money in is positive, money out is negative — and asks how many contiguous billing periods net to exactly zero. Brute force checks every start and every end: O(n^2) additions, fine for a hundred days and hopeless for a million. ## The identity that makes it one pass Define the running total `P[i]` as the sum of the first `i` deltas, with `P[0] = 0` (the empty prefix, before any day). Then the total of the stretch covering days `l..r` is ``` sum(l..r) = P[r+1] - P[l] ``` A stretch nets to zero exactly when `P[r+1] == P[l]`. So the question "how many zero-net stretches are there" is really the question "how many PAIRS of positions share the same running total". Nothing about the individual deltas matters any more — only repeats of the running total. ## The algorithm Scan once. Maintain `sum` and a map `seen` from running total to how many times that total has occurred so far, seeded with `seen[0] = 1` for the empty prefix. 1. Add today's delta to `sum`. 2. Add `seen[sum]` to the answer — every earlier position holding this same total is the left edge of a zero-net stretch ending today. 3. Increment `seen[sum]`. The order matters: query first, then record. If you record first, today's position matches itself and you count an empty stretch. The same skeleton answers the general question "how many stretches total exactly `target`": look up `sum - target` instead of `sum`, because `P[l] = P[r+1] - target` is what a stretch of the required total demands. ## Why a count, not just a flag A running total can recur many times — a ledger that oscillates around the same balance produces it constantly — and each earlier occurrence is the left edge of a distinct qualifying stretch. A set that only remembers "this total appeared" undercounts badly: three earlier occurrences mean three stretches ending here, not one. Store the multiplicity. If instead you want the LONGEST zero-net stretch rather than how many there are, the bookkeeping flips: you keep the first index at which each total occurred and never overwrite it. Counting wants frequencies; longest wants earliest positions. ## Cost, stated precisely Time is O(n) map operations. Hash map lookup and insert are expected O(1) and amortized O(1) across growth, not O(1) in the worst case: adversarial or pathological key sets can collide and degrade a lookup toward O(n). For interview purposes the honest sentence is "expected linear time". Space is O(n) in the worst case — a strictly increasing balance never repeats a total, so every one of the n+1 running totals lands in the map. That is the real price of this pattern versus a two-pointer window, which is O(1) space but cannot cope with negative values. One more caution that only bites at scale: running totals accumulate, so on a long ledger of large magnitudes the totals themselves can grow beyond the range of a fixed-width integer even when every individual delta is small. The differences are what you care about, but the keys you store are the raw accumulations. ## What the pattern does NOT need It needs no sorting (sorting destroys contiguity, which is the whole point), no window, no assumption that deltas are positive, and no second pass. It does need random-access-free sequential reading only, which makes it a natural fit for streaming a ledger once. ## The common wrong answers "Two equal running totals mean the days between them were all zero" — no, they mean the days between them CANCEL; a +40 followed by a -40 qualifies. "Use a sliding window" — that assumes growing the window cannot shrink the sum, which negative deltas violate. "Sort the deltas first" — sorting reorders days, and a stretch must be contiguous.