STEP 3 · ARRAYS · PREFIX SUM + FREQUENCY MAP · MEDIUM

Count Subarrays With Sum K

WHAT IT SAYS

Count how many contiguous subarrays of an array sum to exactly k. The array may contain negatives.

WHAT IT'S REALLY ASKING

"Freeze the right end at index j and let S be the running total up to there. A subarray ending here hits k exactly when the chunk you chop off the front sums to S - k. So you were never hunting subarrays — you were asking, at every step, how many times have I already walked past a running total of S - k?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Total up every subarray

O(n^2) time, O(1) space

Pick a start i, extend an end j to the right, carry a running sum, and increment the answer every time it equals k. Restart the sum for every new i.

WHERE THE WORK IS WASTED — Every subarray sum is the difference of two prefix sums, and an array of length n has only n+1 prefix sums in it — that is the entire supply of raw material. Brute force re-derives those same n+1 numbers from scratch for every starting index: O(n^2) additions to manufacture O(n) distinct facts. Start at index 5 and you re-add elements 5, 6, 7 that you already added when you started at index 2.

KEY OBSERVATION — THE UNLOCKlink

A subarray sum is a difference of two prefix sums.

Define P[i] as the sum of the first i elements, so P[0] = 0. Then sum(i..j) = P[j+1] - P[i], because everything before i appears in both prefix totals and cancels. Now set that equal to k and solve for the thing you do not know: P[i] = P[j+1] - k. Read what just happened. With the right end fixed at j, the set of valid starts is no longer something to search for — it is exactly the set of earlier prefixes whose value is one specific number. A subarray is a coincidence between two odometer readings. So counting subarrays becomes counting how many times a particular value has occurred before. That is a frequency question, and a frequency question is O(1) if you keep a tally as you go. Note it must be a tally, not a flag: three different earlier prefixes can share the value P[j+1] - k, and each of them is a genuinely different subarray with its own start index. Existence is not enough — you need the count. Two details fall out of the same algebra. First, the tally must be seeded with P = 0 occurring once, because a subarray that starts at index 0 chops off the empty prefix, and the empty prefix has sum 0 — omit it and every answer anchored at the front of the array becomes invisible. Second, you must consult the tally BEFORE inserting the current prefix, or when k = 0 you will happily count the empty subarray as a hit.

One pass, one tally

O(n) time, O(n) space

Carry a running sum and a map from prefix value to how many times you have seen it, seeded with 0 -> 1. At each element: add it to the running sum, add map[running - k] to the answer, then bump map[running] by one. Never look backwards, never re-add anything.

WHAT YOU TRADED — You spend O(n) memory on the tally, and you give up the sliding window's O(1) space — but you gain the thing the window cannot survive: negative numbers. A window only works if growing it monotonically grows the sum, so the moment negatives appear the shrink-from-the-left logic is meaningless. Prefix-plus-map does not care about signs at all, because it never assumes anything about direction.

WATCH THE IDEA RUN

-3

running sum 0

prefix needed -

found here 0

total count 0

seen sum 0 x1

Before the array even starts, the running total is 0 and you have seen it once. That phantom entry is what lets a subarray that begins at index 0 ever be counted.

step 1 / 10

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Difference of Prefixes

YOU'LL SEE IT AGAIN WHEN

The quantity over a range is expressible as f(end) minus f(start) — sums, counts, balances, running differences.
You are counting how many ranges qualify, not finding one, so you need the frequency of past states rather than mere existence.
The array contains negatives or zeros, which kills any argument that a window can be grown and shrunk monotonically.

SAME BLUEPRINT, DIFFERENT PROBLEM

Subarray Sums Divisible by KContiguous Array (equal 0s and 1s)Count Subarrays With XOR KBinary Subarrays With Sum

The bar isn't "solved it once." It's "could rebuild it from the observation."