Prefix Sum

Precompute cumulative sums to answer range queries in O(1).

7 problems 3 Easy 4 Medium 0 Hard

Overview

Prefix sum transforms expensive range queries into O(1) lookups by precomputing cumulative values. The same idea extends to 2D arrays and product arrays.

When to Use

Range sum queries
Subarray sum equals k
Number of subarrays with given sum
2D range sum queries
Product of array except self

Common Mistakes

Forgetting the +1 offset in the prefix array
Not handling negative numbers in subarray sum problems
Confusing prefix sum with sliding window for variable-size windows

Complexity

Time

O(n) build, O(1) per query

Space

O(n)

function buildPrefix(arr) {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix;
}

function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l]; // inclusive [l, r]
}

Problems (7)

Hide completed

Problem	Difficulty	Companies	Freq
Subarray Sum Equals K	Medium	FacebookGoogle +2	High
Product of Array Except Self	Medium	AmazonFacebook +2	High
Range Sum Query - Immutable	Easy	Amazon	Medium
Contiguous Array	Medium	Facebook	Medium
Find Pivot Index	Easy	AmazonGoogle	High
Running Sum of 1D Array	Easy	AmazonApple	Medium
Minimum Average Difference	Medium	Amazon	Low

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee