Know this before you start: “A hash map of totals seen so far, to count subarrays”

Counting subarrays with a map of totals

A adds up to k exactly when two running totals differ by k. Keep a count of every total seen so far and each step asks: how many earlier totals were total − k?

The idea

Any subarray nums[i..j] sums to prefix[j + 1] − prefix[i]. So “a subarray sums to k” means “an earlier total equals the current total minus k”.

Walk once with a running total. Before adding the current total to the map, look up how many times total − k has appeared: each one is the start of a subarray ending here.

Start the map with {0: 1}: the empty prefix, so subarrays that begin at index 0 are counted too. This works with negative numbers, where a doesn't.

Worked example

Subarrays summing to 0 in [1, −1, 1, −1]

  1. seen = {0: 1}. total 1: no earlier 1 → count 0; seen {0: 1, 1: 1}.
  2. total 0: one earlier 0 → count 1; seen {0: 2, 1: 1}. total 1: one earlier 1 → count 2.
  3. total 0: two earlier 0s → count 4. Those are [1, −1] twice, [−1, 1] and the whole array.

Pseudocode

The steps in plain words. ← means “set to”; indentation shows what's inside what.

seen ← {0: 1}(the empty prefix)
total ← 0, count ← 0
for each x in nums:
total ← total + x
count ← count + seen[total − k](earlier totals that leave k)
seen[total] ← seen[total] + 1
return count

See it run

The worked example, step by step, beside the Python. The highlighted line is the one running.

Step-by-step

nums = [1, -1, 1, -1], k = 0

nums

01
1-1
21
3-1

seen (total → times)

0→1
total = 0count = 0

Solution · Pythonline 5

from collections import defaultdict
def count_sum_k(nums, k):
seen = defaultdict(int)
seen[0] = 1 # the empty prefix
total = count = 0
for x in nums:
total += x
count += seen[total - k] # earlier totals that leave exactly k
seen[total] += 1
return count
print(count_sum_k([1, -1, 1, -1], 0)) # 4
print(count_sum_k([1, 2, 3], 3)) # 2: [1, 2] and [3]

Step 1 of 14· line 5

The empty prefix has total 0: count it once, so subarrays starting at index 0 are found too.

  • just added

time and O(n) space for the map, instead of checking every subarray.

When you'll use it

  • “How many subarrays sum to k”, “divisible by k” (store total % k), “equal 0s and 1s” (count 0 as −1).
  • Any subarray question with negative numbers, where a sliding window can't decide when to shrink.

In the wild · Analytics dashboards: “Sales between March 3 and March 17” is one subtraction of two running totals, so charts answer any date range instantly instead of re-adding every day.

Common mistakes

  • Forgetting seen[0] = 1, which misses every subarray that starts at index 0.
  • Adding the current total to the map before looking up total − k: with k = 0 every position then counts itself.

Practise it · before the Prefix Sum problems

Subarrays that add up to zero

Return how many non-empty runs of consecutive numbers in nums add up to exactly 0.

Input nums = [1, -1, 1, -1]

Output 4

[1, −1] twice, [−1, 1] and the whole array.

Input nums = [1, 2, 3]

Output 0

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?