Typorithm · medium

Subarray Sum Equals K

subarray-sum-equals-kprefix-sumsprefix-mapcomplementcount

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Subarray Sum Equals K

Prefix Sums

Track running prefix sums in a count map; each time sum-k was seen before, that many subarrays end here with sum k.

A subarray sums to k exactly when currentPrefix - earlierPrefix = k.

So for each running sum, the number of valid subarrays ending here is how often sum-k has appeared.

A count map of prefix sums (seeded with 0 → 1) makes each step O(1).

Seed counts with {0: 1}.

Add counts.get(sum - k) each step.

Then record the current prefix.

function subarraySum(nums, k) {
  const counts = new Map();
  counts.set(0, 1);
  let sum = 0;
  let result = 0;

  for (const num of nums) {
    sum += num;
    result += counts.get(sum - k) ?? 0;
    counts.set(sum, (counts.get(sum) ?? 0) + 1);
  }

  return result;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Empty prefix

One prefix sum of 0 exists before any element.

counts.set(0, 1)

2. Running sum

Track the cumulative sum as you scan.

sum += num

3. Find complement

A prior prefix of sum-k closes a subarray summing to k.

result += counts.get(sum - k) ?? 0

4. Record prefix

Count how many times each prefix sum has appeared.

counts.set(sum, (counts.get(sum) ?? 0) + 1)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.