Prefix Sum with Negative Numbers: Why Sliding Window Breaks

Your sliding window solution works on positive numbers. You test with negatives. Wrong Answer.

Why? Negative numbers break the monotonicity that sliding window relies on. But prefix sum + hash map handles them perfectly.

TL;DR

With negative numbers:

• ❌ Sliding window fails (sum can decrease)
• ✅ Prefix sum + hash map works

Example:

nums = [1, -1, 5, -2, 3], k = 3

# Sliding window: FAILS
# Prefix sum + hash map: WORKS

Why Sliding Window Fails

Sliding window assumes: Adding elements increases sum, removing decreases it.

With negatives: Sum can go up OR down unpredictably.

Example:

nums = [1, -1, 1], k = 1

Sliding window logic:
- Add 1: sum = 1 (equals k, count it)
- Add -1: sum = 0 (less than k, keep expanding)
- Add 1: sum = 1 (equals k again)

But this misses [1, -1, 1] which also equals 1!

Why Prefix Sum Works

Prefix sum + hash map doesn't rely on monotonicity:

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_count = {0: 1}
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
    
    return count

Works with any numbers: positive, negative, or zero.

Conclusion

Key takeaway: Negative numbers → Use prefix sum + hash map, not sliding window.

For more, see Prefix Sum + Hash Map and vs Sliding Window.