cf.completefrontend
ARRAYS & HASHING · CORE

Prefix sums with a hash map

Count or find subarrays with a given sum in one pass, by looking up earlier running totals in a hash map.

Time O(n)Space O(n)8 practice problemsStep-through picture

The idea

A subarray is a run of neighboring items, like nums[2..5]. Finding subarrays whose sum is exactly k by checking every start and end takes O(n^2) time. Sliding windows don't help when numbers can be negative.

Combine two ideas. First, the sum of a subarray is a difference of two running totals: the total at its end minus the total just before its start. Second, a hash map can remember every running total seen so far. So at each position, with running total sum, a subarray ending here sums to k exactly when an earlier running total equals sum - k.

The code walks the array once, keeps sum, asks the map how many earlier totals equal sum - k, and then records sum in the map.

An everyday example

Finding when you spent exactly 20 dollars

Your bank app shows your balance after every purchase. You want to know how many times a run of back-to-back purchases cost exactly 20 dollars. When your balance is 75 now, any earlier moment when the balance was 95 marks the start of such a run. So as you go down the list, you keep a tally of every balance you've had, and at each step ask: how many times was my balance exactly 20 more than it is now?

How the example maps to the code
In the exampleIn the code
Your balance after each purchaseThe running total sum
The tally of balances you've hadseen, a Map from running total to how many times it occurred
The balance that would make a 20-dollar runsum - k
The balance before any purchaseseen starts with [0, 1]

From the slow way to prefix sums with a hash map

  1. The obvious way to count subarrays that sum to k: try every start, extend the end one step at a time, and keep a running sum. That is about n² / 2 subarrays, so 50,000 numbers mean more than a billion steps.
  2. A sliding window can't fix this when numbers can be negative. A window shrinks when its sum is too big, but with negatives, adding a number can lower the sum and removing one can raise it. There is no safe rule for when to move either end.
  3. Rewrite the question with running totals. The subarray from j to i sums to the total of the first i + 1 numbers minus the total of the first j numbers. That equals k exactly when the earlier total is sum - k. So for each end, the question becomes: how many earlier totals equal one exact value?
  4. "How many times has this value appeared?" is counting with a hash map. Keep the running sum, look up how many earlier totals equal sum - k, then record sum. Seed the map with total 0 for the empty start. That loop is prefix sums with a hash map.

How it works

  1. Create seen holding 0 -> 1: before any number, the running total 0 has appeared once.
  2. Set sum = 0 and count = 0.
  3. For each num, add it to sum.
  4. Every earlier running total equal to sum - k starts a subarray ending here with sum k, so add seen.get(sum - k) ?? 0 to count.
  5. Record the current total: add 1 to seen's count for sum.
  6. After the loop, return count.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function countSubarraysWithSum(nums, k) {
  2. const seen = new Map([[0, 1]]);
  3. let sum = 0;
  4. let count = 0;
  5. for (const num of nums) {
  6. sum += num;
  7. count += seen.get(sum - k) ?? 0;
  8. seen.set(sum, (seen.get(sum) ?? 0) + 1);
  9. }
  10. return count;
  11. }

How fast it is

TimeO(n)
Extra memoryO(n)

One pass, with a constant-time lookup and update per number. The map can hold up to n + 1 different running totals.

  • Best caseO(n)

    There is no early exit: every number needs its own lookup, even in a one-number list like [2].

  • Average caseO(n)

    One pass with one get and one set per number, each about constant time.

  • Worst caseO(n)

    Every running total is different, so the map grows to n + 1 keys. Each step is still about constant time.

Common mistakes

  • Forgetting to start seen with 0 -> 1, which misses every subarray that starts at index 0.
  • Recording sum before looking up sum - k. When k is 0, that counts an empty subarray at every position.
  • Using a sliding window when numbers can be negative. Shrinking the window no longer always lowers the sum.
  • Using sum % k directly with negative numbers in JavaScript, which can give a negative remainder. Use ((sum % k) + k) % k.

When to use it

Look for these clues in a problem:

  • The problem asks for subarrays (contiguous runs) with sum exactly k, or sum divisible by k.
  • The numbers can be negative or zero, so a sliding window won't work.
  • You want the longest or shortest run with some balance property, like equal numbers of two kinds.
  • You could rephrase it as "two running totals that differ by k".

Check yourself

Answer each one in your head first, then open it.

In the trace, why does the last 2 add 2 to count instead of 1?

sum is 4, so it looks for 2, and total 2 appeared twice before: after the first number and after the fifth. Each one is the start of a different subarray.

What does nums = [0, 0] with k = 0 return?

3: the first 0, the second 0, and [0, 0].

Why must the lookup happen before seen.set?

If sum is recorded first, then for k = 0 the lookup finds the current total itself, which stands for an empty subarray, and counts it at every step.

How would you return the length of the longest subarray with sum k?

Store the first index where each total appears, and never overwrite it. At each step, if sum - k is stored, the length is the current index minus that stored index.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The map keeps one rule: at the top of the step for index i, seen maps each total value to how many of the totals of the first 0, 1, up to i numbers equal it. The total of the first 0 numbers is 0, which is why the map starts as {0: 1}. After the lookup, the step adds the new total, so the rule holds for index i + 1.

After sum += num, sum is the total of nums[0..i]. Each subarray ending at i has one start j, and its sum is sum minus the total of the first j numbers. That equals k exactly when that earlier total is sum - k. By the rule, seen.get(sum - k) counts exactly those starts, no more and no fewer.

Every subarray has exactly one end, so it is counted exactly once, at the step for its end, and adding up the counts over all ends gives the answer. The lookup must come before recording sum. Otherwise, when k is 0, the current total would match itself and count an empty subarray at every position.

Going deeper

3 more ideas

Why the lookup finds exactly the right subarrays

Let sum be the total of nums[0..i] and let an earlier total p be the total of nums[0..j - 1]. The subarray nums[j..i] sums to sum - p. That equals k exactly when p = sum - k. seen holds every earlier total with how often it occurred, so seen.get(sum - k) counts every start j that works for this end i.

Why seen starts with 0

A subarray that starts at index 0 has nothing before it, so its "earlier total" is the empty total, 0. Putting 0 -> 1 in the map before the loop lets those subarrays be found. Forgetting it is the most common bug with this pattern.

Variations

For the longest subarray with sum k, store the first index where each total appeared instead of a count, and compare lengths. For sums divisible by k, store totals by their remainder ((sum % k) + k) % k. For "equal numbers of 0s and 1s", treat 0 as -1 and look for sum 0.

Work it by hand

Every step in a table, with why

Count subarrays that add up to 2 in a list with negative numbers. Some answers start at index 0, and the last step finds two at once.

nums = [2, -1, 3, 1, -3, 2], k = 2

Stepnumsumsum - kFoundcountseen afterWhy
122011{0: 1, 2: 1}The seeded total 0 matches, which means the subarray from index 0 to here, [2], sums to 2.
2-11-101{0: 1, 2: 1, 1: 1}No earlier total is -1, so no subarray ending here works.
334212{0: 1, 2: 1, 1: 1, 4: 1}Total 2 was seen after the first number, so the numbers after it, [-1, 3], sum to 2.
415302{0: 1, 2: 1, 1: 1, 4: 1, 5: 1}No earlier total is 3. The map now holds five different totals.
5-32013{0: 1, 2: 2, 1: 1, 4: 1, 5: 1}Total 0 matches again: [2, -1, 3, 1, -3] sums to 2. The total 2 now has a count of 2.
624225{0: 1, 2: 2, 1: 1, 4: 2, 5: 1}Total 2 was seen twice, so two subarrays end here: [-1, 3, 1, -3, 2] and the last [2] alone.

It returns 5: [2], [-1, 3], [2, -1, 3, 1, -3], [-1, 3, 1, -3, 2], and the final [2]. Checking all 21 subarrays one by one gives the same 5, but this took 6 steps.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Prefix sums with a hash mapO(n)O(n)Numbers can be negative or zero, and you need an exact sum, count, or remainder.
Sliding windowO(n)O(1)All numbers are positive, so growing the window always raises the sum and shrinking always lowers it.
Prefix sums plus binary searchO(n log n)O(n)All numbers are non-negative and you want the totals sorted for "first position where" questions.
Check every subarrayO(n²)O(1)Very short lists, or when you must list every matching subarray anyway.

Extra memory: O(n) for the map, which holds at most n + 1 different totals. Inputs whose totals repeat a lot, like many zeros, use fewer keys.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Prefix sums with a hash map and the other approaches, on a scale where each line up is 10 times more steps.
  • Prefix sums with a hash map, Sliding window O(n)
  • Prefix sums plus binary search O(n log n)
  • Check every subarray O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Prefix sums with a hash map101,0001 million
Sliding window101,0001 million
Prefix sums plus binary search339,96620 million
Check every subarray1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list: nums = []
The loop never runs and the answer is 0.
k = 0 with zeros: nums = [0, 0]
The answer is 3: each 0 alone, and [0, 0]. The second step finds total 0 twice in seen, the seed and the first total.
A negative target: nums = [3, -5, 1], k = -2
Nothing changes. At the second step sum is -2 and sum - k is 0, the seed, so [3, -5] is counted. The answer is 1.
The whole array sums to k
At the last step sum - k is 0, and the seed counts the subarray that starts at index 0.
Many answers: 100,000 zeros with k = 0
Every subarray counts, about 5 billion of them. That is above 32-bit limits but exact in a JavaScript number.

Variations and follow-ups

Twists interviewers add

Shortest subarray with sum k

Store the latest index where each total appeared, overwriting older ones. At each step, a match gives the shortest subarray ending here, because the latest start is the closest one.

Count submatrices with sum k

Fix a top row and a bottom row, add up each column between them into one array, and run this algorithm on that array. Over all row pairs that is O(rows² × cols).

Sum at most k instead of exactly k

A hash map only answers exact matches, so "at most" needs earlier totals kept in order. A sorted structure or a Fenwick tree over compressed totals counts how many earlier totals are at least sum - k, in O(n log n).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "number of subarrays with sum k", "contiguous", "divisible by k", or "equal numbers of 0s and 1s", especially when negatives are allowed.
  • Explain the rewrite first: "a subarray sum is the difference of two running totals, so I look for an earlier total equal to sum - k." Then explain the seed {0: 1}.
  • Test by hand: a subarray starting at index 0, k = 0 with zeros, and a negative number in the middle.
  • Expect "why not a sliding window?". Answer: with negatives, the window's sum doesn't move in one direction as it grows. Also expect "longest instead of count?": store the first index of each total and compare i - firstIndex.

Where frontend code uses it

The same idea in real UI code
  • Finding stretches in a metrics time series (sign-ups minus cancellations per day) whose net change is exactly some target.
  • Detecting balanced spans, such as a run of chat messages with as many sent as received, by treating one kind as +1 and the other as -1.
  • Checking whether a slice of transactions in a finance dashboard sums to an amount that has to be reconciled.

Related algorithms