mediumDSA

How do you count subarrays that sum to k?

Q: How do you count subarrays that sum to k?

**Intuition.** A subarray sum equals prefix[j] − prefix[i] . So a subarray ending at j sums to k exactly when an earlier prefix equals prefix[j] − k . Keep a running prefix sum and a **hash map of how many times each prefix value has occurred** — then each step adds those matches in O(1). k=3: at prefix 6, look up prefix 6−3=3 seen before 1 <rect x

342 views

Understand the problem

Explain the prefix-sum + hashmap method.

arraysprefix-sum

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Prefix sum + hash map

Run Playground

def subarray_sum(nums, k):
    counts = {0: 1}
    total = run = 0
    for x in nums:
        run += x
        total += counts.get(run - k, 0)
        counts[run] = counts.get(run, 0) + 1
    return total


# --- demo ---
print(subarray_sum([1, 1, 1], 2))   # 2
print(subarray_sum([1, 2, 3], 3))   # 2  ([1,2] and [3])

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find a peak element in an array?

How do you solve the 3Sum problem?