DSA Pattern: Prefix Sum

Prefix sum is a technique for answering range-sum questions quickly.

Instead of adding the same values repeatedly, build a helper array where each position stores the sum of everything before it.

values:  3   2   5   1
prefix: 0   3   5  10  11

The sum from index left to right is:

prefix[right + 1] - prefix[left]

Implementation

function buildPrefix(values) {
	const prefix = [0];

	for (const value of values) {
		prefix.push(prefix[prefix.length - 1] + value);
	}

	return prefix;
}

function rangeSum(prefix, left, right) {
	return prefix[right + 1] - prefix[left];
}

When to use prefix sum

Use prefix sum when the problem asks many questions about ranges.

• sum from index i to index j
• count how many subarrays meet a condition
• compare left and right side sums
• find equilibrium indexes

Complexity

• Build prefix array: O(n)
• Range query: O(1)
• Extra space: O(n)

Practice problems

1. Range sum query.
2. Find pivot index.
3. Count subarrays with sum k.
4. Maximum score from taking cards from ends.
5. Find the difference between left and right sums.

Practice links

• LeetCode Prefix Sum problems
• NeetCode practice roadmap