Prefix Sum Pattern

Why this pattern matters for LeetCode

When you need the sum of elements from index i to j, the brute force adds them up each time — O(n) per query, O(n²) total across many queries. A prefix sum fixes this with one O(n) preprocessing pass that builds cumulative totals. After that, any range sum is a single subtraction: O(1). The same technique unlocks subarray problems — store prefix sums in a hash map as you build them and you can detect subarrays with a specific target sum without a nested loop.

What the Prefix Sum pattern is

A prefix sum array stores the running total at every position. prefix[i] holds the sum of all elements from index 0 through i-1. To get the sum of any range [left, right], compute prefix[right + 1] - prefix[left]. That subtraction works because prefix[right + 1] includes everything from index 0 to right, and prefix[left] includes everything from index 0 to left-1 — subtracting cancels everything before left, leaving exactly the range you want. One extra element (prefix[0] = 0) eliminates the need to special-case when left is 0.

Reach for Prefix Sum when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Prefix Sum

• ✓Answering multiple range sum queries on a fixed array efficiently
• ✓Detecting whether any subarray sums to a target (combine with a hash map of seen prefix sums)
• ✓Finding a pivot index where left and right sums are equal
• ✓Computing running totals or cumulative differences across a sequence

When NOT to use Prefix Sum

• ✕The array is modified between queries — the prefix sum becomes stale and you'd need to rebuild it
• ✕You only need a single range sum — just loop through it, no preprocessing needed
• ✕The problem involves non-contiguous elements — prefix sums are strictly for contiguous ranges
• ✕The window size is fixed and moves forward — Sliding Window is simpler and cleaner

Better alternative: In those cases, Sliding Window (for a fixed advancing window) or a Fenwick Tree (for arrays with frequent updates) is more appropriate.

JavaScript code template

Range Sum Query — O(n) to build, O(1) per query

function buildPrefixSum(nums) {
  const prefix = new Array(nums.length + 1).fill(0);

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

  return prefix;
}

// Sum of nums[left..right] inclusive
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

const nums = [1, 2, 3, 4, 5];
const prefix = buildPrefixSum(nums);
console.log(rangeSum(prefix, 1, 3)); // 2 + 3 + 4 = 9

The prefix array is one element longer than nums so prefix[0] = 0 acts as a base case with no special handling. prefix[i + 1] = prefix[i] + nums[i] builds the cumulative total at each step. For range [left, right]: prefix[right + 1] includes all elements up to and including right; prefix[left] includes all elements up to but not including left. Subtracting them gives exactly the slice you want.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create a prefix array of length nums.length + 1, filled with zeros.
2. 2Loop i from 0 to nums.length - 1: set prefix[i + 1] = prefix[i] + nums[i].
3. 3To query sum(left, right): return prefix[right + 1] - prefix[left].
4. 4For the subarray-sum-equals-target variant: initialize a Map with {0: 1}. As you walk through and accumulate currentSum, check if (currentSum - target) is already in the Map — that gap is a valid subarray. Add currentSum to the Map after each check.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Running Sum of 1d Array

  Build the prefix array directly — each output value is the cumulative total at that index.

  Coming soon
• Find Pivot Index

  Left sum at index i is prefix[i]; right sum is totalSum - prefix[i] - nums[i]. Find where they're equal.

  Coming soon
• Range Sum Query - Immutable

  Build the prefix array once, then answer every [left, right] query in O(1) with one subtraction.

  Coming soon
• Subarray Sum Equals K

  Store prefix sums in a Map as you walk the array. At each step, check if (currentSum - k) is already there — that gap is a valid subarray.

  Coming soon
• Product of Array Except Self

  Build prefix products left-to-right and suffix products right-to-left, then multiply them at each index.

  Coming soon

Common mistakes beginners make

• ✕Making the prefix array length n instead of n + 1 — without the extra slot, prefix[0] = 0 has nowhere to live and you need a special case every time left is 0.
• ✕Getting the range formula wrong: it's prefix[right + 1] - prefix[left], not prefix[right] - prefix[left - 1], which breaks when left is 0.
• ✕Rebuilding the prefix array inside the query loop — build it once, then reuse it for every query.
• ✕Reaching for a prefix sum when Sliding Window is simpler — if the window size is fixed and always moves forward, you don't need the full prefix array.

Prefix Sum vs Sliding Window

Choose the right tool for the job.

Time and space complexity

Building the prefix array visits each element once — O(n) time, O(n) space. Each range sum query is a single array lookup and subtraction — O(1). For the subarray-sum-equals-target variant, the hash map holds at most n + 1 entries — still O(n) space. The preprocessing cost is paid once; every subsequent query is constant time.

Frequently asked questions

Why does the prefix array need to be one element longer than nums?

The extra slot at index 0 (set to 0) represents the sum before any elements — the empty prefix. This lets the range formula prefix[right + 1] - prefix[left] work correctly when left is 0, without needing an 'if left is 0, return prefix[right + 1]' special case. Without it, your formula breaks at the left boundary.

How does combining a prefix sum with a hash map find subarrays with a target sum?

As you walk the array and accumulate currentSum, you ask: 'is there a previous position where the prefix sum was currentSum - target?' If yes, the subarray between that position and now sums to exactly target. A Map stores every prefix sum you've seen so far, so you can answer that question in O(1) at each step. The full scan is O(n).

How is Prefix Sum different from Sliding Window?

Sliding Window maintains a contiguous range that moves forward — you add what enters on the right and remove what leaves on the left. Prefix Sum builds a lookup table that answers any arbitrary [left, right] range in O(1). Use Sliding Window when the range advances predictably; use Prefix Sum when you need to jump to arbitrary positions or detect subarrays with a hash map.

When should I just loop instead of building a prefix sum?

When you only need a single range sum. Building the prefix array is O(n) overhead that only pays off across multiple queries. For one query on a fixed range, just loop — it's simpler and the same O(n) time. The prefix sum earns its cost when you query the same array many times, or when you're checking every possible subarray.