Subarray Sum Equals K

This is the most important problem in the section, and one of the most asked medium problems anywhere. It is the point where prefix sums stop being a lookup table and become a way of searching: instead of asking "what is the sum of this range?", you ask "which earlier point would make the range ending here sum to k?"

Many candidates try a sliding window first, because the problem says "contiguous subarray". The window fails as soon as numbers can be negative, and noticing that — and saying why — is part of what the interviewer is listening for.

The problem

Given a list of integers and a target k, return how many contiguous, non-empty subarrays have a sum of exactly k.

• nums = [1, 2, 3, -2, 2], k = 3 → 4. The subarrays are [1, 2], [3], [2, 3, -2] and [3, -2, 2].
• nums = [0, 0, 0], k = 0 → 6. Every one of the 6 subarrays sums to 0.

Constraints: 1 ≤ n ≤ 10⁵, values between −1000 and 1000, and k between −10⁷ and 10⁷.

Clarifying questions

• Count them, or return them? Count. (Returning them all could need O(n²) output.)
• Can values be negative? Zero? Both. This matters a lot — see below.
• Can k be 0 or negative? Yes.
• Do overlapping subarrays count separately? Yes; each (start, end) pair is one subarray.
• Non-empty only? Yes; the empty subarray never counts, even when k = 0.

Approach 1: the simple way

Try every start. For each start, extend the end one step at a time and keep a running total, so each subarray's sum costs O(1).

1def subarray_sum_brute(nums: list[int], k: int) -> int:2    """Try every start; extend the end while keeping a running total."""3    count = 04    for start in range(len(nums)):5        total = 06        for end in range(start, len(nums)):7            total += nums[end]8            if total == k:9                count += 110    return count

Time is O(n²), space O(1). (Summing each subarray from scratch would be O(n³); the running total already saves a factor of n.)

Why it is too slow: there are n(n + 1)/2 subarrays. At n = 10⁵ that is about 5 × 10⁹ — minutes of Python. We need to stop enumerating subarrays one by one.

Why not a sliding window? A window grows its right edge while the sum is too small and shrinks its left edge while it is too big. That only works if adding an element always raises the sum. With [1, -1, 1] and k = 1, the answer is 3 ([1], [1, -1, 1], and the last [1]), but a window cannot know whether adding −1 will help or hurt later. Negatives break the window's one assumption.

The key insight

Use the prefix sums from the core idea: prefix[k] is the sum of the first k elements. A subarray from index i to index j sums to

prefix[j + 1] - prefix[i]

We want that to equal k. Rearrange:

prefix[i] = prefix[j + 1] - k

Read it as a question you can ask at every position j: "How many earlier prefix sums equal my current prefix minus k?" Each one marks a start i where the subarray i..j sums to exactly k.

That turns a search over pairs into a lookup. Walk left to right, keep running (the current prefix sum), and keep a hash map from each prefix value to how many times it has appeared so far. At each step:

1. Add the current element to running.
2. Add counts[running - k] to the answer — that many subarrays end here.
3. Record running in the map, for the positions still to come.

Two details make it correct. The map must start with {0: 1}, because the empty prefix (before index 0) is a real starting point — without it, [1, 2] in the example is never found. And the lookup must happen before recording the current prefix, so a position never pairs with itself (which would count an empty subarray when k = 0).

This is exactly the hash map "have I seen the complement?" idea from Two Sum, applied to prefix sums instead of values.

Approach 2: prefix sums plus a count map

1def subarray_sum(nums: list[int], k: int) -> int:2    """Count subarrays summing to k with prefix sums and a count map."""3    counts = {0: 1}             # the empty prefix: lets a subarray start at index 04    running = 05    answer = 06    for value in nums:7        running += value8        answer += counts.get(running - k, 0)      # earlier prefixes that fit9        counts[running] = counts.get(running, 0) + 110    return answer

We use .get() rather than a defaultdict for the lookup on purpose: reading a missing key from a defaultdict inserts it with count 0, which quietly grows the map with keys that never occurred.

Dry run on nums = [1, 2, 3, -2, 2], k = 3

Each match is one subarray. At i = 1, the prefix 0 (before index 0) gives [1, 2]. At i = 2, the prefix 3 (after index 1) gives [3]. At i = 3, the prefix 1 (after index 0) gives [2, 3, -2]. At i = 4, the prefix 3 again gives [3, -2, 2]. Total 4. The figure runs the same idea on a second array with k = 7.

Complexity. Time is O(n): one pass, with an O(1) average map lookup and update per element. Space is O(n): in the worst case every prefix is different and the map holds n + 1 keys.

Edge cases

• The answer starts at index 0. [3], k = 3 → 1. Only the {0: 1} seed finds it.
• k = 0 with zeros. [0, 0, 0] → 6. The count map is what makes repeated prefixes work: the third 0 prefix pairs with all three earlier ones.
• Prefixes that repeat. [1, -1, 1, -1], k = 0 → 4. The count for prefix 0 and prefix 1 each climbs to 2, and each repeat adds that many subarrays at once.
• No match. [5], k = 3 → 0.
• Empty input. The loop does nothing and returns 0.

Saying it in the interview

Follow-ups

• "Return the longest such subarray instead." Store the first index of each prefix (seeded {0: -1}) instead of a count, and take i - first[running - k]. The next lesson, Contiguous Array, is this exact shape.
• "All numbers are non-negative." Now growing the window never lowers the sum, so a sliding window counts in O(n) time with O(1) space. (Careful with zeros: they create several windows with the same sum.)
• "Count subarrays whose sum is divisible by k." Compare remainders instead of values: two prefixes with the same remainder mod k bound a divisible subarray. That is the last lesson in this section.