Prefix Sum

In coding interviews, many array problems involve answering repeated range-based questions, such as computing sums or counts over subarrays. A straightforward solution often recomputes these values again and again, which quickly becomes inefficient as input sizes grow.

Prefix Sum solves this by shifting work to a preprocessing step. By building cumulative values once, you can answer range queries in constant time instead of looping repeatedly over the same elements. This approach turns brute-force logic into scalable solutions that perform well under interview constraints.

The trade-off is a small amount of extra memory in exchange for significantly better runtime performance.

What is the Prefix Sum pattern?

The Prefix Sum pattern is a technique where you precompute cumulative information about an array such that future calculations can be performed efficiently.

Instead of repeatedly summing elements over a range, you store a running total as you move through the array. Once this cumulative data is available, many range and subarray problems can be solved using simple arithmetic instead of loops.

Understanding Prefix Sum using a real-life example

Imagine you are tracking your score while playing a game, and after each round, you write down your score for that round along with the running total:

• In round 1, you scored 5 points. The running total is 5.
• In round 2, you scored 10 points. The running total becomes 15.
• In round 3, you scored 7 points. The running total becomes 22.
• In round 4, you scored 8 points. The running total becomes 30.
• In round 5, you scored 10 points. The running total becomes 40.

Each of these values represents the sum of everything you have scored up to that point, not just what happened in the most recent round.

Now, suppose someone asks how many points you scored between round 2 and round 5. If you only had individual scores, you would need to add them again:

$$\text{round} \space 3 + \text{round} \space 4 + \text{round} \space 5 = 7 + 8 + 10 = 25$$

But because you already have the running totals, you can answer instantly by subtracting the total after round $2$2 from the total after round 5: 40−15=25. This gives you the total points scored between those rounds without re-adding individual values.

This is exactly how the Prefix Sum pattern works. As you move through an array, you maintain a running sum of values. Once this running sum is available, any range or subarray sum can be computed using subtraction, eliminating the need for repeated calculations and nested loops.

In terms of Prefix Sum, this example maps directly as follows:

• Each running total corresponds to a prefix sum value.
• Subtracting two prefix sums gives the sum of the range between them.
• Reusing these precomputed values avoids repeated work and improves efficiency.

At its core, Prefix Sum is about keeping a running record so you can answer future questions quickly and cleanly without recalculating the same information again.

When should you think about using Prefix Sum

Prefix Sum is especially useful for problems that involve repeated calculations over parts of an array. These problems often feel slow or awkward when approached with brute force.

You should start thinking about Prefix Sum when you see questions involving range sums, subarrays, or repeated aggregation of values.

The key idea behind Prefix Sum is simple:

This shift, from repeated computation to reuse, is what unlocks major performance improvements.

Prefix Sum formula

There are two formulas that appear in nearly every prefix sum problem. To build the prefix sum array:

$$\text{prefix[i]} = \text{prefix[i − 1]} + \text{nums[i]}$$

To calculate the sum of a range from index $\text{left}$left to $\text{right}$right:

$$\text{rangeSum(left, right)} = \text{prefix[right]} − \text{prefix[left − 1]}$$

This subtraction works because $\text{prefix[right]}$ already includes everything before index $\text{left}$. Removing that extra portion leaves exactly the range you need.

Prefix Sum template (Range Queries)

Some coding problems involve answering multiple range-based questions, such as finding the sum of elements between two indices. Calculating these sums repeatedly leads to unnecessary recomputation and poor performance.

In such cases, Prefix Sum is used to precompute cumulative sums so range queries can be answered efficiently. By storing the running total of elements up to each index, the sum of any subarray can be obtained using simple subtraction instead of iterating over elements.

The core idea is that the prefix sum at index right already includes all values before index left. Subtracting the prefix sum just before left removes the extra portion and leaves exactly the desired range sum.

This approach is commonly used in problems such as “303. Range Sum Query – Immutable,” where preprocessing enables constant-time range queries.

# Build the prefix sum array where prefix[i] stores the sum of elements from 
# index 0 to i (inclusive)
prefix = [0] * len(nums)
prefix[0] = nums[0]

# Populate the prefix sum array using running totals
for i in range(1, len(nums)):
    prefix[i] = prefix[i - 1] + nums[i]

# Return the sum of elements in the range [left, right]
def rangeSum(left, right):
    # If the range starts at index 0, no subtraction is needed
    if left == 0:
        return prefix[right]

    # Subtract prefix sum before 'left' to isolate the range
    return prefix[right] - prefix[left - 1]

Prefix Sum with Hash Map

Some problems require more than simple range queries. In those cases, Prefix Sum is often combined with a hash map to efficiently track additional information while iterating through the array.

The core idea is to store how often each prefix sum has appeared so far. As you compute the running sum, you check whether a related prefix sum has been seen before. If it has, the elements in between form a subarray that satisfies the required condition. This allows you to count or detect valid subarrays in constant time per element.

For example, consider the classic “560. Subarray Sum Equals K” problem. Instead of checking every possible subarray, we track prefix sums and their frequencies as we move through the array:

nums = [1, 2, 3]
k = 3

prefixSum = 0          # Running sum of elements seen so far
countMap = { 0: 1 }    # Stores how many times each prefix sum has appeared
answer = 0             # Counts valid subarrays with sum equal to k

for each number in nums:
    prefixSum += number    # Update running sum

    # If we have seen (prefixSum - k) before, it means a subarray ending here sums to k
    if (prefixSum - k) exists in countMap:
        answer += countMap[prefixSum - k]

    # Record the current prefix sum in the map
    increment countMap[prefixSum]

Code explanation

As the loop runs (line 8), prefixSum represents the sum of all elements up to the current index. If prefixSum - k has appeared before (line 13), it means the elements between those two positions form a subarray whose sum is exactly $k$k. The hash map allows us to detect this relationship instantly, without nested loops.

This powerful variant frequently appears in problems such as:

• Subarray sum equals $k$k.
• Zero-sum subarrays.
• Balance problems involving +1 and −1 transformations.

Prefix Sum combined with hashing is one of the most important interview patterns to master.

Prefix Sum vs. Sliding Window

Prefix Sum is often confused with the Sliding Window pattern, but they serve different purposes.

Choosing the correct pattern can save both time and mistakes during interviews.

Common mistakes when using Prefix Sum

Prefix Sum is conceptually simple, but small implementation errors can lead to incorrect results. Some of the most common mistakes include:

1. Off-by-one indexing errors, especially when accessing prefix[left - 1] or handling the first element of the array.
2. Forgetting to initialize base cases, such as setting prefix[0] correctly or initializing a hash map with {0: 1} when counting subarrays.
3. Incorrect update order when using a hash map, such as updating the current prefix sum frequency before checking for a valid condition.
4. Misunderstanding inclusive and exclusive ranges, which can cause range sums to include or exclude unintended elements.
5. Overusing Prefix Sum in situations where a simpler approach (such as a single pass or Sliding Window) would be clearer and equally efficient.

Prefix Sum is a powerful pattern, but it should be applied deliberately and with careful attention to indexing, initialization, and problem constraints.