Skip to content

Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

Prefix sums as keys

Lesson · 12 min read · Arrays and hashing · Running totals as keys

A subarray is the difference of two prefixes. Store the prefixes in a map and every question about a range becomes a lookup.

Count subarrays that sum to k in one pass

A range is two prefixes

Write P[j] for the sum of the first j elements, with P[0] = 0. The sum of nums[i .. j − 1] is then P[j] − P[i], so if you're asked something about ranges that end at j, you can turn it into a question about prefixes we've already worked out. A range summing to k ends at j once for every earlier i with P[i] = P[j] − k.

So the keys in our map are prefix values, and what we keep under a key depends on what we've been asked to find. Here are the four versions I'd expect you to meet.

The question	Key	Store
how many ranges sum to k	P[i]	how many times it has occurred
the longest range summing to k	P[i]	the first index where it occurred, never overwritten
how many ranges have a sum divisible by m	P[i] mod m, made non-negative	a count
the longest range with equal 0s and 1s	the running total of +1 for 1 and −1 for 0	the first index

Counting ranges with sum k

We start the map off as {0: 1}, to stand for the empty prefix. Then at each element we look up P − k before we add P. The trace below runs on an array that's got a negative value in it, which is the case where a sliding window can't help you.

If you're asked for the longest range in place of the count, keep the first index you saw for a prefix and don't write over it, since an earlier start gives you a longer range. For the count, all of the earlier ones matter, so you keep how many of them there were.

Ranges summing to 7 in [3, 4, 7, 2, -3, 1, 4, 2].

Step 1 / 10

nums
30417223-34154627
prefix0total0k7
The map starts as {0: 1}, for the empty prefix. Without it, every subarray starting at index 0 is missed.
Step 2 / 10

nums
30j417223-34154627
prefix3want-4found0total0
Take 3: prefix = 3. Looking for an earlier prefix of -4: none, so nothing ends here. Total 0.
Step 3 / 10

nums
3041j7223-34154627
prefix7want0found1total1
Take 4: prefix = 7. Looking for an earlier prefix of 0: found 1, so 1 subarray ends here. Total 1.
Step 4 / 10

nums
304172j23-34154627
prefix14want7found1total2
Take 7: prefix = 14. Looking for an earlier prefix of 7: found 1, so 1 subarray ends here. Total 2.
Step 5 / 10

nums
30417223j-34154627
prefix16want9found0total2
Take 2: prefix = 16. Looking for an earlier prefix of 9: none, so nothing ends here. Total 2.
Step 6 / 10

nums
30417223-34j154627
prefix13want6found0total2
Take -3: prefix = 13. Looking for an earlier prefix of 6: none, so nothing ends here. Total 2.
Step 7 / 10

nums
30417223-3415j4627
prefix14want7found1total3
Take 1: prefix = 14. Looking for an earlier prefix of 7: found 1, so 1 subarray ends here. Total 3.
Step 8 / 10

nums
30417223-341546j27
prefix18want11found0total3
Take 4: prefix = 18. Looking for an earlier prefix of 11: none, so nothing ends here. Total 3.
Step 9 / 10

nums
30417223-34154627j
prefix20want13found1total4
Take 2: prefix = 20. Looking for an earlier prefix of 13: found 1, so 1 subarray ends here. Total 4.
Step 10 / 10

nums
30417223-34154627
total4
One pass, one map lookup per element. Answer 4.

Prefixes without a map

Sometimes the prefix is all we need, and there's nothing to look up. The product of all the elements apart from the one at i is the product of everything to its left times the product of everything to its right. A pass from the left fills in the first of those, and a pass from the right multiplies in the second. Since we never divide, a zero in the array won't cause us any trouble.

TimeO(n)

SpaceO(n) for the map; O(1) extra for the two product passes

The output array does not count as extra space in the usual statement of the product problem.

Problems in this module