Prefix Sum Coding Pattern

Prefix Sum is a powerful and commonly used technique in algorithms that helps efficiently calculate the sum of elements in a subarray. Instead of recomputing sums again and again, we preprocess the array once and then answer range sum queries in constant time.

What is Prefix Sum?

A prefix sum is an auxiliary array where each element at index i stores the cumulative sum of elements from index 0 to i of the original array.

For example:

nums = [1, 2, 3, 4, 5]
prefix = [1, 3, 6, 10, 15]

This means:

prefix[0] = 1
prefix[1] = 1 + 2 = 3
prefix[2] = 1 + 2 + 3 = 6

Why Prefix Sum?

Prefix Sum helps with range queries, where we need to find the sum of elements between two indices multiple times.

Without prefix sum:

Each range sum calculation takes O(n) time

With prefix sum:

Each range sum calculation takes O(1) time after preprocessing

Building the Prefix Sum array O(n)

First, we build the prefix sum array only once.

function buildPrefixSum(nums) {
  let n = nums.length
  let prefix = new Array(n)
  prefix[0] = nums[0]

  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] + nums[i]
  }

  return prefix
}

Explanation

Each element in prefix stores the sum of all elements before it
We traverse the array once
Time complexity: O(n) because we iterate through the array one time

This preprocessing step is done only once.

Getting Range Sum in Constant Time O(1)

Once the prefix sum array is built, we can answer any range sum query instantly.

function getSum(prefix, left, right) {
  if (left !== 0) {
    return prefix[right] - prefix[left - 1]
  }
  return prefix[right]
}

How the formula works

prefix[right] gives the sum from index 0 to right
Subtracting prefix[left - 1] removes the sum before left

nums = [1, 2, 3, 4, 5]
prefix = [1, 3, 6, 10, 15]

getSum(prefix, 1, 3)
= prefix[3] - prefix[0]
= 10 - 1
= 9

Time complexity: O(1) because it performs only constant time operations

Complete code:

function buildPrefixSum(nums) {
  let n = nums.length
  let prefix = new Array(n)
  prefix[0] = nums[0]

  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] + nums[i]
  }

  return prefix
}

function getSum(prefix, left, right) {
  if (left !== 0) {
    return prefix[right] - prefix[left - 1]
  }
  return prefix[right]
}

let nums = [1, 2, 3, 4, 5]
let prefix = buildPrefixSum(nums)

console.log(getSum(prefix, 1, 3)) // 2 + 3 + 4 = 9

Common Use Cases of Prefix Sum

Precompute prefix sums and answer queries efficiently.
Use prefix sums with a HashMap to count subarrays in O(n) time.
Convert 0 to -1 and use prefix sums to find balanced subarrays.
Track prefix sums modulo k to find valid subarrays.

Conclusion

Prefix Sum is a simple yet powerful pattern:

It reduces repeated work
Improves performance significantly
Forms the foundation for many advanced problems

Mastering Prefix Sum will make many array problems easier and faster to solve