Learn

Your sliding window works until one of the numbers is negative

31 October 2026 · One mistake, one counterexample

You see "contiguous" and "sum" in the same question, and your hand reaches for a sliding window. It passes the example, it runs in linear time, and you say so with some pride. Then the interviewer asks whether the values can be negative, and the window you trusted turns out to rest on a rule nobody wrote down.

The situation

You are given a list of account movements, deposits and withdrawals, and a target amount. The question: is there a run of consecutive movements whose total is exactly the target?

The familiar shape grows the window on the right and shrinks it from the left whenever the total overshoots:

def has_run(moves, target):
    left, total = 0, 0
    for right, x in enumerate(moves):
        total += x
        while total > target and left <= right:
            total -= moves[left]
            left += 1
        if total == target and left <= right:
            return True
    return False

On [2, 3, 1, 4] with target 4 it returns True: the window overshoots at 2 + 3, drops the 2, and then finds 3 + 1. Correct, and quick to trace.

The input that breaks it

Try [5, -2] with target 3. The answer is True, because 5 + (-2) is 3. The method returns False.

Trace it. After the first value the total is 5, which is more than 3, so the loop drops the 5 and the window is empty. Then -2 arrives, the total is -2, and nothing more happens. The one run that answers the question was thrown away before its second half arrived.

The hidden assumption is adding a value on the right can only raise the total, and removing one on the left can only lower it. That is what makes shrinking safe: once the total is too big, no longer window starting at the same place can come back down, so the left end can move on. It holds when every value is zero or more. A single withdrawal breaks it, and the sample input never contains one because samples are usually written with small positive numbers.

Note what the bug is not. The loop condition is fine, the indices are fine, and the code is correct for the inputs it was designed for. The mistake is choosing the pattern without checking its precondition.

The fix and the invariant

When values can be negative, keep running totals instead of a window. A run from just after position i to position j sums to the target exactly when the total up to j minus the total up to i equals the target. So remember every total seen so far and ask whether current - target is among them:

def has_run(moves, target):
    seen = {0}
    prefix = 0
    for x in moves:
        prefix += x
        if prefix - target in seen:
            return True
        seen.add(prefix)
    return False

On [5, -2] with target 3: the totals are 5, then 3, and 3 - 3 = 0 is in the set from the start, so it returns True. On [2, 3, 1, 4] with target 4: the totals are 2, 5, 6, and at 6 the value 6 - 4 = 2 is already there, which is the run 3 + 1. The 0 seeded into the set covers a run that starts at the very first movement. The check happens before the current total is added, so the run is never empty.

The price is memory: linear space for the set, where the window needed none. In Java the same idea uses a HashSet<Long>, since totals of many int values can overflow an int.

The invariant to say: a shrinking window is only correct when every value is non-negative; with negatives, use prefix sums and a set of totals seen.

What to say out loud

Before you write the window: "A sliding window works here only if the values are non-negative, because then shrinking can never skip an answer. Can a movement be negative?" If the answer is yes, say the consequence straight away: "Then the window can drop the start of a run that a later negative would have balanced. I'll use running totals and a set instead: linear time, linear space."

If you have already written the window, name the breaking input yourself: "Five then minus two, target three. My window drops the five and misses it." Naming the two-number input is the proof that you understand the bug and not only the fix.

The exercise

1. Find two solutions you wrote with a sliding window over sums or counts.
2. For each, write down the precondition it silently relies on, in one sentence.
3. Build the smallest input that violates that precondition, and predict the wrong answer before running it.
4. Rewrite one of them with prefix totals and a set, and trace both of the inputs above by hand.
5. Say the "can a value be negative?" question aloud before starting your next practice problem, even when you think you know the answer.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. Prefix sums are 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 rather than revealing the solution, so "what happens to your window when the next value is negative?" is the kind of question it would put to you; "I'm stuck" gives one more step, up to pseudocode, never finished code.