Sliding a Sum Window Over Negative Numbers

A variable window that shrinks on a sum gives wrong answers when the values can be negative. Its shrinking step rests on one assumption: dropping the leftmost element never raises the sum, so once the window stops being valid, no shorter window ending here can be valid either. With non-negative values that holds. A negative value breaks it, because dropping it raises the sum.

The values 5 −4 6 3 have a shortest run with a sum of at least 8: 6 3, of length 2. The window grows to the whole array before its sum reaches 8, records length 4, then drops the 5. The sum falls to 5, below 8, and the window stops shrinking, though dropping the −4 next would have raised it to 9. The listing runs the window and a check of every run on the same values, then on non-negative values.

def shortest_by_window(values: list[int], target: int) -> int:
    start = total = best = 0
    for end in range(len(values)):
        total += values[end]
        while total >= target:
            length = end - start + 1
            best = length if best == 0 else min(best, length)
            total -= values[start]
            start += 1
    return best


def shortest_by_every_run(values: list[int], target: int) -> int:
    best = 0
    for i in range(len(values)):
        total = 0
        for j in range(i, len(values)):
            total += values[j]
            if total >= target:
                length = j - i + 1
                best = length if best == 0 else min(best, length)
                break
    return best


for values, target in [([5, -4, 6, 3], 8), ([1, 2, 3, 4], 6)]:
    window = shortest_by_window(values, target)
    every_run = shortest_by_every_run(values, target)
    print("values", *values, f"sum at least {target}: window says {window}, every run says {every_run}")

values 5 -4 6 3 sum at least 8: window says 4, every run says 2
values 1 2 3 4 sum at least 6: window says 2, every run says 2

On 5 −4 6 3 the window says 4 and the check of every run says 2; on 1 2 3 4 both say 2. Checking every run is correct for any values but costs O(n²). The fast form for negative values uses prefix sums, the running totals that turn any run's sum into one subtraction, and the Prefix Sums topic builds it.

Before choosing a variable window, check that the rule moves one way as the window grows. Sums of non-negative values, counts and sets of distinct items do. Sums that can fall do not, and a fixed window is unaffected, because its length, not its sum, decides when start moves.