Sliding Window vs Prefix Sum
Use a sliding window when the answer is one contiguous range you can grow and shrink under a rule. Use prefix sums when you need the total of arbitrary ranges, or when negative numbers break the window's assumption.
Both turn a nested loop over every subarray into a single pass, and they fail in different places. A window works because growing it only ever pushes you one way and shrinking pushes you back, so you never have to look at a range twice. Prefix sums make no such assumption: they precompute totals once, and any range is then a subtraction.
Side by side
| Dimension | Sliding window | Prefix sum |
|---|---|---|
| Shape of the answer | One contiguous range, grown and shrunk | Any range, computed on demand |
| Setup | None, the window is the loop | One O(n) pass to build the table |
| Query cost | Amortised O(1) per step | O(1) per range, after the build |
| Negative numbers | Breaks a sum constraint, the rule stops being monotonic | Handled, subtraction does not care about sign |
| Extra space | O(1), or O(k) for a count map | O(n) for the table |
| Counting subarrays | Awkward, the window gives you one at a time | Natural, paired with a hash map of seen sums |
When to pick each
Sliding window
- Longest or shortest range satisfying a rule: longest substring without repeats, smallest subarray with a sum of at least S.
- Fixed-size windows, where the state updates by adding one element and dropping one.
- Rules about the contents rather than the total, like at most K distinct characters.
Prefix sum
- Many range-sum queries on an array that does not change.
- Counting subarrays with an exact sum, where prefix sums in a hash map answer it in one pass.
- Anything with negative values, which is exactly where a window stops working.
- Two dimensions, where a 2D table answers any rectangle with four lookups.
Reaching for a window on subarray sum equals K. It passes the examples with positive numbers and then fails the first test with a negative, because shrinking the window no longer reduces the sum and the loop has no safe direction to move. The giveaway is any array that can hold negatives together with an exact-sum target, and the fix is prefix sums with a hash map.
Questions people ask
Why does a window need the rule to be monotonic?
Because the left pointer never goes back. A window relies on the fact that if a range is invalid, every larger range containing it is also invalid, which is what lets you shrink from the left without reconsidering. Negative numbers break that: adding an element can reduce the sum, so an invalid range can become valid by growing, and the single pass misses it.
Can I use both in one problem?
Yes, and some problems need it. Counting subarrays whose sum is at most K on an array of positive numbers can be done with a window, while the exact-sum version needs prefix sums. The combination of a prefix table and a hash map of counts is itself the standard answer for a whole family of counting questions.
What replaces prefix sums when the array changes?
A Fenwick tree or a segment tree. A prefix table is only correct while the array stays still, since one update invalidates every entry after it. A Fenwick tree gives you a prefix sum in O(log n) and a point update in O(log n), which is the trade you make for mutability.