Prefix Sum & Subarray Count

Medium

Count subarrays summing to k. Every subarray sum is a difference of two prefix sums, so a map of seen prefixes does it in one pass.

hash maplinear

TimeO(n)

SpaceO(n)

Inputnumbers | target sum k

-2

seen map

0:1

count0

Counting subarrays that sum to 3. Seed the map with prefix 0 seen once, which covers subarrays starting at index 0.

1 / 16

count = {0: 1}; pre = 0; ans = 0

for x in a:

pre += x

ans += count[pre - k]

count[pre]++

Why it matters

Works with negative numbers, where sliding window does not.

Practise this

Keyboard

space play← → stepr restartctrl K search