Lesson 5 of 16 Arrays and Strings

Prefix Sum Pattern

Prefix sums for O(1) range queries, counting subarrays that sum to k with a hash map (negative numbers too), and product of array except self.

30-40 min intermediate 0/16 lessons done
Course contents Lesson 5 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. The idea
  4. Code
  5. Variants
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • Building prefix sums and answering range sums in O(1).
  • Combining prefix sums with a hash map to count subarrays.
  • Prefix and suffix passes for “everything except me” problems.

Signals

  • Many queries for the sum of a range.
  • “Number of subarrays whose sum equals k” (especially with negative numbers, where sliding window fails).
  • “Product/sum of all elements except index i” without division.

The idea

pre[i] is the sum of the first i elements, with pre[0] = 0. Then sum(nums[l..r]) = pre[r + 1] - pre[l]. The extra leading zero removes all edge cases at index 0.

For counting: a subarray ending at the current index sums to k exactly when some earlier prefix equals running - k. Count earlier prefixes in a dictionary.

Code

"""Prefix sums: O(1) range queries and counting subarrays with a hash map."""
from collections import defaultdict
from itertools import accumulate


class RangeSum:
    def __init__(self, nums):
        self.pre = [0, *accumulate(nums)]  # pre[i] = sum of nums[:i]

    def query(self, left, right):  # inclusive
        return self.pre[right + 1] - self.pre[left]


def count_subarrays_with_sum(nums, k):
    count, running = 0, 0
    seen = defaultdict(int)
    seen[0] = 1  # the empty prefix
    for x in nums:
        running += x
        count += seen[running - k]  # earlier prefixes that leave exactly k
        seen[running] += 1
    return count


def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out


if __name__ == "__main__":
    rs = RangeSum([3, -2, 5, 1, 6])
    print(rs.query(1, 3), rs.query(0, 4))
    print(count_subarrays_with_sum([1, 2, 3, -3, 1, 2], 3))
    print(product_except_self([1, 2, 3, 4]))

Output:

4 13
6
[24, 12, 8, 6]
  • query(1, 3) is -2 + 5 + 1 = 4.
  • seen[0] = 1 accounts for subarrays that start at index 0.
  • Product except self makes a left-to-right pass of running products, then multiplies in a right-to-left pass. O(n) time, O(1) extra space besides the output.

Variants

  • 2D prefix sums: pre[r][c] for sub-rectangle sums with inclusion-exclusion.
  • Difference arrays: add v to a range in O(1) by diff[l] += v; diff[r+1] -= v, then prefix-sum once.
  • Prefix XOR or prefix counts of parity work the same way as sums.
  • Longest subarray with sum k: store the first index of each prefix instead of counts.

Practise: prefix sum problems.

Key takeaways

  • pre[r + 1] - pre[l] gives any range sum in O(1) after O(n) setup.
  • Prefix sum + hash map counts subarrays with a given sum, negative numbers included.
  • Initialise the map with prefix 0 to count subarrays starting at index 0.
  • Prefix and suffix passes replace division in “except self” problems.

Exercises

  1. Implement a 2D RangeSum for sub-rectangle queries.
  2. Count subarrays whose sum is divisible by k (hint: store prefix mod k).
  3. Find the longest subarray with equal numbers of 0s and 1s (treat 0 as −1).

Quiz

  1. Why does pre have a leading 0?
  2. Why can’t the sliding window pattern count subarrays with sum k when numbers can be negative?
  3. What does a difference array speed up?
Show answers
  1. So a range starting at index 0 needs no special case: pre[r + 1] - pre[0].
  2. Window validity isn’t monotonic: adding a negative number can bring an oversized sum back to k, so shrinking decisions can be wrong.
  3. Many range updates: each update is O(1), and one prefix pass at the end applies them all.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).