Prefix Sums With a Hash Map

Prefix Sums: Store the Total Before Each Boundary

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
}

Counting Subarrays: Why Repeated Prefix Sums Matter

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.

Trace the count rather than accepting six as magic:

before array: prefix 0 has appeared once (the empty prefix)

read first 0:  prefix = 0, find 1 earlier zero  → add 1, total 1
               record current zero             → zero count becomes 2

read second 0: prefix = 0, find 2 earlier zeroes → add 2, total 3
               record current zero              → zero count becomes 3

read third 0:  prefix = 0, find 3 earlier zeroes → add 3, total 6

Each earlier zero marks a different boundary. At the final position, pairing with the empty prefix gives the whole array, pairing with the prefix after index 0 gives the last two zeroes, and pairing with the prefix after index 1 gives the final zero alone. The prefix values are equal, but the positions—and therefore the subarrays—are different.

Practice: Count Earlier Prefix Boundaries

Before comparing techniques, try counting repeated prefix boundaries yourself. The map below contains only earlier prefixes at each lookup; predict the contribution before advancing.

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.

Monotonic means movement changes something in only one direction. With nonnegative numbers, moving the right edge forward can only keep or increase the sum. That makes a decision such as “the sum is too large, so remove values from the left” safe.

Now consider [4, -3, 2] with target 3. The entire array sums to 3. A sliding-window rule that sees 4 > 3 may immediately remove the 4. It cannot know that the next value, -3, would bring the sum back down. After discarding 4, that valid whole-array window can never be recovered.

keep 4:     4 + (-3) + 2 = 3  → valid
shrink at 4, then continue:    -3 + 2 = -1 → missed it

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.

Choose What the Prefix Map Stores: Counts or Indices

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.

The stored value must answer the output question. A frequency tells you how many earlier boundaries work, but it cannot tell you which boundary to return. An index identifies a boundary, but one index alone cannot represent several matching subarrays.

For the longest subarray, preserve the first occurrence of each prefix. Suppose the array is [1, -1, 5, -2, 3] and the target is 3:

index              -1   0   1   2   3   4
prefix sum           0   1   0   5   3   6

At index 3, the current prefix is 3, so the needed earlier prefix is 3 - 3 = 0. Prefix zero appeared at the virtual index -1 and again at index 1:

use earliest -1 → length = 3 - (-1) = 4 → [1, -1, 5, -2]
use later 1     → length = 3 - 1    = 2 → [5, -2]

Keeping the later occurrence would throw away the longer answer. Store an index only when that prefix has not been seen before:

function longestSubarraySum(nums: number[], target: number): number {
  const earliest = new Map<number, number>([[0, -1]])
  let prefix = 0
  let longest = 0

  for (let index = 0; index < nums.length; index += 1) {
    prefix += nums[index]
    const needed = prefix - target
    if (earliest.has(needed)) {
      longest = Math.max(longest, index - earliest.get(needed)!)
    }
    if (!earliest.has(prefix)) earliest.set(prefix, index)
  }

  return longest
}

The initial 0 → -1 represents the empty prefix. It allows a qualifying subarray that starts at index 0 to have the correct length: index - (-1) = index + 1.

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.