Prefix Sum Complete Guide - Master Range Queries in O(1) Time

Overview

Prefix sum is one of the most powerful yet simple optimization techniques in algorithm interviews. It transforms O(n) range sum queries into O(1) operations, making it essential for:

• Range sum queries
• Subarray sum problems
• Contiguous array problems
• 2D matrix sum queries

Why interviewers love it: Tests your ability to use preprocessing and space-time tradeoffs to optimize brute force solutions.

---

Core Concept: Cumulative Sum

The key insight: precompute cumulative sums so any range sum becomes a simple subtraction.

What is Prefix Sum?

Given array nums, the prefix sum array prefix where:

$$\text{prefix}[i] = \sum_{j=0}^{i-1} \text{nums}[j]$$

In plain English:

• prefix[0] = 0 (sum of zero elements)
• prefix[1] = nums[0]
• prefix[2] = nums[0] + nums[1]
• prefix[i] = sum of first i elements

Visual Intuition

Original:  [2,  4,  -1,  5,  3]
Index:      0   1    2   3   4

Prefix:    [0,  2,  6,  5, 10, 13]
Index:      0   1   2   3   4   5
            ↑
         base case

Each prefix[i] stores the sum of all elements before index i.

The Magic Formula

To get sum of range [left, right]:

$$\text{sum}[\text{left}, \text{right}] = \text{prefix}[\text{right} + 1] - \text{prefix}[\text{left}]$$

Why?

prefix[right + 1] = nums[0] + nums[1] + ... + nums[right]
prefix[left]      = nums[0] + nums[1] + ... + nums[left-1]
                    ────────────────────────────
Subtract:           nums[left] + ... + nums[right]  ✓

---

Building Prefix Sum Array

💡 Algorithm

1. Create array of size n + 1 (one extra for base case)
2. Set prefix[0] = 0
3. For each index i, compute prefix[i + 1] = prefix[i] + nums[i]

🎮 Interactive Visualization

Watch how prefix sum array is built step by step.

💻 Template Code

JavaScriptJavaPython

Loading...

✅ Key Points

• Size: Prefix array has n + 1 elements (one more than original)
• Base case: prefix[0] = 0 represents empty prefix
• Recurrence: prefix[i + 1] = prefix[i] + nums[i]
• Time: O(n) to build
• Space: O(n) extra space

---

Range Sum Query in O(1)

Once prefix sum is built, any range query takes constant time!

💡 Formula

sum[left, right] = prefix[right + 1] - prefix[left]

🎮 Interactive Visualization

See how range sum is computed using prefix sum.

💻 Template Code

JavaScriptJavaPython

Loading...

📊 Example Walkthrough

nums = [2, 4, -1, 5, 3]
prefix = [0, 2, 6, 5, 10, 13]

Query: sum of [1, 3]
─────────────────────
sum[1, 3] = prefix[4] - prefix[1]
          = 10 - 2
          = 8

Verify: nums[1] + nums[2] + nums[3]
      = 4 + (-1) + 5
      = 8 ✓

Why prefix[4] not prefix[3]?

Because prefix[i] represents sum up to but not including index i.

• prefix[4] = sum of indices [0, 3]
• prefix[1] = sum of indices [0, 0]
• Difference = sum of indices [1, 3] ✓

---

The Subarray Sum Pattern

The most powerful prefix sum application: finding subarrays with specific sum.

Core Insight

For subarray [i, j] to have sum k:

$$\text{prefix}[j + 1] - \text{prefix}[i] = k$$

Rearrange:

$$\text{prefix}[i] = \text{prefix}[j + 1] - k$$

Key idea: As we iterate, check if (currentSum - k) exists in our history!

The HashMap Trick

Use a HashMap to store:

• Key: prefix sum value
• Value: count (or index) of occurrences

🎮 Interactive Visualization

Watch how we find subarrays with target sum using HashMap.

Template Pattern

function subarraySum(nums, target) {
  const map = new Map();
  map.set(0, 1);  // Base case: empty prefix
  
  let count = 0;
  let sum = 0;
  
  for (const num of nums) {
    sum += num;
    
    // Check if (sum - target) exists
    if (map.has(sum - target)) {
      count += map.get(sum - target);
    }
    
    // Add current sum to map
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  
  return count;
}

Why This Works

At each position j, we know:
  - Current prefix sum = sum
  - We want subarray with sum = k
  - Need: prefix[i] = sum - k
  
If (sum - k) exists in map:
  → We found subarray(s) from some i to j with sum k!

---

Interview Problems

Problem 1: Range Sum Query - Immutable (LC 303)

Problem: Design a data structure to compute range sums efficiently.

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) → 1  ((-2) + 0 + 3)
sumRange(2, 5) → -1 (3 + (-5) + 2 + (-1))
sumRange(0, 5) → -3 (all elements)

Solution: Classic prefix sum application!

JavaScriptJavaPython

Loading...

Complexity:

• Constructor: O(n) time, O(n) space
• sumRange: O(1) time

Interview Tip: This is the baseline problem. Master this first!

---

Problem 2: Subarray Sum Equals K (LC 560)

Problem: Count number of continuous subarrays with sum equal to k.

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: Subarrays [1, 2] and [3]

Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: Subarrays [1, 1] (twice)

Key Insight: Use HashMap to track prefix sum frequencies.

JavaScriptJavaPython

Loading...

Complexity: O(n) time, O(n) space

Step-by-Step Example

nums = [1, 2, 3], k = 3
map = {0: 1}  (base case)

i=0, num=1:
  sum = 1
  complement = 1 - 3 = -2 (not in map)
  map = {0: 1, 1: 1}
  count = 0

i=1, num=2:
  sum = 3
  complement = 3 - 3 = 0 (found in map!)
  count += map[0] = 1
  map = {0: 1, 1: 1, 3: 1}
  count = 1

i=2, num=3:
  sum = 6
  complement = 6 - 3 = 3 (found in map!)
  count += map[3] = 1
  map = {0: 1, 1: 1, 3: 1, 6: 1}
  count = 2

Return 2 ✓

Common Mistake: Forgetting map.set(0, 1) base case!

---

Problem 3: Contiguous Array (LC 525)

Problem: Find longest subarray with equal number of 0s and 1s.

Input: nums = [0, 1, 0]
Output: 2
Explanation: [0, 1] or [1, 0]

Input: nums = [0, 1, 1, 0, 1, 1, 1, 0]
Output: 4
Explanation: [1, 0, 1, 1] or [0, 1, 1, 0]

Key Insight: Transform problem!

• Replace 0 with -1
• Problem becomes: find longest subarray with sum = 0

JavaScriptJavaPython

Loading...

Complexity: O(n) time, O(n) space

Why This Works

Original: [0, 1, 0, 1, 1, 0]
Transform: [-1, 1, -1, 1, 1, -1]
Prefix:   [0, -1, 0, -1, 0, 1, 0]
               ↑       ↑
            same value!

When prefix sum repeats:
  → sum of elements between them = 0
  → equal number of -1s and 1s
  → equal number of 0s and 1s in original ✓

Interview Tip: Transform to simpler problem is a key skill!

---

Problem 4: Subarray Sums Divisible by K (LC 974)

Problem: Count subarrays with sum divisible by k.

Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7

Key Insight: Use modulo arithmetic!

If two prefix sums have same remainder when divided by k:

• Their difference is divisible by k
• The subarray between them has sum divisible by k!

JavaScriptJavaPython

Loading...

Complexity: O(n) time, O(k) space

Why Modulo Works

prefix[i] % k = r
prefix[j] % k = r  (same remainder)

Then:
  (prefix[j] - prefix[i]) % k = 0
  → sum[i+1, j] is divisible by k ✓

Critical Detail: Handle negative modulo!

let mod = sum % k;
if (mod < 0) mod += k;  // Make it positive

In Java/JavaScript, -7 % 5 = -2, but we want 3.

---

Problem 5: Count Subarrays With More Ones Than Zeros (LC 2031) 🔒

Note: This is a LeetCode Premium problem. You need a subscription to submit on the platform.

Problem: Given a binary array, count the number of non-empty subarrays with more 1s than 0s.

Input: nums = [0, 1, 1, 0, 1]
Output: 9

Input: nums = [1, 1, 1]
Output: 6 (all 6 non-empty subarrays)

Core Insight: This is a brilliant problem that combines prefix sum with a clever O(n) observation!

Step 1: Transform the Problem

1. Transform: 0 → -1, 1 → 1
2. Problem becomes: Count subarrays with sum > 0
3. Key relationship: Subarray [i, j] has sum > 0 ⟺ prefixSum[j] > prefixSum[i-1]

For each position j, we need to count how many i exist where prefixSum[i-1] < prefixSum[j].

Step 2: The O(n) Breakthrough! 💡

Why O(n) is possible?

After transformation, array only contains 1 and -1, so:

• Each prefix sum changes by exactly +1 or -1
• We can dynamically maintain the count of smaller prefix sums!

Key Variables:

• currSum: Current prefix sum
• ltCurrSum: Count of prefix sums less than currSum
• sumCount: Frequency of each prefix sum value

Algorithm Logic

When we see 0 (becomes -1):

Old currSum: 5
After -1: currSum = 4

Before: ltCurrSum counted all prefix sums < 5
Now: Some prefix sums = 4 are no longer < currSum
→ Subtract count of prefix sums = 4

When we see 1:

Old currSum: 5
After +1: currSum = 6

Before: ltCurrSum counted all prefix sums < 5
Now: All prefix sums < 5 are still < 6
     AND prefix sums = 5 are now < 6 too!
→ Add count of prefix sums = 5

JavaScriptJavaPython

Loading...

Complexity: O(n) time, O(n) space — Much better than O(n log n) BIT solution!

Detailed Example

nums = [0, 1, 1, 0, 1]
Transform: [-1, 1, 1, -1, 1]

Initialize:
  sumCount = {0: 1}  (base case)
  currSum = 0
  ltCurrSum = 0
  result = 0

Position 0 (num=0 → -1):
  currSum: 0 → -1
  ltCurrSum -= sumCount[-1] = 0 - 0 = 0
  sumCount = {0: 1, -1: 1}
  result += 0 → result = 0

Position 1 (num=1):
  ltCurrSum += sumCount[-1] = 0 + 1 = 1
  currSum: -1 → 0
  sumCount = {0: 2, -1: 1}
  result += 1 → result = 1
  (Found subarray [1])

Position 2 (num=1):
  ltCurrSum += sumCount[0] = 1 + 2 = 3
  currSum: 0 → 1
  sumCount = {0: 2, -1: 1, 1: 1}
  result += 3 → result = 4
  (Found subarrays [1,1], [0,1,1], [1,1] from start)

Position 3 (num=0 → -1):
  currSum: 1 → 0
  ltCurrSum -= sumCount[0] = 3 - 2 = 1
  sumCount = {0: 3, -1: 1, 1: 1}
  result += 1 → result = 5

Position 4 (num=1):
  ltCurrSum += sumCount[0] = 1 + 3 = 4
  currSum: 0 → 1
  sumCount = {0: 3, -1: 1, 1: 2}
  result += 4 → result = 9

Return 9 ✓

Why This Works: The Increment Property

Critical observation: After 0 → -1 transformation:

• Prefix sum only changes by ±1 each step
• Moving from currSum to currSum+1 or currSum-1
• We can incrementally update ltCurrSum!

Visual Understanding:

Prefix sums seen: [-1, 0, 0, 1]
At currSum = 1:
  ltCurrSum = 3 (three prefix sums < 1)

Next num = 1, currSum becomes 2:
  Old < 1: still < 2 ✓
  Old = 1: now < 2 ✓
  → ltCurrSum += count(1)

Next num = -1, currSum becomes 0:
  Old < 1: some are = 0, no longer < currSum
  → ltCurrSum -= count(0)

Comparison with O(n log n) Solutions

Approach	Time	Space	Difficulty
This O(n) solution	O(n)	O(n)	Medium (clever!)
Binary Indexed Tree	O(n log n)	O(n)	Hard
Merge Sort	O(n log n)	O(n)	Hard

Interview Tip: Start with the O(n log n) BIT solution, then mention the O(n) optimization if time permits!

Common Mistakes

❌ Wrong: Forgetting to subtract when currSum decreases

if (num === 0) {
  currSum--;
  // Missing: ltCurrSum -= sumCount.get(currSum) || 0;
}

❌ Wrong: Updating sumCount before using ltCurrSum

sumCount.set(currSum, ...);  // Too early!
result += ltCurrSum;  // ltCurrSum needs old state

✅ Correct: Update ltCurrSum, then update sumCount, then add to result

---

2D Prefix Sum (Bonus)

Extend prefix sum to 2D matrices for O(1) rectangle sum queries!

Problem 6: Range Sum Query 2D (LC 304)

Problem: Compute sum of elements in any sub-rectangle efficiently.

Matrix:
[3, 0, 1, 4, 2]
[5, 6, 3, 2, 1]
[1, 2, 0, 1, 5]
[4, 1, 0, 1, 7]
[1, 0, 3, 0, 5]

sumRegion(2, 1, 4, 3) = 8

2D Prefix Sum Formula

$$\text{prefix}[i][j] = \text{matrix}[i-1][j-1] + \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1]$$

Visualization:

To compute prefix[i][j], we need:
  
  ┌─────┬───┐
  │  A  │ B │  A = prefix[i-1][j-1]
  ├─────┼───┤  B = prefix[i-1][j]
  │  C  │ X │  C = prefix[i][j-1]
  └─────┴───┘  X = matrix[i-1][j-1]

prefix[i][j] = B + C - A + X

Why subtract A? It’s counted twice in B and C!

Query Formula

$$\text{sum} = \text{prefix}[r2+1][c2+1] - \text{prefix}[r1][c2+1] - \text{prefix}[r2+1][c1] + \text{prefix}[r1][c1]$$

JavaScriptJavaPython

Loading...

Complexity:

• Build: O(m × n)
• Query: O(1)

---

Common Patterns & Variations

Pattern 1: Count Subarrays

Template:

const map = new Map();
map.set(0, 1);  // Always start with base case!
let count = 0, sum = 0;

for (const num of nums) {
  sum += num;
  const complement = sum - target;
  if (map.has(complement)) count += map.get(complement);
  map.set(sum, (map.get(sum) || 0) + 1);
}

Examples:

• LC 560: Subarray Sum Equals K
• LC 974: Subarray Sums Divisible by K
• LC 1074: Number of Submatrices That Sum to Target

---

Pattern 2: Find Longest/Shortest Subarray

Template:

const map = new Map();
map.set(0, -1);  // Store index, not count!
let maxLen = 0, sum = 0;

for (let i = 0; i < nums.length; i++) {
  sum += transform(nums[i]);  // Transform if needed
  
  if (map.has(sum - target)) {
    maxLen = Math.max(maxLen, i - map.get(sum - target));
  }
  
  if (!map.has(sum)) {  // Only store first occurrence
    map.set(sum, i);
  }
}

Examples:

• LC 525: Contiguous Array
• LC 325: Maximum Size Subarray Sum Equals k
• LC 1124: Longest Well-Performing Interval

---

Pattern 3: Transformation Tricks

Problem Type	Transform	Target
Equal 0s and 1s	0 → -1, 1 → 1	sum = 0
Equal vowels/consonants	vowel → 1, consonant → -1	sum = 0
More 1s than 0s	1 → 1, 0 → -1	sum > 0
Even/odd frequency	even → 0, odd → 1	XOR-based

---

Common Pitfalls

1. Forgetting Base Case

❌ Wrong:

const map = new Map();
// Missing base case!

✅ Correct:

const map = new Map();
map.set(0, 1);  // For count problems
// OR
map.set(0, -1);  // For length problems

Why: To handle subarrays starting from index 0!

---

2. Off-by-One in Range Query

❌ Wrong:

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

✅ Correct:

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

Remember: prefix[i] = sum of first i elements (not including index i).

---

3. Negative Modulo

❌ Wrong (in JavaScript/Java):

let mod = sum % k;  // Can be negative!
map.set(mod, ...);

✅ Correct:

let mod = sum % k;
if (mod < 0) mod += k;  // Make positive
map.set(mod, ...);

Example: -7 % 5 = -2 in JS, but we want 3.

---

4. Wrong Map Value for Length Problems

❌ Wrong:

map.set(sum, (map.get(sum) || 0) + 1);  // Storing count!

✅ Correct (for length problems):

if (!map.has(sum)) {  // Only first occurrence
  map.set(sum, i);  // Store index!
}

Why: For longest subarray, we want the earliest occurrence of each sum.

---

5. Integer Overflow

For very large arrays, prefix sum can overflow. Use long in Java or BigInt in JavaScript if needed.

// Java - use long
long[] prefix = new long[n + 1];

---

Summary

🔑 The Core Idea

Prefix sum trades O(n) preprocessing for O(1) queries.

Build once, query many times!

📋 Quick Reference

Operation	Time	Space
Build prefix sum	O(n)	O(n)
Range sum query	O(1)	-
Subarray sum (HashMap)	O(n)	O(n)
2D build	O(m×n)	O(m×n)
2D query	O(1)	-

🎯 Pattern Recognition

Use prefix sum when you see:

• “subarray sum equals k”
• “continuous array”
• “sum of range [i, j]”
• Multiple queries on same array
• “longest/shortest subarray with sum…”

Add HashMap when:

• Finding subarrays with specific sum
• Counting occurrences
• Need to track history of sums

💡 Key Takeaways

1. Base case matters: Always initialize map.set(0, ...)
2. Index vs Count: Store index for length, count for frequency
3. Transform cleverly: Turn hard problems into sum = 0
4. Handle negatives: Modulo can be negative in some languages
5. Think cumulative: Prefix sum is just cumulative addition

🚀 Pro Tips for Interviews

1. Start simple: Implement basic prefix sum first, then optimize
2. Draw it out: Sketch the array and prefix values
3. Explain the math: Walk through prefix[r+1] - prefix[l]
4. Consider space: Can you build prefix sum on-the-fly?
5. Test edge cases: Empty array, all negatives, single element

🎯 Interview Template: When you see “subarray sum”, immediately think:

1. Can I use prefix sum?
2. Do I need a HashMap?
3. What’s my base case?
4. Am I finding count, length, or indices?

📚 Related Topics

• Sliding Window: For subarray problems without prefix sum
• Binary Search on Prefix Sum: For problems like “find minimum length”
• Difference Array: Inverse operation for range updates
• Segment Tree: When array is mutable and we need range queries

Master prefix sum, and you’ll crush a whole category of interview problems! 🚀