Why does a sliding window fail to find a stretch summing to a target when values can be negative?

## Two patterns, one problem shape Both patterns answer questions about contiguous stretches in one pass, and interviewers deliberately blur them. The decision usually turns on a single property of the data: whether the values are guaranteed non-negative. ## What the window actually assumes The expand-and-shrink window maintains a current sum for the range between two pointers, growing the right edge and, when the sum overshoots, advancing the left edge. Its correctness argument is greedy and has two halves: 1. **Monotone growth.** Extending the right edge never decreases the window sum, so if a window is already too large the only way toward the target is to shrink. 2. **Safe discard.** Once the left pointer passes a position, no future answer needs it, so each pointer advances at most n times, giving linear time with O(1) state. Sign is what underwrites both. With all values non-negative, sum is a monotone function of the window's extent. With a single negative value present, a longer window can total LESS than a shorter one, so an overshooting window may be fixed by growing rather than shrinking, and a left position discarded as unusable can be needed again. Neither half survives, and the pattern does not merely get slower — it returns wrong answers, which is worse. Zeros are a milder case: they keep the sum non-decreasing but not strictly increasing, so feasibility survives while COUNTING variants get delicate — a run of zeros creates many windows with identical sums, and naive two-pointer counting either double-counts or misses them. ## What the prefix map assumes Nothing about sign. It rests on an identity, not a greedy argument: the total of a stretch is the difference of two running totals, so "is there a stretch totalling `target` ending here" becomes "has the running total `sum - target` occurred before", answered by a map. Negative values, zeros and mixed signs are all ordinary inputs. It also counts ALL qualifying stretches, including overlapping ones, which the window fundamentally cannot do in one pass. What it costs: O(n) worst-case memory for the map — worst when the running totals never repeat — plus hashing work per element, and expected rather than worst-case constant-time lookups. On a memory-constrained embedded target or a very long stream, that difference is the whole argument. ## Choosing, out loud - Values are guaranteed non-negative, and you want the shortest or longest window meeting a threshold: **window**. O(1) state, cache-friendly, streaming, no allocation. - Any value may be negative or zero, or the question asks HOW MANY stretches hit an exact total: **prefix totals plus a map**. Correctness first; pay the memory. - Non-negative values but you need exact-total COUNTS including overlaps: the map is still the safer answer, because window-based counting on repeated sums is where subtle bugs live. The strongest interview answer names the assumption, not just the pattern: "a window is valid here only if every value is non-negative — is that guaranteed by the domain, or just true of the sample data?" That question is the point of the exercise. Domains where it is genuinely guaranteed (durations, byte counts, weights) invite the window; domains of signed deltas (ledger movements, temperature changes, sensor drift) forbid it. ## What a weak answer sounds like "Sliding window is O(1) space so it's better" — better only where it is correct. "You can fix the window by allowing the left pointer to move back" — that reintroduces the quadratic scan the window existed to avoid. "Sort the values first so they're positive-ordered" — sorting destroys contiguity and answers a different question entirely. And the reverse mistake is real too: reaching for a map on a strictly non-negative workload where a window would have been simpler, allocation-free and equally correct. ## The related-but-different variants Some threshold questions on signed data — shortest stretch whose total is at least a bound — need neither pattern in pure form: they combine running totals with a monotone structure over those totals. Knowing that such hybrids exist, and that the plain window is not among the fixes, is the differentiator between having memorised two templates and understanding what each one assumes.