Prefix Sum

How It Works

A prefix sum array stores the running total of all elements up to each index: prefix[i] = arr[0] + arr[1] + ... + arr[i]. Once built, the sum of any range [i, j] is just prefix[j] - prefix[i-1] — a single subtraction instead of a loop.

The pattern goes further when combined with a hash map. Instead of materializing the whole prefix array, you walk the array once while keeping a running sum, and store how many times each running sum value has been seen. To count subarrays that sum to k, you check at every index whether runningSum - k has been seen before — if prefix[j] - prefix[i] = k, then a subarray from i+1 to j sums to exactly k. This turns "count subarrays with sum k" from an O(n^2) brute force into a single O(n) pass.

The same running-total idea extends to problems that don't look like sums at first: "equal number of 0s and 1s" becomes a running sum where 0 contributes -1 and 1 contributes +1, and a subarray is balanced exactly when the running sum returns to a previously-seen value.

When To Use It

Reach for prefix sum when you see:

• Repeated queries for "sum of elements from index i to j" — precompute once, answer each query in O(1).
• "Count the number of subarrays that sum to k" or similar phrasing.
• A problem that can be reframed as a cumulative/balance count, like tracking a running difference between two categories of elements.
• "Product of everything except this index" style problems, which use the same left-to-right/right-to-left running accumulation idea, just with multiplication instead of addition.
• A brute-force solution that recomputes a range sum from scratch for every starting index.

Time & Space Complexity

• Time: O(n) to build the prefix sums (or running sum + hash map) and answer all queries; each individual range query afterward is O(1).
• Space: O(n) for the prefix array or the hash map of seen running sums.

Pattern Template

function subarraySum(nums, k) {
  const prefixCounts = new Map();
  prefixCounts.set(0, 1); // empty prefix sums to 0

  let runningSum = 0;
  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    runningSum += nums[i];

    // If (runningSum - k) has been seen, those subarrays sum to k
    if (prefixCounts.has(runningSum - k)) {
      count += prefixCounts.get(runningSum - k);
    }

    prefixCounts.set(runningSum, (prefixCounts.get(runningSum) || 0) + 1);
  }

  return count;
}

Alternative Approaches

• Brute force: for every pair of start/end indices, sum the range directly — O(n^2) time, O(1) space. Correct but too slow once inputs get large.
• Sliding window: works for range-sum problems only when all numbers are non-negative (since the window sum grows monotonically as you extend it). Prefix sum with a hash map handles negative numbers correctly, which sliding window cannot.
• Segment tree / Fenwick tree: needed when the underlying array is mutable (updates interleaved with range-sum queries). Plain prefix sums only work for static arrays; for that, a Binary Indexed Tree gives O(log n) updates and queries.

Common Mistakes

• Forgetting to seed the hash map with prefixCounts.set(0, 1) — without it, subarrays starting at index 0 are undercounted.
• Using prefix sum for range sums but rebuilding it from scratch after every mutation, when a Fenwick tree or recomputation strategy is actually needed for mutable arrays.
• Off-by-one errors when converting between "prefix sum up to and including index i" and "prefix sum up to index i-1" in range-sum formulas.
• Assuming sliding window is interchangeable with prefix sum — it isn't once negative numbers are involved.

Pattern Summary

Prefix sum trades O(n) extra space for turning repeated range-sum queries, or subarray-sum counting, into O(1) lookups after a single O(n) pass. It's the default tool whenever a problem's brute force is "recompute a range sum for every possible start/end pair."