Skip to main content

Prefix Sum

Premium

The prefix sum technique is a powerful pattern for solving problems involving ranges, subarrays, or cumulative values. It works by building an auxiliary array (prefix) or maintaining a running sum, where each element represents the sum of everything before it. With this pre-computation, you can answer range-sum queries in O(1) time instead of recalculating sums repeatedly.

When to use it

You can identify prefix-sum problems if they meet one or more of these conditions:

  • The problem involves subarrays, ranges, or cumulative values

  • You need to answer repeated “sum between i and j” queries efficiently

  • Brute-force nested loops would lead to O(n²), but prefix sums can reduce it to O(n)

Prefix sums can be extended beyond raw addition. You can use them for:

  • Counting frequencies

  • Counting number of subarrays with certain properties

  • Keeping track of cumulative XOR, products, or bitmasks

  • Range updates (with difference arrays)

How it works

We maintain a running sum while iterating through the array. At each step:

  • Add the current number to the running sum

  • Check if current_sum - k exists in the hashmap

    • If yes, that means a previous prefix leads to a subarray summing to k

  • Store/update the frequency of current_sum in the hashmap

Example: Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals k.

nums = [1, 2, 3] k = 3 prefix_count = {0: 1} # prefix sum → frequency current_sum = 0 count = 0 for num in nums: current_sum += num if current_sum - k in prefix_count: count += prefix_count[current_sum - k] prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1 print(count) # Output: 2

prefix sum

Here, current_sum keeps track of the cumulative sum as we iterate through the array. The hashmap prefix_count stores how many times each prefix sum has occurred. If current_sum - k is found in the map, it means a subarray ending at the current index sums to k. This lets us solve the problem in O(n) time instead of checking all possible subarrays.

Examples

  1. Range Sum Query (Static Array)
  • Problem: Given an array of numbers, efficiently answer multiple queries of the form: “What is the sum of elements between index i and j?”
  • Approach: Build a prefix-sum array where prefix[i] holds the sum of elements up to i. Then each query can be answered in O(1) using: range_sum(i, j) = prefix[j] - prefix[i-1].
  1. Maximum Subarray Sum (Kadane + Prefix Insight)
  • Problem: Find the maximum sum over all continuous subarrays.
  • Approach: Track a running prefix sum and maintain the minimum prefix seen so far. At each index, the difference between the current prefix and the smallest prefix before it gives a candidate max subarray sum.
Next Lesson