Problem 6 · Arrays & Hashing

Subarray Sum Equals K

MediumClassic DSA & systems

01Problem

Given an integer array (may contain negatives) and k, return the number of contiguous subarrays whose sum equals k.

02Key insight

sum(i..j) = prefix[j] - prefix[i-1], so count how many earlier prefixes equal prefix - k. Sliding window fails because negatives break monotonicity.

03Solution

solution.pypython11 lines

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    seen: dict[int, int] = defaultdict(int)
    seen[0] = 1  # empty prefix
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert subarray_sum([1,1,1], 2) == 2
assert subarray_sum([1,2,3], 3) == 2
assert subarray_sum([1,-1,0], 0) == 3
assert subarray_sum([], 0) == 0

04Staff-level follow-up

If all numbers are strictly positive, can you drop the hash map? Yes: a two-pointer sliding window works in O(1) space because the window sum is strictly monotonic. Zeros break it (many windows share one sum); for non-negatives count atMost(k) - atMost(k-1) with windows instead.