AlgoPatterns
Pattern RecognitionArticles
0/315
Back

Prefix Sum

Easy-Medium
Time: O(n) build, O(1) querySpace: O(n)
0/5
problems solved
0%
1.

What is Prefix Sum?

A prefix sum array stores cumulative sums, enabling O(1) range sum queries after O(n) preprocessing.

The Core Idea:

Original: [2, 4, 1, 3, 5]
Prefix: [0, 2, 6, 7, 10, 15]
^ ^ ^ ^ ^ ^
| | | | | sum of all
| | | | sum of first 4
| | | sum of first 3
| | sum of first 2
| sum of first 1
0 (empty sum)

Range Sum Formula:

sum(arr[i..j]) = prefix[j+1] - prefix[i]
Example: sum of arr[1..3] = [4, 1, 3] = 8
prefix[4] - prefix[1] = 10 - 2 = 8 ✓

Why prefix[0] = 0? It handles edge cases elegantly - sum from index 0 works without special handling.

▶ Interactive Prefix Sum

Prefix Sum Array

Build once O(n), query range sums in O(1)

Speed:
Original Array:
2[0]
4[1]
1[2]
3[3]
5[4]
Prefix Sum Array:
0[0]
?
0/5
Built
0/3
Queries
O(1)
Per Query
Click Play to build prefix sum array

Key Formula: sum(arr[i..j]) = prefix[j+1] - prefix[i]

2.

Building and Querying Prefix Sum

Two phases: Build once O(n), query many times O(1) each.

Building:

prefix[0] = 0 (base case)
prefix[i] = prefix[i-1] + arr[i-1] (accumulate)

Querying:

sum(i, j) = prefix[j+1] - prefix[i]

Why This Works:

  • •prefix[j+1] = sum of arr[0..j]
  • •prefix[i] = sum of arr[0..i-1]
  • •Subtracting removes the part we don't want

Common Pattern: When you see "multiple range queries on static array", think prefix sum.

Code
Java

▶ Interactive Prefix Sum

Prefix Sum Array

Build once O(n), query range sums in O(1)

Speed:
Original Array:
2[0]
4[1]
1[2]
3[3]
5[4]
Prefix Sum Array:
0[0]
?
0/5
Built
0/3
Queries
O(1)
Per Query
Click Play to build prefix sum array

Key Formula: sum(arr[i..j]) = prefix[j+1] - prefix[i]

3.

Subarray Sum Equals K (Prefix Sum + HashMap)

Count subarrays with sum exactly K. This is the most important prefix sum pattern.

Key Insight: If prefix[j] - prefix[i] = k, then subarray [i, j-1] has sum k.

Rearranging: prefix[i] = prefix[j] - k

So for each position j, we ask: "How many earlier prefix sums equal current_sum - k?"

Algorithm:

For each position:
1. Add current element to running sum
2. Check: How many times have we seen (sum - k)?
3. Add current sum to HashMap
Example: arr = [1, 2, 3], k = 3
Step 0: sum=0, map={0:1}
Step 1: sum=1, look for 1-3=-2 (not found), map={0:1, 1:1}
Step 2: sum=3, look for 3-3=0 (found 1!), count=1, map={0:1, 1:1, 3:1}
Step 3: sum=6, look for 6-3=3 (found 1!), count=2, map={0:1, 1:1, 3:1, 6:1}
Answer: 2 subarrays ([1,2] and [3])

Critical: Initialize map with {0: 1} to count subarrays starting at index 0.

Code
Java

▶ Interactive Subarray Sum K

Subarray Sum Equals K

Prefix Sum + HashMap: Look for complement (sum - k)

Speed:
Target sum k = 3
Array:
1[0]
2[1]
1[2]
1[3]
1[4]
Running Sum
0
Looking For
-
sum - k
Count
0
Prefix Sum Map (sum → count):
0: 1
Click Play to count subarrays with sum = 3

Key Insight: If prefix[j] - prefix[i] = k, then subarray [i+1, j] sums to k. So we look for (currentSum - k) in the HashMap.

4.

Contiguous Array (Binary Transformation Trick)

Find longest subarray with equal 0s and 1s. This seems different but uses prefix sum!

The Trick: Transform 0 → -1, then find longest subarray with sum 0.

Original: [0, 1, 0, 1, 1, 0]
Transform: [-1, 1, -1, 1, 1, -1]
Now: equal 0s and 1s → sum = 0

Why it works:

  • •Each 1 contributes +1
  • •Each 0 contributes -1
  • •Equal count ⟹ contributions cancel ⟹ sum = 0

Algorithm: Use prefix sum + HashMap to find longest subarray with sum 0.

prefix[j] - prefix[i] = 0
⟹ prefix[j] = prefix[i]
So we look for: "Earliest index with same prefix sum"
Code
Java
5.

Product of Array Except Self

Compute product of all elements except current, without division.

Why no division? Array might contain zeros!

Solution: Prefix AND Suffix products.

arr = [1, 2, 3, 4]
left = [1, 1, 2, 6] ← product of all elements to the LEFT
right = [24, 12, 4, 1] ← product of all elements to the RIGHT
result = [24, 12, 8, 6] ← left[i] * right[i]

Space Optimization: Build left products in result array, then multiply by right products in a single pass (O(1) extra space).

Code
Java

▶ Interactive Product Except Self

Product of Array Except Self

Two passes: Left products × Right products (no division needed)

Speed:
Pass 1: Left Products →
← Pass 2: Right Products
Original Array:
1[0]
2[1]
3[2]
4[3]
Result (Product Except Self):
?
?
?
?
Click Play to compute product except self

Key Insight: result[i] = (product of all left) × (product of all right). Build left products forward, then multiply by right products backward.

6.

Find Pivot Index

Find index where left sum equals right sum.

Approach: Use total sum.

leftSum = rightSum
leftSum = totalSum - leftSum - nums[pivot]
2 * leftSum = totalSum - nums[pivot]

So iterate and check: leftSum == totalSum - leftSum - nums[i]

Code
Java
7.

2D Prefix Sum (Matrix Region Queries)

Extend prefix sum to 2D for submatrix sum queries.

Building 2D Prefix:

prefix[i][j] = sum of all elements in submatrix (0,0) to (i-1,j-1)
prefix[i][j] = matrix[i-1][j-1]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1] (subtract double-counted)

Query Formula:

sum of region (r1,c1) to (r2,c2):
= prefix[r2+1][c2+1]
- prefix[r1][c2+1] (remove top)
- prefix[r2+1][c1] (remove left)
+ prefix[r1][c1] (add back corner, was removed twice)

Visualization:

+--------+--------+
| A | B |
+--------+--------+
| C | REGION |
+--------+--------+
REGION = Total - A - B - C + corner(A∩B∩C)
Code
Java
8.

Subarray Sum Divisible by K

Count subarrays whose sum is divisible by K. Uses modular arithmetic with prefix sums.

Key Insight: If prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0.

So we count prefix sums with the SAME remainder.

Visual Trace: nums = [4, 5, 0, -2, -3, 1], k = 5

prefix sums: [0, 4, 9, 9, 7, 4, 5]
remainders: [0, 4, 4, 4, 2, 4, 0]
Count same remainders:
- remainder 0: indices {0, 6} → C(2,2) = 1 subarray
- remainder 4: indices {1, 2, 3, 5} → C(4,2) = 6 subarrays
- remainder 2: indices {4} → C(1,2) = 0 subarrays
Total: 1 + 6 + 0 = 7 subarrays

Handling Negative Numbers: In some languages, -3 % 5 = -3 (not 2). Fix: ((sum % k) + k) % k

Code
Java

▶ Interactive Subarray Sum K

Subarray Sum Equals K

Prefix Sum + HashMap: Look for complement (sum - k)

Speed:
Target sum k = 3
Array:
1[0]
2[1]
1[2]
1[3]
1[4]
Running Sum
0
Looking For
-
sum - k
Count
0
Prefix Sum Map (sum → count):
0: 1
Click Play to count subarrays with sum = 3

Key Insight: If prefix[j] - prefix[i] = k, then subarray [i+1, j] sums to k. So we look for (currentSum - k) in the HashMap.

9.

Continuous Subarray Sum

Check if there's a subarray of length >= 2 with sum that's a multiple of k.

Different from Count Problem:

  • •Need length >= 2
  • •Just need existence (true/false), not count

Key Insight: Store the INDEX where each remainder was first seen. If we see the same remainder again AND the gap is >= 2, we found a valid subarray.

Visual Trace: nums = [23, 2, 4, 6, 7], k = 6

prefix sums: [0, 23, 25, 29, 35, 42]
remainders: [0, 5, 1, 5, 5, 0]
indices: [-1, 0, 1, 2, 3, 4]
At index 3: remainder 5, first seen at index 0
Gap = 3 - 0 = 3 >= 2 ✓
Subarray [23, 2, 4] sum = 29... wait that's not divisible by 6
Actually: prefix[4] - prefix[1] = 35 - 23 = 12, which IS divisible by 6
Subarray [2, 4, 6] = 12 ✓

Edge Case: k = 0 means we need subarray with sum exactly 0.

Code
Java

▶ Interactive Subarray Sum K

Subarray Sum Equals K

Prefix Sum + HashMap: Look for complement (sum - k)

Speed:
Target sum k = 3
Array:
1[0]
2[1]
1[2]
1[3]
1[4]
Running Sum
0
Looking For
-
sum - k
Count
0
Prefix Sum Map (sum → count):
0: 1
Click Play to count subarrays with sum = 3

Key Insight: If prefix[j] - prefix[i] = k, then subarray [i+1, j] sums to k. So we look for (currentSum - k) in the HashMap.

10.

Minimum Size Subarray Sum

Find the minimum length subarray with sum >= target. Combines prefix sum thinking with sliding window.

Two Approaches:

1. Sliding Window (O(n)) - Preferred Expand until sum >= target, then shrink while maintaining validity.

2. Prefix Sum + Binary Search (O(n log n)) For each end, binary search for smallest start where sum >= target.

Sliding Window Trace: nums = [2,3,1,2,4,3], target = 7

window [2]: sum=2 < 7
window [2,3]: sum=5 < 7
window [2,3,1]: sum=6 < 7
window [2,3,1,2]: sum=8 >= 7 → len=4
shrink: [3,1,2]: sum=6 < 7, stop
window [3,1,2,4]: sum=10 >= 7 → len=4
shrink: [1,2,4]: sum=7 >= 7 → len=3 ★
shrink: [2,4]: sum=6 < 7, stop
window [2,4,3]: sum=9 >= 7 → len=3
shrink: [4,3]: sum=7 >= 7 → len=2 ★★
shrink: [3]: sum=3 < 7, stop
Minimum length: 2
Code
Java

▶ Interactive Subarray Sum K

Subarray Sum Equals K

Prefix Sum + HashMap: Look for complement (sum - k)

Speed:
Target sum k = 3
Array:
1[0]
2[1]
1[2]
1[3]
1[4]
Running Sum
0
Looking For
-
sum - k
Count
0
Prefix Sum Map (sum → count):
0: 1
Click Play to count subarrays with sum = 3

Key Insight: If prefix[j] - prefix[i] = k, then subarray [i+1, j] sums to k. So we look for (currentSum - k) in the HashMap.

11.

Path Sum III: Prefix Sum in Trees

Count paths in a tree that sum to target. Prefix sum works on trees too!

Key Insight: As we traverse from root, maintain prefix sum. For each node, check how many earlier prefix sums equal (currentSum - target).

Tree Traversal with Prefix Sum:

10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
target = 8
Paths summing to 8:
- 5 → 3 (sum = 8)
- 5 → 2 → 1 (sum = 8)
- -3 → 11 (sum = 8)
Answer: 3 paths

The DFS Pattern:

  1. •Add current node to running sum
  2. •Check map for (sum - target) count
  3. •Add current sum to map
  4. •Recurse on children
  5. •BACKTRACK: Remove current sum from map (crucial!)
Code
Java
12.

Running Sum vs Prefix Array

Two ways to implement prefix sums - understand when to use which.

1. Prefix Array (Pre-built)

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// Query: sum(i, j) = prefix[j+1] - prefix[i]

Use when: Multiple queries on static array

2. Running Sum (On-the-fly)

int sum = 0;
for (int num : nums) {
sum += num;
// Use sum immediately
}

Use when: Single pass, updating result as you go

Comparison:

AspectPrefix ArrayRunning Sum
SpaceO(n)O(1)
Query timeO(1)N/A
Build timeO(n)N/A
Use caseRange queriesStream processing

Example Transformation:

// Prefix array approach:
int[] prefix = buildPrefix(nums);
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = prefix[j+1] - prefix[i];
}
}
// Running sum approach:
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
}
}
13.

Difference Array (Inverse of Prefix Sum)

Difference arrays are the inverse operation of prefix sums. They enable O(1) range updates.

The Relationship:

  • •Prefix sum: cumulative sums (query O(1), update O(n))
  • •Difference array: cumulative differences (update O(1), query O(n))

Building Difference Array:

arr = [1, 3, 6, 10, 15]
diff = [1, 2, 3, 4, 5]
diff[i] = arr[i] - arr[i-1]
prefix_sum(diff) = arr (they're inverses!)

Range Update with Difference Array: To add val to range [l, r]:

diff[l] += val
diff[r+1] -= val
Then prefix_sum(diff) gives the updated array

Example: Add 5 to range [1, 3]

arr = [0, 0, 0, 0, 0]
diff = [0, 0, 0, 0, 0]
Operation: add 5 to [1, 3]
diff[1] += 5 → [0, 5, 0, 0, 0]
diff[4] -= 5 → [0, 5, 0, 0, -5]
Prefix sum of diff: [0, 5, 5, 5, 0]
Result: arr = [0, 5, 5, 5, 0] ✓
Code
Java
14.

Common Mistakes and Tips

Mistake 1: Forgetting {0: 1} Initialization

// WRONG: Misses subarrays starting at index 0
Map<Integer, Integer> map = new HashMap<>();
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0); // Misses sum == k case!
map.merge(sum, 1, Integer::sum);
}
// CORRECT: Initialize with 0 → 1
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // CRITICAL!

Mistake 2: Off-by-One in Prefix Indexing

// WRONG: Confusing indices
int sum = prefix[j] - prefix[i]; // Sum of what range?
// CORRECT: Be explicit
// prefix[i] = sum of nums[0..i-1]
// Sum of nums[i..j] = prefix[j+1] - prefix[i]

Mistake 3: Negative Remainders

// WRONG in some languages
int rem = sum % k; // -3 % 5 = -3 (not 2)
// CORRECT: Handle negative
int rem = ((sum % k) + k) % k;

Mistake 4: Not Backtracking in Tree Problems

// WRONG: Prefix counts leak between branches
map.put(sum, map.get(sum) + 1);
recurse(left);
recurse(right);
// Forgot to remove!
// CORRECT: Backtrack after recursion
map.put(sum, map.get(sum) - 1);

Pro Tips:

  1. •prefix[0] = 0 handles "empty prefix" elegantly
  2. •For longest/shortest, store first occurrence index
  3. •For count, store occurrence count
  4. •Prefix sum + HashMap is a powerful combination
15.

Complexity Analysis

Time Complexity:

OperationBasic PrefixPrefix + HashMap
BuildO(n)O(n)
Range queryO(1)N/A
Count subarrays = kO(n²) naiveO(n)
Point updateO(n)O(n)

Space Complexity:

  • •Basic prefix array: O(n)
  • •Prefix + HashMap: O(n) for map
  • •Running sum: O(1)
  • •2D prefix: O(m × n)

When to Use What:

Multiple range sum queries on static array:
→ Build prefix array, O(1) queries
Count/find subarrays with sum = k:
→ Prefix sum + HashMap, O(n) time
Longest subarray with sum = 0:
→ HashMap storing first occurrence, O(n)
Range updates + single final query:
→ Difference array, O(1) updates
Both updates and queries:
→ Fenwick Tree or Segment Tree

2D Complexity:

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

Comparison with Alternatives:

Problem: Range sum queries
Brute force: O(n) per query
Prefix sum: O(1) per query, O(n) build
Segment tree: O(log n) per query/update
Fenwick tree: O(log n) per query/update
16.

Pattern Recognition Guide

Quick reference for prefix sum problems:

Problem TypeTechniqueKey Signal
Multiple range queriesBasic prefix sum"sum of range", "static array"
Count subarrays = KPrefix + HashMap"count subarrays", "sum equals"
Longest subarray = 0HashMap first occurrence"longest", "equal counts"
Equal 0s and 1sTransform + prefix"equal number of", "balanced"
Product except selfPrefix + suffix"product", "except current"
Pivot/equilibriumTotal sum trick"equal left and right"
Matrix region sum2D prefix"submatrix", "rectangle sum"
Divisible by KModular arithmetic"divisible", "remainder"
Range updatesDifference array"add to range", "multiple updates"
Tree path sumsDFS + prefix map"paths summing to", "tree"

Decision Tree:

Need range sums?
├── Static array → Prefix sum array
└── With updates → Fenwick/Segment tree
Counting subarrays?
├── Sum equals K → Prefix + HashMap (count)
├── Divisible by K → Prefix + HashMap (remainder)
└── Longest with sum K → Prefix + HashMap (first index)
Matrix problems?
├── Region sums → 2D prefix sum
└── Max rectangle → Combine with other techniques
Range updates?
└── Difference array + final prefix sum
17.

Template Summary

Template 1: Basic Prefix Sum Array

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// Query sum of nums[i..j]
int sum = prefix[j + 1] - prefix[i];

Template 2: Count Subarrays with Sum K

Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1); // CRITICAL
int sum = 0, result = 0;
for (int num : nums) {
sum += num;
result += count.getOrDefault(sum - k, 0);
count.merge(sum, 1, Integer::sum);
}

Template 3: Longest Subarray with Sum K

Map<Integer, Integer> firstIndex = new HashMap<>();
firstIndex.put(0, -1); // Sum 0 at index -1
int sum = 0, maxLen = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
if (firstIndex.containsKey(sum - k)) {
maxLen = Math.max(maxLen, i - firstIndex.get(sum - k));
}
firstIndex.putIfAbsent(sum, i); // Only first occurrence
}

Template 4: 2D Prefix Sum

// Build
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = matrix[i-1][j-1]
+ prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
}
}
// Query (r1,c1) to (r2,c2)
int sum = prefix[r2+1][c2+1] - prefix[r1][c2+1]
- prefix[r2+1][c1] + prefix[r1][c1];

Template 5: Difference Array (Range Updates)

int[] diff = new int[n + 1];
// Add val to range [l, r]
diff[l] += val;
diff[r + 1] -= val;
// Get final array
for (int i = 0; i < n; i++) {
result[i] = (i == 0) ? diff[0] : result[i-1] + diff[i];
}

Test Your Knowledge

Take a quick 15question quiz to test what you've learned.