pattern heroPT–23LeetCode Extension

Prefix sums

Work out running totals from the start once. Then the sum of any stretch is the difference of two ready numbers, and nothing has to be added up again.

Variant
P04 Prefix sumsSubarray sum · 1×

Example problem: count the subarrays of [2, -1, 1, 5, 2, 2, 3] that add up to 7.

numsprefix2-115223
not reached yetalready seencurrentearlier prefix equal to needsubarray with sum k

No subarrays found yet: count = 0

count = 0prefix = –seen = –x = –need = –
01/42
restart · back · play · step
Speed
1function countSubarrays(nums, k):
2 count = 0
3 prefix = 0
4 seen = map {0: 1} // missing keys: 0
5 for each x in nums:
6 prefix = prefix + x
7 need = prefix - k
8 if need in seen:
9 count = count + seen[need]
10 seen[prefix] = seen[prefix] + 1
11 return count

← → step · space play/pause

How to recognise

the sum of a contiguous range: how many subarrays sum to k, many questions about the sum from i to j, or negative numbers that break a sliding window.

How to solve problems like this

  1. Rewrite the sum of a range as the difference of two running sums.
  2. Decide what to remember about earlier prefixes: how often each appeared, its first index, or only that it appeared.
  3. Put the empty prefix, 0, in the map first, so ranges that start at index 0 count too.
  4. For each number: update the running sum, look up the prefix you need, then store the current one.

Variant: From both sides

The same, but build up from both sides: one pass from the left, one from the right. Use it when the answer at a position depends on everything to its left and everything to its right.

  1. Reach for it when the answer at i depends on everything before i and everything after i.
  2. Pass from the left and store, for each index, what lies before it: a product, a sum, a maximum.
  3. Pass from the right with one running value for what lies after it, and combine the two.
  4. The same two passes give the highest wall to the left and to the right of each spot when you count trapped rain water, and they settle a two-sided rule: hand out candies so that a higher rating beats both neighbours.

Where it's used

  • Face detection. The Viola–Jones detector, which ships with OpenCV, needs the brightness sum of many rectangles. It first builds a table of running sums, and then the sum of any rectangle takes four numbers from it.
  • Sorting on a GPU. Radix sort counts how many numbers fall into each bucket, and the running sums of those counts say where each bucket starts in the output. NVIDIA's CUB library sorts this way.
  • SQL. The window function SUM(...) OVER (ORDER BY ...) gives a running total: for each row, the sum of all rows up to it. Those are exactly the running sums.