Prefix Sums

Why start reading from chapter one every time you pick up a book, when you can just use a bookmark?

Imagine you're analyzing financial data and need to calculate the total revenue for hundreds of different time periods—this week, last month, the first quarter, etc. Calculating the sum for each period from scratch would be incredibly slow. How can we perform a single, quick pre-calculation that allows us to find the sum of any range almost instantly?

This problem is the purest definition of why the Prefix Sum pattern exists. Take 15-20 minutes to think about how you would build the NumArray class described in the problem.

Problem: Range Sum Query - Immutable LeetCode Link : You are asked to implement a class that, given an array nums, can quickly answer multiple queries about the sum of elements between two indices.

A naive implementation of the sumRange(left, right) function would be to loop from left to right and sum the elements, which would take $O(N)$ time for each query. If you have to answer many such queries, this becomes inefficient. The optimal approach is to use the Prefix Sum pattern.

You perform a single, upfront linear-time $O(N)$ computation to build a special "running total" array. Once this prefixSum array is ready, you can find the sum of any subarray in constant time $O(1)$.

How it works: You create a new array, let's call it prefixSum, where each prefixSum[i] stores the cumulative sum of all elements from the beginning of the original array up to index i-1.

So, for nums = [a, b, c, d], the prefixSum array would be [0, a, a+b, a+b+c, a+b+c+d].

The sum of any subarray from index l to r can then be computed as: Sum(nums[l...r]) = prefixSum[r+1] - prefixSum[l]

Note: (It is r + "one" and not r + "L", just saving you from confusion)

Walkthrough: Solving "Range Sum Query - Immutable"

Let's apply the pattern to our above problem. The solution is split into two phases:

1. The Constructor (Initialization Phase): This is where we do our one-time, $O(N)$ pre-computation.

   • We create a prefixSum array of size nums.length + 1.
   • We loop through the input nums from left to right.
   • For each element nums[i], we calculate the new running total and store it: prefixSum[i+1] = prefixSum[i] + nums[i].
   PythonJavaC++

   class NumArray:
       def __init__(self, nums):
           self.prefixSum = [0] * (len(nums) + 1)  # Initialize with an extra element for easier calculation
           for i in range(len(nums)):
               self.prefixSum[i + 1] = self.prefixSum[i] + nums[i]
   

   class NumArray {
       private int[] prefixSum;
       public NumArray(int[] nums) {
           prefixSum = new int[nums.length + 1]; // Initialize with an extra element
           for (int i = 0; i < nums.length; i++) {
               prefixSum[i + 1] = prefixSum[i] + nums[i];
           }
       }
   

   class NumArray {
       private:
           std::vector<int> prefixSum;
       public:
           NumArray(std::vector<int>& nums) {
               prefixSum.resize(nums.size() + 1, 0); // Initialize with an extra
               for (int i = 0; i < nums.size(); ++i) {
                   prefixSum[i + 1] = prefixSum[i] + nums[i];
               }
           }
   

2. The sumRange Function (Query Phase): This function now run in constant time.

   • It takes left and right indices as input.
   • It applies the formula directly, returning prefixSum[right + 1] - prefixSum[left].
   PythonJavaC++

   def sumRange(self, left: int, right: int) -> int:
       return self.prefixSum[right + 1] - self.prefixSum[left]
   

   public int sumRange(int left, int right) {
       return prefixSum[right + 1] - prefixSum[left];
   }
   

   int sumRange(int left, int right) {
       return prefixSum[right + 1] - prefixSum[left];
   }
   

Complexity Analysis

• Time Complexity:
  • Constructor: $O(N)$ for building the prefixSum array.
  • Query: $O(1)$ for each sumRange call.
• Space Complexity: $O(N)$ for storing the prefixSum array.

Bonus Point: Prefix sum in 2D is used for real-time image processing, where you can quickly compute the sum of pixel values in any rectangular region of an image!

More Problems & Variations

1. Subarray Sum Equals K LeetCode Link 💡 HintThe most important variation. Use a hash map to store the frequencies of prefix sums encountered so far. For each current_sum, you're looking for a previous_sum where current_sum - previous_sum = k.
2. Product of Array Except Self LeetCode Link 💡 HintTwo changes from our core example. Use multiplication instead of addition. Use a suffix sum in addition to prefix sum and then combine them, but the pattern remains the same.
3. Find Pivot Index LeetCode Link 💡 HintIf you have the total sum and the prefix sum up to an index i, how can you find the sum of the elements to the right of i in $O(1)$ time?
4. Range Sum Query 2D - Immutable LeetCode Link 💡 HintThe pattern extends to 2D! You precompute a sum matrix where sum[r][c] is the sum of the rectangle from (0,0) to (r,c). The sum of any sub-rectangle can then be found with four lookups.