Why does the shrinking sliding window break when a contiguous-stretch problem allows negative values?
answer
- why is the left edge allowed to move forward only
- what the shrink step promises about the total
- adding a value could lower the total
- a retired start might still be optimal
- differences of running totals give any stretch
basics
~20 sThe shrinking window assumes the total only rises when you extend right and only falls when you advance the left edge. Negative values break that monotonicity, so a discarded left endpoint can still belong to the answer.
solid answer
~50 sThe two-pointer window is sound only because of an invariant: once the tracked quantity exceeds the limit, advancing the left edge is guaranteed to reduce it, and a left endpoint you retire can never be part of a better later window. That guarantee comes from monotonicity — with non-negative values, the total grows on extension and shrinks on contraction. Allow negatives and both directions fail: shrinking from the left can *increase* the total, and a window that is currently over the limit may become valid again after extending right. The window then silently returns a too-small answer; it does not crash, and it passes every non-negative test case. The replacement is prefix sums plus a lookup structure: a hash map of previously seen prefix totals for an exact-target stretch in expected O(n), or a monotonic deque over prefix sums for a shortest-stretch-at-least-K in O(n). You trade O(1) extra space for O(n).
code
pseudocode · 10 lineslo = 0
total = 0
best = 0
for hi in 0..length(a)-1:
total = total + a[hi]
while total > L and lo <= hi:
total = total - a[lo]
lo = lo + 1
best = max(best, hi - lo + 1)
return bestgo deeper
Be ready to say that a shrinking window needs the tracked total to move predictably as the edges move, and that negative values remove that guarantee. Recognising the risk is enough at this level.
State the invariant precisely — extending never lowers the total, shrinking never raises it, therefore a retired start can never help again — and show which half of it negatives break.
Demonstrate the diagnosis. Explain that the failure is a silently wrong answer that survives every non-negative sample, and name the prefix-sum replacement plus the space it costs.
Own the general rule that a stated constraint overrides a surface cue, and make that habit visible in how your team reviews solutions: every pattern choice carries a named assumption that someone checks.
## The invariant the window rests on A shrinking sliding window maintains a span `[lo, hi]` and a running aggregate over it. The loop extends `hi` by one, then advances `lo` while the span is infeasible. Its correctness rests on a claim that is easy to forget because it is never written down: > Extending the right edge never decreases the tracked quantity, and advancing the left edge never increases it. Therefore, if a span starting at `lo` is already infeasible, no longer span starting at `lo` can be feasible — so `lo` may be retired forever. That is what makes each index move at most once and the whole scan O(n). It is also exactly what negative values destroy. ## What negatives do With negative values in the sequence, the running total is no longer monotone in either endpoint. Advancing the left edge past a negative entry **raises** the total instead of lowering it, so the shrink loop can push the window further away from feasibility. Worse, a span that is infeasible now may become feasible after extending right, because the next entries may be negative. The retirement argument — "this left endpoint can never help again" — has no justification left, and the algorithm reports a shorter stretch than the true optimum. Note the failure mode: it is not a crash and not a slowdown. It is a **wrong answer that looks right on every sample you are likely to type by hand**, because hand-written samples of "lengths", "counts" and "durations" are all non-negative. The test that catches it is one you must think to write. The same reasoning generalises past sums. A window over a product breaks once values may be negative or lie strictly between minus one and one. A window on "maximum total over a contiguous run" breaks even with only the shrink step removed, because the optimum may need to absorb a locally losing prefix. By contrast, a window tracking a **count** — how many distinct items are inside the span, how many of a given kind — stays monotone regardless of the values, which is why distinct-item window problems are unaffected by this trap. ## What to reach for instead Once monotonicity is gone, the window's constant-space trick goes with it and you buy the answer with memory: - **Exact target total over a contiguous run.** Walk the sequence keeping the running prefix total, and keep a hash map from prefix total to how many times (or how early) it was seen. A stretch ending here with total exactly T exists precisely when the value `currentPrefix - T` has been seen before, since the difference of two prefixes is a contiguous stretch. Expected O(n) time, O(n) space; the expected qualifier is real, because hash lookups degrade under adversarial key collisions. - **Shortest contiguous run with total at least K, values possibly negative.** Keep a deque of indices whose prefix totals are strictly increasing. From the front, pop and record any index whose prefix is far enough below the current one; from the back, pop any index whose prefix is not below the current one, since it can never be a better start. O(n) time, O(n) space. - **Maximum total over a contiguous run.** Kadane's scan: at each position take either the current entry alone or the current entry plus the best run ending at the previous position. O(n) time, O(1) space — a dynamic-programming recurrence, not a window. ## The general lesson about cues This is the cleanest example of a cue and a constraint disagreeing, and the rule is that **the constraint wins**. "Contiguous run" genuinely does point at the window family; a single sentence elsewhere in the statement — "values may be negative" — disqualifies it. Reading the ask and stopping there is what produces a confident wrong pattern. The same shape appears elsewhere. A statement that says "the k largest" points at a size-k heap, which costs O(n log k); if the constraints let k equal the input size, that is O(n log n) and an outright sort is simpler and no worse. A statement that says "sorted" points at halving, which needs random access the storage may not provide. The interview-grade habit is to name the assumption at the same moment you name the pattern: "contiguous, so a window — that assumes the totals are monotone, which needs non-negative values; let me check the constraints." Interviewers plant the negative-value clause precisely to see whether the mapping was recalled or reasoned.
- Name another cue that the constraints can invalidate the same way."The k largest" points at a size-k heap for O(n log k), but if the constraints allow k to reach the input size, that is O(n log n) — the same as sorting outright, with more code and no advantage. Similarly, "the input is sorted" points at halving, which the storage model can rule out if reaching the midpoint is not constant-time. In each case the surface cue is real and a stated constraint overrides it.
- Which contiguous-run problems are unaffected by negative values?Those whose tracked quantity is a count rather than a sum: how many distinct items are inside the span, how many of a given kind, the longest run with at most k distinct entries. Adding an element can only raise the count and removing one can only lower it, so the retirement argument survives whatever the values are. The trap is specific to aggregates whose direction the values control.
- What does the switch from a window to prefix sums cost you?Space, and the worst-case guarantee. The window runs in O(1) extra space with a hard linear bound; prefix sums with a hash map need O(n) space and give expected O(n) time, degrading under adversarial collisions. A monotonic deque over prefix sums keeps a true O(n) worst case but still holds O(n) indices. On a memory-bounded target that difference can decide the design.
saying these in an interview costs you the question
- Believes a window works on any contiguous-run problem
- Cannot state the monotonicity invariant behind the shrink step
- Thinks negatives make the window slow rather than wrong
- Validates only on hand-written non-negative samples
- Confuses the maximum-run scan with a sliding window