Subarray-sum problems show up often. Brute force runs over every subarray in O(N²) and times out on large inputs. Two tools — sliding window and prefix sum — collapse the same family into O(N). They don’t cover the same ground, though. Once the input has negative numbers or asks for a sum exactly equal to K, monotonicity breaks and sliding window stops working; prefix sum with a hash map takes over. The choice between them comes down to one line: does monotonicity hold on this input?

Sliding Window

Sliding window keeps two indices, left and right, and moves them together. right admits the next element into the window; when some validity condition breaks, left advances to shrink the window back to a valid state. Each element enters and leaves exactly once, so the total work is O(N).

Three variants come up most often.

  • Variable window — the size depends on the answer. Grow right while the state is valid; on a break, advance left to recover.
  • Fixed window — size K is set in advance. Each step admits one element on the right and drops one on the left.
  • Two-end pointers — for sorted arrays, left and right start at the endpoints and close inward. Common for two-element sum or combination problems.

The variable-window skeleton lifts across problems with little change.

def min_subarray_len(nums, target):
    left = 0
    window_sum = 0
    answer = float("inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum >= target:
            answer = min(answer, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return answer if answer != float("inf") else 0

This solves LC 209 — the shortest subarray with sum at least target. The validity condition is window_sum >= target, and once it is defined precisely the skeleton transfers to other problems unchanged. For the longest substring with no repeats it becomes len(seen) == right - left + 1. For the longest run of 1s after flipping up to K zeros it becomes zero_count <= K.

Why Sliding Window Needs Monotonicity

Sliding window leans on one assumption: as right advances, the window state changes monotonically. With positive sums, admitting a new element always grows window_sum; dropping one always shrinks it. That monotonicity is what justifies “once the condition breaks, push left forward and don’t reconsider earlier left positions.” Without it, every right would have to re-examine every prior left, and the complexity is back to O(N²).

Negatives break the assumption. A new element on the right can shrink the sum; a removal on the left can grow it. There’s no monotone direction for left to follow, so the skeleton stops working.

The same holds for “sum exactly equals K”. Inequalities like >= K recover gracefully — if the window grows too large, shrink it back. Equalities don’t — overshoot by one and there’s no path back.

Prefix Sum with a Hash Map

Where monotonicity breaks, prefix sum with a hash map picks up. Define prefix[i] as the sum of nums[0..i-1]. The sum of subarray nums[l..r] becomes a single subtraction: prefix[r+1] - prefix[l]. “Count subarrays whose sum equals K” reduces to counting earlier prefixes that satisfy prefix[l] == prefix[r+1] - K. Keep those prefixes in a hash map and each r is an O(1) lookup.

def subarray_sum(nums, k):
    prefix_count = {0: 1}
    prefix_sum = 0
    answer = 0

    for x in nums:
        prefix_sum += x
        answer += prefix_count.get(prefix_sum - k, 0)
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1

    return answer

Two spots need care. The initial prefix_count = {0: 1} is a sentinel — it catches subarrays that start at index 0 and happen to sum exactly to K. And the order of lookup and store matters. Store first and the lookup catches a “subarray of length zero” against itself, double-counting. Lookup always comes before store.

Choosing Between Them

The choice splits on two properties of the input.

flowchart TD
    A[Subarray sum problem] --> B{Negative values}
    B -->|Yes| D[Prefix sum + hash]
    B -->|No| C{Sum exactly K}
    C -->|Yes| D
    C -->|No| E[Sliding window]
    E --> F{Fixed window size}
    F -->|Yes| G[Fixed window]
    F -->|No| H[Variable window]

Sliding window fits when:

  • Inputs are non-negative
  • The condition is an inequality (>= K, <= K)
  • Window state changes monotonically (sum, count, set size)

Prefix sum with a hash fits when:

  • Inputs include negatives
  • The condition is an equality (sum exactly equal to K)
  • Range-sum queries arrive in batches

A rule of thumb that covers most cases: positive plus inequality goes to sliding window, negative or equality goes to prefix sum. Under live-coding pressure, that one-line check is the branching point.

Subarray-sum problems collapse from O(N²) to O(N) along two paths. Positive inputs with inequality conditions lean on sliding window’s monotonicity to narrow and grow the window. Negative inputs or strict equality break monotonicity and the work moves to prefix sum with a hash. The skeletons look alike, but which one applies comes down to whether monotonicity survives the input.

References