Why does this sliding window count overestimate valid subarrays?

programming web dev
1

I’m counting subarrays where the sum is <= k using a sliding window, but some cases come out too high. I expected this to work for all integer arrays, but negatives seem to break it. What assumption is invalid here, and what’s the right approach?

function countAtMost(nums, k) {
  let left = 0, sum = 0, count = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > k) sum -= nums[left++];
    count += right - left + 1;
  }
  return count;
}
console.log(countAtMost([3, -2, 4], 4));

Sora

2

The invalid assumption is monotonicity: sliding windows only work here when all numbers are nonnegative, because then moving left right can only decrease the sum and every suffix of a valid window stays valid.

Hari