Prefix Sum Technique on LeetCode for Beginners: From Intuition to Patterns

You see yet another LeetCode problem asking about subarray sums or ranges. The brute-force solution is obvious—but too slow.

Editorials often say:

“We can optimize this using a prefix sum array.”

Yet prefix sums can feel abstract if you’ve never seen them properly explained.

This guide breaks down the prefix sum technique on LeetCode for beginners: what it is, how to build it, how to use it for different patterns, and how to avoid common pitfalls.

TL;DR

• A prefix sum array stores cumulative sums so you can answer “sum of [L..R]” in O(1) after O(n) preprocessing.
• Many subarray problems (fixed-range queries, counts of subarrays with sum = K, etc.) become simpler and faster when reframed in terms of prefix sums.
• The core steps: build the prefix array, derive a formula like sum(L..R) = prefix[R+1] - prefix[L], and adapt it to the problem’s constraints (including negatives).
• Beginners often mis-index prefix arrays, forget the extra leading 0, or apply prefix sums where sliding window or hashing would be better.
• With a few templates, diagrams, and tools like AI-guided LeetCode practice, prefix sums can become one of your go-to techniques for array problems.

What Is a Prefix Sum, Intuitively?

Idea: Prepay the work of adding

Instead of recomputing sums for each query, you maintain a running total:

nums   = [2, 3, 5, 1]
prefix = [0, 2, 5, 10, 11]
          ^
          0 (empty sum)

• prefix[i] = sum of the first i elements (often nums[0..i-1]).
• prefix[0] is usually 0, representing the sum of an empty prefix.

Then:

sum of nums[L..R] = prefix[R+1] - prefix[L]

Example:

• Sum of nums[1..3] = 3 + 5 + 1 = 9.
• Using prefix: prefix[4] - prefix[1] = 11 - 2 = 9.

Why it’s powerful

Once you build prefix in O(n), you can:

• Answer range sum queries in O(1).
• Count subarrays with certain sums using hash maps over prefix sums.
• Reason about constraints like “subarray sum equals K” in a cleaner way.

Step-by-Step: Building and Using a Prefix Sum Array

1. Build the prefix array

function buildPrefix(nums: number[]): number[] {
  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;
}

Convention:

• prefix[0] = 0.
• prefix[i] = nums[0] + ... + nums[i-1].

2. Compute sum of a range `[L..R]`

function rangeSum(prefix: number[], L: number, R: number): number {
  return prefix[R + 1] - prefix[L];
}

Check with a small example to avoid off-by-one errors.

Pattern 1: Fast Range Sum Queries

Problem type: Given nums, answer many queries: “What is the sum of nums[L..R]?”

Naive approach: O(n) per query. With prefix sums: O(1) per query after O(n) preprocessing.

Visual

prefix[R+1] = sum(nums[0..R])
prefix[L]   = sum(nums[0..L-1])

prefix[R+1] - prefix[L] = sum(nums[L..R])

Code snippet

class NumArray {
  private prefix: number[];

  constructor(nums: number[]) {
    this.prefix = buildPrefix(nums);
  }

  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

This pattern shows up in many “range sum query” problems.

Pattern 2: Subarray Sum Equals K (Prefix + Hash Map)

Now, something more interesting.

Problem: Count the number of subarrays whose sum equals k. Values can be negative.

Why simple sliding window fails here

With negative numbers, the sum isn’t monotonic as you expand or shrink a window. Sliding window logic breaks down.

Prefix-sum formulation

Let:

• prefix[i] = sum of nums[0..i-1].
• Sum of nums[j..i-1] = prefix[i] - prefix[j].

We want:

prefix[i] - prefix[j] = k
→ prefix[j] = prefix[i] - k

So for each i, we count how many prior prefixes equal prefix[i] - k.

Code example (TypeScript)

function subarraySum(nums: number[], k: number): number {
  const countByPrefix = new Map<number, number>();
  countByPrefix.set(0, 1); // empty prefix

  let prefix = 0;
  let result = 0;

  for (const num of nums) {
    prefix += num;

    const needed = prefix - k;
    if (countByPrefix.has(needed)) {
      result += countByPrefix.get(needed)!;
    }

    countByPrefix.set(prefix, (countByPrefix.get(prefix) ?? 0) + 1);
  }

  return result;
}

This is a classic LeetCode pattern; tools like LeetCopilot can explain it with diagrams and execution traces so you see the prefix evolution over time.

Pattern 3: Prefix Sums in 2D (Matrices)

For grids/matrices, you can build a 2D prefix sum to answer rectangle sum queries quickly.

Idea

Let prefix[r+1][c+1] be the sum of all elements in the submatrix from (0,0) to (r,c) inclusive.

Then the sum of a rectangle (r1,c1) to (r2,c2) is:

prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1]

Diagrammatically:

Sum(rect) = A - B - C + D

This pattern appears in “range sum query 2D”–type problems and some advanced grid problems.

Practical Preparation Strategies

Strategy 1: Practice basic 1D prefix sums first

Master these before 2D:

• Build prefix arrays correctly.
• Answer “sum of [L..R]” queries.
• Translate simple constraints into prefix formulas.

Strategy 2: Keep a consistent indexing convention

Pick one:

• prefix[0] = 0, prefix[i] = sum of nums[0..i-1], or
• prefix[i] = sum of nums[0..i].

Then stick to it in your DSA learning path and notes. Inconsistent conventions cause off-by-one bugs.

Strategy 3: Combine prefix sums with hash maps deliberately

Whenever you see:

• “subarray sum equals K” with possible negatives, or
• “number of subarrays with property X based on sums”

Think: “Can I express this in terms of prefix sums and counts of previous prefixes?”

Common Mistakes to Avoid

Mistake 1: Forgetting the leading 0 in prefix

Without prefix[0] = 0, formulas like prefix[R+1] - prefix[L] break for L = 0.

Mistake 2: Mixing up indices

If you define prefix[i] one way but use a formula that assumes another, you’ll get off-by-one errors.

Fix: Always test your formula on a tiny array by hand.

Mistake 3: Using prefix sum where sliding window is simpler

For non-negative arrays and constraints like “sum < target” or “max subarray of size k,” sliding window is often simpler and avoids extra memory.

Mistake 4: Ignoring negative numbers

Sliding window usually fails with negative numbers in sum-based constraints; prefix sums + hash maps are more robust there.

FAQ

Q1: How do I know if prefix sums are appropriate?
Look for repeated sum queries over different ranges or counting subarrays based on sums (especially when values can be negative).

Q2: Is prefix sum always better than brute force?
Not always. For a single query on a small array, brute force is fine. Prefix sums shine when you have many queries or need to reason about sums algebraically.

Q3: How do prefix sums compare to sliding window?
Sliding window is great when sums are monotonic with expansion/shrinking (often non-negative arrays). Prefix sums are more general and work even with negative numbers.

Q4: How should I practice prefix sum problems?
Solve a cluster: range sum queries, subarray sum equals K, and at least one 2D variant. Use tools like AI-guided LeetCode practice to debug your off-by-one errors with visual traces.

Q5: Can prefix sums help with averages or other metrics?
Yes. Average of [L..R] is (prefix[R+1] - prefix[L]) / (R-L+1). Similar ideas apply to weighted sums or partial aggregates.

Conclusion

The prefix sum technique is a simple idea with huge leverage on LeetCode:

• Precompute cumulative sums once.
• Answer range questions and count patterns in O(1) per query.
• Work cleanly even when values are negative.

Once you internalize the indexing and a couple of core formulas, prefix sums become a natural tool you reach for whenever you see subarray sum constraints and repeated range queries.