Sign in
Skip to solution
mediumDSA

How do you count subarrays that sum to k?

342 views
01

Understand the problem

Explain the prefix-sum + hashmap method.

arraysprefix-sum
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Maintain a running prefix sum and a hash map of how many times each prefix sum has occurred. For each index, the number of subarrays ending there with sum k equals the count of prefixSum - k seen so far. O(n) time and space.

Solution ready — 2 min read

Classified // press E to declassify

04

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])
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 80 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track