Pattern 7 of 27

Prefix Sum

Precompute running totals so any subarray sum is one subtraction, and pair them with a hash map to count subarrays by their sum.

Cost: O(n) time, O(n) space
Problems: 6

When to reach for it

The prompt asks about sums of subarrays or ranges.
Negative numbers are allowed, which rules out a sliding window.
Many range queries arrive on an array that does not change.

How it works

If prefix[i] is the sum of the first i elements, then the sum from i to j is prefix[j + 1] minus prefix[i], so range queries cost O(1) after one pass. The stronger form turns "how many subarrays sum to k" into "how many earlier prefix sums equal the current running sum minus k", which a hash map of prefix counts answers during the same scan. Swapping the sum for its remainder handles divisibility questions in exactly the same way.

The template

Written for Subarray Sum Equals K (write-up)

def subarray_sum(nums, k):
    count = {0: 1}                    # prefix sum -> times seen
    running = total = 0
    for x in nums:
        running += x
        total += count.get(running - k, 0)
        count[running] = count.get(running, 0) + 1
    return total

Open in the editor Trace it line by line

Six problems, in learning order

1.Range Sum Query - ImmutableLeetCode 303Build the prefix array once; every query becomes a subtraction.Not in the curated 370 yet.Easy
2.Subarray Sum Equals KLeetCode 560Count earlier prefixes equal to the running sum minus k.Medium
3.Find Pivot IndexLeetCode 724The pivot is where the left sum equals the total minus the left sum minus the element.Not in the curated 370 yet.Easy
4.Binary Subarrays With SumLeetCode 930Binary values keep the map small; counting at most goal minus at most goal - 1 also works.Not in the curated 370 yet.Medium
5.Subarray Sums Divisible by KLeetCode 974Key the map by remainder mod k, normalised to be non-negative.Not in the curated 370 yet.Medium
6.Continuous Subarray SumLeetCode 523Store the first index of each remainder and require a gap of at least two.Not in the curated 370 yet.Medium

What usually goes wrong

Not seeding the map with a prefix sum of 0 seen once, which misses subarrays that start at index 0.
Negative remainders in languages where % can return a negative number.
Off-by-one mistakes between prefix[i] and the element at index i.

Prefix Sum, answered

When should I use the prefix sum pattern?

The prompt asks about sums of subarrays or ranges. Negative numbers are allowed, which rules out a sliding window. Many range queries arrive on an array that does not change.

What is the time complexity of prefix sum?

O(n) time, O(n) space. Swapping the sum for its remainder handles divisibility questions in exactly the same way.

Which problem should I start with for prefix sum?

Start with Range Sum Query - Immutable (LeetCode 303, Easy). Build the prefix array once; every query becomes a subtraction. The six problems on this page are in learning order.