AlgoMaster Logo

Introduction to Prefix Sum

Ashish

Ashish Pratap Singh

Prefix Sum is a powerful problem solving pattern that can optimize the time complexity of many array-related problems from O(n²) to O(n).

In this chapter, you'll learn:

  • What a prefix sum is.
  • How to implement it in code.
  • When to use this pattern.

What is Prefix Sum?

In simple terms, a prefix sum for an array is the cumulative sum of elements from the start of the array to a given index.

In other words, each element in the prefix sum array at index i contains the sum of all elements from the start of the original array up to index i.

Here’s how to build the prefix sum:

  • Initialize a prefix_sum array with an extra space to handle zero-based indexing:prefix_sum = [0] * (len(nums) + 1)
  • Iterate through the input array and update the prefix sum array using this formula:prefix_sum[i + 1] = prefix_sum[i] + nums[i].

If the input array is:

0
2
1
4
2
6
3
8
4
10

The prefix sum array will look like this:

0
0
1
2
2
6
3
12
4
20
5
30

One thing to remember is that :

Sometimes, you don't even need a new array. You can modify the original array itself and use it as a prefix sum array if memory is a constraint.

When to Use the Prefix Sum Pattern?

Now that we know what a prefix sum is, let’s talk about when to use this pattern.

Here are a few common scenarios:

  1. Range Sum Queries: If you need to compute the sum of elements between two indices frequently, prefix sums help you do that in O(1) time.
  2. Subarray Problems: When solving problems that involve finding subarrays that meet certain conditions, like subarrays that add up to a specific number.
  3. Frequency Counting: If you need to count the number of subarrays or subsequences that satisfy specific conditions, prefix sums can help optimize your solution.

In short, if your problem involves frequent calculations of sums over ranges or conditions over subarrays, the Prefix Sum pattern is likely the way to go.

Prev:

Next: