Sliding Window vs Prefix Sum: Two O(n) Tricks, One Deciding Question

You have an array. It's full of numbers. You need a subarray with a certain sum. "O(n)," you think, reaching confidently for the first technique you learned. Ten minutes later you're stuck, the interviewer is quiet, and the window that was supposed to slide somewhere has very much stopped sliding.

The technique does apply. You just picked the wrong one.

The distinction is simple: sliding window is a discovery tool, and prefix sum is a query tool. Once that clicks, you'll know within thirty seconds which one to reach for, and you can spend the remaining forty-three minutes on code instead of second-guessing yourself.

What a Sliding Window Actually Does

A sliding window maintains a contiguous subarray by moving two pointers. The window expands or contracts based on some condition. The insight is that you never re-examine every element from scratch on each step.

arr = [2, 1, 5, 2, 3, 2]  target sum >= 7

Step 1:  [2  1  5] 2  3  2   sum=8, condition met, shrink left
Step 2:   2 [1  5  2] 3  2   sum=8, still met
Step 3:   2  1 [5  2] 3  2   sum=7, condition still met, try smaller
Step 4:   2  1  5 [2] 3  2   sum=2, too small, expand right

The window is always your current subarray under consideration. You're asking: "which contiguous chunk satisfies my condition?"

Two flavors matter here. A fixed-size window of size k slides one step at a time. A variable-size window expands when you need more and contracts when you've gone too far. Either way, each element enters the window once and leaves once, so total work is O(n).

Space is O(1) for fixed windows (track left pointer, right pointer, a running aggregate). Variable windows can reach O(k) if you track element frequencies inside the window, like in longest substring without repeating characters.

What Prefix Sum Actually Does

Prefix sum is preprocessing. You build one auxiliary array before answering any questions. Think of it as the informational equivalent of meal prepping: you do the work on Sunday so Monday-you can just grab and go.

arr    =  [ 3,  1,  4,  1,  5,  9,  2]
          index: 0   1   2   3   4   5   6

prefix =  [ 0,  3,  4,  8,  9, 14, 23, 25]
          index: 0   1   2   3   4   5   6   7
          (prefix[i] = sum of arr[0..i-1])

Any range sum from index l to r (inclusive) is prefix[r+1] - prefix[l]. One subtraction, O(1).

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

# Sum of arr[2..4] = prefix[5] - prefix[2] = 14 - 4 = 10
# Verify: 4 + 1 + 5 = 10 ✓

You're not discovering anything dynamically. You've indexed every possible cumulative sum upfront. The payoff is O(1) per query after O(n) build time, but you always pay O(n) extra space.

The One Question That Decides

Before you pick a technique, ask: does the problem change if there are negative numbers in the array?

If yes, use prefix sum. If no, sliding window is probably cleaner.

Here's why negatives are the deciding factor. A variable-size sliding window relies on a monotonic assumption: making the window bigger increases (or at least doesn't shrink) the metric you're tracking. If you're hunting for subarrays with sum greater than or equal to a target, shrinking from the left only makes sense when the window is already above target. That logic holds perfectly when all numbers are non-negative. Add one negative, and a window that looks too large might actually need to get larger, because the negative element ahead will drag the sum down before a big positive restores it.

The window's core contract is: "larger window means larger sum." Negative numbers shred that contract immediately.

Prefix sum doesn't care about negatives. It records every cumulative sum and lets you answer questions about arbitrary ranges without any traversal assumptions. Negatives are just numbers. Subtraction still works.

Where Sliding Window Wins

Maximum sum subarray of size k is the canonical fixed-window problem.

def max_sum_fixed(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

O(n) time, O(1) space. You could solve this with prefix sum too: prefix[i+k] - prefix[i] for each i. But that costs O(n) space for an array you scan once and discard. Sliding window is strictly better here. Sometimes the boring answer is correct.

Any problem where you need to know which elements are inside the current subarray belongs to sliding window. Longest substring without repeating characters (LeetCode 3) tracks which characters are active in a set. Minimum window substring (LeetCode 76) needs counts of required characters inside the window. Prefix sum tells you the aggregate of a range. It cannot tell you what's in it.

For the full template and variable-window mechanics, the sliding window algorithm guide has both flavors end to end.

Where Prefix Sum Wins (and Sliding Window Falls on Its Face)

Subarray sum equals k (LeetCode 560) is the canonical prefix sum problem. It's also the clearest example of why you cannot just default to sliding window every time.

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}
    for num in nums:
        prefix += num
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Try to do this with a sliding window. You'll hit a wall quickly. The input [-1, 1, 1] with k = 1 has three valid subarrays: [-1, 1, 1] (sum 1), [1] (second element), and [1] (third element). A window that contracts when the sum gets too large will miss the first one entirely. You'll get count 2, submit, and wonder why the judge disagrees.

The prefix sum + hashmap pattern works like this: at each index, you know the running sum up to here. If you can find an earlier index where the running sum was current_prefix - k, then the subarray between those two points sums to exactly k. The hashmap answers "how many times have I seen this earlier prefix value?" in O(1). One pass, O(n) time, O(n) space.

This pattern generalizes to any problem that asks you to count subarrays. Count subarrays with sum divisible by k, find the longest subarray with sum at most k, check whether any subarray sums to zero. All of them reduce to prefix sum + some data structure.

When Both Work: The Fixed-Window Overlap

For fixed-size windows with all-positive numbers, both techniques reach O(n) time. The space split is what separates them.

Sliding window: O(1) space. You track a running sum and slide one pointer.
Prefix sum: O(n) space. You store the whole prefix array.

Sliding window wins when you only need one pass over the data.

The calculus flips for repeated queries over the same array. If you need fifty different range sums over the same dataset, building the prefix array once costs O(n) and each query costs O(1). Running a sliding window fifty times costs O(50n). Build once, query many is prefix sum's reason for existing. This is the "index first, ask questions later" philosophy applied to arrays.

Scenario	Sliding Window	Prefix Sum
Fixed window max/min sum	O(n) time, O(1) space	O(n) time, O(n) space
Variable window, positive numbers only	O(n) time, O(1) to O(k)	O(n) build + binary search
Subarrays with exact sum k (with negatives)	Doesn't generalize	O(n) time, O(n) space
Multiple range sum queries	O(q * n) for q queries	O(n) build + O(1) per query
Track elements inside the window	O(n) with hash set	Cannot track elements
2D range queries (matrix)	Not applicable	2D prefix sum, O(mn) build

The Negative Number Test in Practice

When you're in an interview and unsure which to use, run this quick mental check.

Pick any test case and mentally add a negative number somewhere. Does that negative break the "shrink left when sum is too big" logic? If yes, sliding window won't generalize to the full problem. Pivot to prefix sum + hashmap.

Does the problem ask for the window's contents rather than a count or aggregate? Prefix sum can't answer that alone. Use sliding window with a tracking structure.

The clearest signal for prefix sum is when the problem says "count subarrays." Counting implies you need to visit every valid subarray. The prefix sum + hashmap achieves this in one pass by asking: how many earlier states could complete a valid subarray ending at this index? It's genuinely elegant once you see it, and it looks like magic to interviewers who haven't seen it.

Drilling the Switch

The sharpest way to internalize this: solve one problem from each category back to back in the same session. Start with maximum sum subarray of size k using sliding window, then do subarray sum equals k with prefix sum. The mental shift between them is the actual skill you're building.

Knowing the technique is step one. Applying it while talking through your reasoning under time pressure is the harder part. SpaceComplexity runs voice-based mock interviews where you work through exactly these pattern-recognition calls out loud, scored on both your decision process and your final code.

Once you can identify the right tool in the first two minutes, your interview time goes toward coding, not deliberating.

For more on the boundary between these and the two-pointer technique, see two pointers vs sliding window. For a curated set of sliding window problems to drill, see sliding window LeetCode problems.