Sliding Window and Prefix Sum — When Monotonicity Decides
Subarray-sum problems collapse from O(N²) to O(N) along two paths — sliding window or prefix sum with a hash. Negative inputs or strict-equality conditions break monotonicity and shift the work from sliding window to prefix sum.