Prefix Sum Array in DSA Javascript

Mental Model

A prefix sum array stores sums of all elements up to each position, so you can quickly find the sum of any part of the original array.

Analogy: Imagine a row of buckets where each bucket holds the total amount of water collected from the first bucket up to that bucket. To find how much water is between two buckets, you just subtract the amounts in those buckets.

Original array:  [2] -> [4] -> [6] -> [8] -> [10]
Prefix sums:     [2] -> [6] -> [12] -> [20] -> [30]

Dry Run Walkthrough

Input: array: [2, 4, 6, 8, 10]

Goal: Create a prefix sum array to quickly find sums of any subarray

Step 1: Start prefix sum array with first element same as original

Prefix sums: [2] -> null

Why: The first prefix sum is just the first element itself

Step 2: Add second element to previous prefix sum: 2 + 4 = 6

Prefix sums: [2] -> [6] -> null

Why: Each prefix sum includes all elements before it

Step 3: Add third element to previous prefix sum: 6 + 6 = 12

Prefix sums: [2] -> [6] -> [12] -> null

Why: Keep accumulating sums to build prefix array

Step 4: Add fourth element to previous prefix sum: 12 + 8 = 20

Prefix sums: [2] -> [6] -> [12] -> [20] -> null

Why: Continue adding to get running totals

Step 5: Add fifth element to previous prefix sum: 20 + 10 = 30

Prefix sums: [2] -> [6] -> [12] -> [20] -> [30] -> null

Why: Final prefix sum includes all elements

Result:

Prefix sums: [2] -> [6] -> [12] -> [20] -> [30] -> null

Annotated Code

DSA Javascript

class PrefixSum {
  constructor(arr) {
    this.arr = arr;
    this.prefixSums = [];
    this.buildPrefixSums();
  }

  buildPrefixSums() {
    if (this.arr.length === 0) return;
    this.prefixSums[0] = this.arr[0]; // start with first element
    for (let i = 1; i < this.arr.length; i++) {
      this.prefixSums[i] = this.prefixSums[i - 1] + this.arr[i]; // add current element to previous sum
    }
  }

  getSum(start, end) {
    if (start < 0 || end >= this.arr.length || start > end) return 0;
    if (start === 0) return this.prefixSums[end]; // sum from start
    return this.prefixSums[end] - this.prefixSums[start - 1]; // subtract to get subarray sum
  }
}

// Driver code
const arr = [2, 4, 6, 8, 10];
const ps = new PrefixSum(arr);
console.log("Prefix sums:", ps.prefixSums.join(' -> ') + ' -> null');
console.log("Sum from index 1 to 3:", ps.getSum(1, 3)); // 4+6+8=18
console.log("Sum from index 0 to 4:", ps.getSum(0, 4)); // total sum 30
console.log("Sum from index 2 to 2:", ps.getSum(2, 2)); // single element 6

this.prefixSums[0] = this.arr[0]; // start with first element

initialize prefix sums with first element of original array

this.prefixSums[i] = this.prefixSums[i - 1] + this.arr[i]; // add current element to previous sum

build prefix sums by adding current element to previous total

if (start === 0) return this.prefixSums[end]; // sum from start

if subarray starts at zero, return prefix sum at end index

return this.prefixSums[end] - this.prefixSums[start - 1]; // subtract to get subarray sum

subtract prefix sums to get sum of subarray between start and end

Output

Prefix sums: 2 -> 6 -> 12 -> 20 -> 30 -> null

Sum from index 1 to 3: 18

Sum from index 0 to 4: 30

Sum from index 2 to 2: 6

Complexity Analysis

Time: O(n) because we build the prefix sums array by traversing the original array once

Space: O(n) because we store a prefix sum for each element in the array

vs Alternative: Without prefix sums, each subarray sum query takes O(k) time for subarray length k, but with prefix sums, queries take O(1) time after O(n) preprocessing

Edge Cases

empty array

prefix sums array remains empty, sum queries return 0

DSA Javascript

if (this.arr.length === 0) return;

single element array

prefix sums array has one element same as original, sum queries return that element or 0 if invalid range

DSA Javascript

this.prefixSums[0] = this.arr[0];

invalid sum query indices (start > end or out of bounds)

getSum returns 0 to indicate invalid query

DSA Javascript

if (start < 0 || end >= this.arr.length || start > end) return 0;

When to Use This Pattern

When you need to answer many sum queries on parts of an array quickly, use the prefix sum array pattern to preprocess sums and answer queries in constant time.

Common Mistakes

Mistake: Not initializing the first prefix sum element before the loop
Fix: Set prefixSums[0] = arr[0] before starting the loop

Mistake: Forgetting to handle sum queries starting at index 0 separately
Fix: Return prefixSums[end] directly if start is 0

Mistake: Not checking for invalid query indices in getSum
Fix: Add boundary checks and return 0 for invalid queries

Summary

It creates an array where each element is the sum of all elements up to that position in the original array.

Use it when you want to quickly find the sum of any part of an array multiple times.

The key is that you can get any subarray sum by subtracting two prefix sums, avoiding repeated addition.

Practice

1. What does a prefix sum array represent for a given array arr?

easy

A. An array where each element is the sum of all elements from the start up to that index in arr.

B. An array where each element is the product of all elements from the start up to that index in arr.

C. An array where each element is the difference between consecutive elements in arr.

D. An array where each element is the maximum value found in arr up to that index.

Solution

1. Step 1: Understand prefix sum array definition

   A prefix sum array stores sums of elements from the start of the original array up to each index.

2. Step 2: Compare options with definition

   Only An array where each element is the sum of all elements from the start up to that index in arr. correctly describes this sum accumulation behavior.

3. Final Answer:

   An array where each element is the sum of all elements from the start up to that index in arr. -> Option A

4. Quick Check:

   Prefix sum = cumulative sum [OK]

Hint: Prefix sum means cumulative addition from start [OK]

Common Mistakes:

• Confusing prefix sum with product or max
• Thinking prefix sum stores differences
• Assuming prefix sum stores original values

2. Which of the following JavaScript code snippets correctly initializes a prefix sum array prefix for an input array arr?

easy

A. const prefix = []; for(let i=0; i<arr.length; i++) { prefix[i] = arr[i] * prefix[i-1]; }

B. const prefix = [0]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; }

C. const prefix = [arr[0]]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; }

D. const prefix = []; for(let i=0; i<arr.length; i++) { prefix[i] = arr[i] - prefix[i-1]; }

Solution

1. Step 1: Check initialization of prefix sum array

   Prefix sum starts with first element of arr, so prefix[0] = arr[0].

2. Step 2: Verify loop logic for prefix sums

   Each prefix[i] = prefix[i-1] + arr[i] correctly accumulates sums.

3. Final Answer:

   const prefix = [arr[0]]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; } -> Option C

4. Quick Check:

   Initialize with arr[0], then add previous prefix [OK]

Hint: Start prefix with arr[0], then add previous sums [OK]

Common Mistakes:

• Starting prefix with 0 instead of arr[0]
• Using multiplication instead of addition
• Accessing prefix[-1] which is undefined

3. What will be the output of the following JavaScript code?

const arr = [2, 4, 6, 8];
const prefix = [arr[0]];
for(let i = 1; i < arr.length; i++) {
  prefix[i] = prefix[i-1] + arr[i];
}
console.log(prefix);

medium

A. [2, 6, 10, 18]

B. [2, 4, 6, 8]

C. [2, 8, 14, 22]

D. [2, 6, 12, 20]

Solution

1. Step 1: Calculate prefix sums step-by-step

   prefix[0] = 2; prefix[1] = 2 + 4 = 6; prefix[2] = 6 + 6 = 12; prefix[3] = 12 + 8 = 20.

2. Step 2: Confirm final prefix array

   The prefix array is [2, 6, 12, 20].

3. Final Answer:

   [2, 6, 12, 20] -> Option D

4. Quick Check:

   Sum accumulates correctly [OK]

Hint: Add current element to previous prefix sum [OK]

Common Mistakes:

• Adding elements incorrectly or skipping first element
• Confusing prefix array with original array
• Off-by-one errors in loop

4. Identify the error in the following code that attempts to create a prefix sum array:

const arr = [1, 3, 5, 7];
const prefix = [];
for(let i = 0; i < arr.length; i++) {
  prefix[i] = prefix[i-1] + arr[i];
}
console.log(prefix);

medium

A. prefix array is not initialized with first element, causing prefix[-1] to be undefined.

B. The loop should start from i = 1 instead of 0.

C. The code uses addition instead of multiplication.

D. The array arr is empty, so prefix will be empty.

Solution

1. Step 1: Analyze prefix[-1] usage at i=0

   At i=0, prefix[i-1] is prefix[-1], which is undefined, causing NaN result.

2. Step 2: Fix initialization to avoid undefined

   Initialize prefix[0] = arr[0] before loop or handle i=0 separately.

3. Final Answer:

   prefix array is not initialized with first element, causing prefix[-1] to be undefined. -> Option A

4. Quick Check:

   Accessing prefix[-1] causes undefined [OK]

Hint: Initialize prefix[0] before loop to avoid undefined [OK]

Common Mistakes:

• Starting loop at 0 without initializing prefix[0]
• Ignoring undefined prefix[-1] access
• Assuming prefix[-1] is zero automatically

5. Given an array arr = [3, 1, 4, 1, 5], how can you use a prefix sum array to efficiently find the sum of elements between indices 1 and 3 (inclusive)?

hard

A. Calculate prefix sums, then subtract prefix[0] from prefix[4].

B. Calculate prefix sums, then subtract prefix[0] from prefix[3].

C. Calculate prefix sums, then subtract prefix[0] from prefix[2].

D. Calculate prefix sums, then subtract prefix[1] from prefix[3].

Solution

1. Step 1: Build prefix sum array for arr

   prefix = [3, 4, 8, 9, 14] where prefix[i] = sum of arr[0..i].

2. Step 2: Calculate sum from index 1 to 3

   Sum = prefix[3] - prefix[0] = 9 - 3 = 6 (elements 1,4,1).

3. Final Answer:

   Calculate prefix sums, then subtract prefix[0] from prefix[3]. -> Option B

4. Quick Check:

   Sum(1 to 3) = prefix[3] - prefix[0] [OK]

Hint: Sum(i to j) = prefix[j] - prefix[i-1] [OK]

Common Mistakes:

• Subtracting prefix[i] instead of prefix[i-1]
• Using wrong indices for subtraction
• Not building prefix sums first