Arrays & Hashing crash course ↗ · 166

560. Subarray Sum Equals K

Count contiguous subarrays whose elements sum to k. A running prefix sum paired with a hash map of prefix-sum frequencies turns the count into a single linear pass — and it survives negative numbers, where a sliding window cannot.

● MediumPrefix SumHash MapTypeScript

PROBLEM What we're solving

Return how many contiguous subarrays of nums sum to k. With nums=[1,1,1], k=2 the answer is 2 — the windows [0,1] and [1,2] each sum to 2. With nums=[1,2,3], k=3 the answer is 2 ([1,2] and [3]).

KEY IDEA A window equals a difference of two prefix sums

Insight → let P[i] be the sum of the first i elements. The subarray ending at the current index with sum k exists for every earlier prefix where P[j] = sum − k, because sum − P[j] = k. So keep a map of how many times each prefix sum has occurred; at each step add count[sum − k] to the answer. Seed it with {0:1} so subarrays starting at index 0 are counted.

RECIPE Seed, sweep, look up, record

  • 0 · Seed. count = {0:1}, sum = 0, total = 0. The 0:1 entry represents the empty prefix so a window starting at index 0 is counted.
  • 1 · Extend. For each x, do sum += x — the prefix sum up to here.
  • 2 · Look up first. Add count[sum − k] to total. This counts every earlier prefix that closes a sum-k window ending here.
  • 3 · Record after. Then count[sum] += 1. Doing the lookup before the insert is what prevents an empty subarray (sum-0) from being miscounted.
Classic confusion → a sliding window does not work here. Sliding windows assume that growing the window only increases the sum (and shrinking only decreases it), which holds for non-negative arrays. With negatives the sum is not monotonic, so you can never safely decide when to shrink. The prefix-sum-plus-map approach makes no monotonicity assumption, so it handles negatives for free.

COST Complexity & alternatives

Every subarray, sum each
O(n²)
Two nested loops with a running inner sum.
Prefix sum + hash map
O(n)
One pass; O(n) space for the map.

Why not a window?

A two-pointer sliding window would be O(n) too, but it is simply wrong for arrays with negatives — there is no valid rule for when to advance the left pointer. The hash-map method trades O(n) space for correctness under negatives.

Pattern transfer → the "prefix sum, then ask the map for sum − k" trick powers Continuous Subarray Sum (store sum % k), Subarray Sums Divisible by K (store remainders), and Contiguous Array (map +1/−1 prefix to first index seen).

RUN IT Run a prefix sum, ask the map for sum − k

step 0 / 10
STARTSeed the map with {0:1} (the empty prefix has sum 0, seen once), sum = 0, total = 0. Target k = 2.
1function subarraySum(nums: number[], k: number): number {
2▶  const count = new Map<number, number>();
3▶  count.set(0, 1);              // empty prefix: sum 0 seen once
4▶  let sum = 0;                  // running prefix sum
5▶  let total = 0;                // subarrays found
6 
7  for (const x of nums) {
8    sum += x;                   // extend prefix by x
9    total += count.get(sum - k) ?? 0;  // prefixes that close a sum-k window
10    count.set(sum, (count.get(sum) ?? 0) + 1);
11  }
12  return total;
13}
101112
State
0
sum
0
total
{0:1}
map
current element / sumprocessed / totalsum − k (the key we look up)hit found in map
slowfast

TYPESCRIPT The solution, annotated

subarraySum.ts
function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>();
  count.set(0, 1);              // empty prefix: sum 0 seen once
  let sum = 0;                  // running prefix sum
  let total = 0;                // subarrays found

  for (const x of nums) {
    sum += x;                   // extend prefix by x
    total += count.get(sum - k) ?? 0;  // prefixes that close a sum-k window
    count.set(sum, (count.get(sum) ?? 0) + 1);
  }
  return total;
}

Reading it block by block

Lines 2–5 — seed the state. The map starts at {0:1}: a prefix sum of 0 has been seen once (the empty prefix). Without this seed, any subarray that starts at index 0 would be missed. sum and total start at zero.
Lines 7–8 — extend the prefix. Adding x makes sum the total of everything from index 0 up to the current element.
Line 9 — the lookup, done first. Every earlier prefix equal to sum - k marks the start of a subarray ending here that sums to k. We add the frequency of that prefix (not 1) because the same prefix sum can recur.
Line 10 — record this prefix. Bump count[sum] so future indices can close windows against it. Crucially this happens after the lookup, so the current prefix never matches itself as a zero-length window.
Line 12 — return the tally. total has accumulated one count for every qualifying subarray across the single pass.
Complexity → O(n) time — one pass with O(1) map operations. O(n) space for the prefix-sum frequency map in the worst case (all prefix sums distinct).

INTERVIEWFollow-ups they'll ask

  • "Why does a sliding window fail?" With negatives the prefix sum is not monotonic, so there is no valid shrink condition — the window method only works for non-negative arrays.
  • "Why seed with {0:1}?" It represents the empty prefix so subarrays beginning at index 0 (where sum === k) are counted.
  • "Why look up before inserting?" Inserting first would let k === 0count the current element's prefix against itself as a zero-length window.
  • "Subarrays divisible by k?" Store ((sum % k) + k) % k as the key instead of the raw sum.
  • "Return the actual subarrays, not just the count?" Map each prefix sum to the list of indices where it occurred and reconstruct ranges — at the cost of more space.

OPTIMAL Prefix Sum

subarraySum.ts
function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>();
  count.set(0, 1);              // empty prefix: sum 0 seen once
  let sum = 0;                  // running prefix sum
  let total = 0;                // subarrays found

  for (const x of nums) {
    sum += x;                   // extend prefix by x
    total += count.get(sum - k) ?? 0;  // prefixes that close a sum-k window
    count.set(sum, (count.get(sum) ?? 0) + 1);
  }
  return total;
}
Complexity → O(n) time — one pass with O(1) map operations. O(n) space for the prefix-sum frequency map in the worst case (all prefix sums distinct).

ALT 1 Brute force — sum every subarray

O(n²) time · O(1) space

Fix a start index, extend the end, and keep a running inner sum, counting whenever it hits k. Correct and simple, but quadratic.

approach-2.ts
function subarraySum(nums: number[], k: number): number {
  let total = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) total++;
    }
  }
  return total;
}
Note → The inner loop keeps a running sum so it avoids an O(n³) re-sum, but it still inspects every start/end pair. The prefix-sum map collapses this to a single pass by remembering how many earlier prefixes equal sum - k.

MNEMONIC The one-liner

"Running prefix, ask the map for sum minus k — seed zero, look up before you store."

TRIGGERS When you see ___ → reach for ___

count contiguous subarrays summing to kprefix sum + freq map
array may contain negativesprefix-sum map (NOT a window)
subarrays starting at index 0seed map with {0:1}
divisible-by-k / balanced 0s & 1s variantstore sum % k or +1/−1 prefix

SKELETON The reusable shape

skeleton.ts
const count = new Map<number, number>();
count.set(0, 1);          // seed the empty prefix
let sum = 0, total = 0;
for (const x of nums) {
  sum += x;
  total += count.get(sum - k) ?? 0;
  count.set(sum, (count.get(sum) ?? 0) + 1);
}
return total;

FLASHCARDS Tap to flip

What makes a window of sum k appear at the current index?
An earlier prefix sum equal to sum - k, since current sum - prefix = k.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Optimal time complexity?
QUESTION 02
At each index, what do you add to the running total?
QUESTION 03
Why is the map seeded with {0:1} before the loop?
QUESTION 04
Why must the lookup happen before incrementing count[sum]?
QUESTION 05
Why does a two-pointer sliding window NOT solve this problem in general?
QUESTION 06
For nums=[1,1,1], k=2, the answer is:
QUESTION 07
You add count[sum − k] (the stored frequency) rather than 1 because…
QUESTION 08
#560 · Subarray Sum Equals KCount contiguous subarrays summing to k in one pass by pairing a running prefix sum with a hash map of seen prefix counts (seeded with {0:1}). Handles negatives, where a sliding window cannot. O(n) time and space.Which algorithmic approach does this primarily use?
QUESTION 09
#560 · Subarray Sum Equals KCount contiguous subarrays summing to k in one pass by pairing a running prefix sum with a hash map of seen prefix counts (seeded with {0:1}). Handles negatives, where a sliding window cannot. O(n) time and space.Which implementation correctly solves it?