Prefix Sums With a Hash Map

Beginner: summarize everything before an index

A prefix sum is a running total from the beginning of an array. Think of a bank statement: the balance after each transaction summarizes everything that happened before that point. Subtracting two balances reveals the net change between them.

For [1, 2, -1, 3]:

index          0  1  2  3
value          1  2 -1  3
prefix sum     1  3  2  5

The sum from index j + 1 through i equals:

prefix[i] - prefix[j]

Everything through j appears in both totals and cancels, leaving only the values after j through i.

Derive the lookup instead of memorizing it

We want a subarray whose sum equals k:

currentPrefix - earlierPrefix = k
earlierPrefix = currentPrefix - k

At each position, currentPrefix is known. The second equation tells us which earlier prefix to look for. A Map stores prefix value → number of earlier occurrences.

Worked trace: [1, 1, 1], target 2

Start with {0 → 1}. The zero represents one empty prefix before the array begins.

value  prefix  needed  earlier count  matches  map after
1      1       -1      0              0        {0:1, 1:1}
1      2        0      1              1        {0:1, 1:1, 2:1}
1      3        1      1              2        {0:1, 1:1, 2:1, 3:1}

The two matching subarrays are indices 0..1 and 1..2.

Why {0 → 1}? When a current prefix itself equals k, subtracting the empty prefix produces a valid subarray beginning at index zero. Without that initial state, the first match in this trace would be missed.

function subarraySum(nums: number[], k: number): number {
  const prefixCounts = new Map<number, number>([[0, 1]])
  let prefix = 0
  let matches = 0

  for (const value of nums) {
    prefix += value
    matches += prefixCounts.get(prefix - k) ?? 0
    prefixCounts.set(prefix, (prefixCounts.get(prefix) ?? 0) + 1)
  }

  return matches
}

Intermediate: why store counts?

Different positions can have the same prefix sum. Each earlier position creates a different starting boundary for a subarray ending now. A Set would preserve existence but lose multiplicity.

For [0, 0, 0] and target 0, there are six valid subarrays: three length-one, two length-two, and one length-three. Repeated prefix zeroes are exactly what produce those different boundaries, so the Map must store how many times zero has appeared.

Prefix Map versus sliding window

A sliding window often works when values are nonnegative: expanding cannot decrease the sum, and shrinking cannot increase it. Negative numbers remove that monotonic behavior. Adding a value might make the sum smaller, so “the sum is too large; shrink” is no longer reliable.

Prefix subtraction is algebraic and does not rely on monotonicity. When negatives are allowed and the problem asks about contiguous subarray sums, a prefix Map is often the more reliable direction.

Advanced: change the stored value to match the question

The Map key can remain a prefix sum while its value changes:

• Count matching subarrays: store frequency.
• Determine whether one exists: membership may suffice.
• Return the longest matching subarray: store the earliest index.
• Return an actual boundary pair: store an index, not merely a count.

For the longest subarray, preserve the first occurrence of each prefix. Replacing it with a later index can only shorten future candidates.

The counting algorithm takes expected O(n) time and O(n) extra space. In languages with fixed-width integers, choose a wide enough running-total type for the constraints.

Common failure modes

• Forgetting the empty prefix {0 → 1}.
• Using a Set when repeated prefix states affect the count.
• Inserting the current prefix before counting earlier matches.
• Applying a sliding window even though negative values are allowed.
• Memorizing prefix - k without being able to derive it.