Prefix Sum Array in DSA Javascript - Execution Trace

Concept Flow - Prefix Sum Array

Start with input array

↓

Create prefix sum array with same length

↓

Set prefixSum[0

↓

For each index i from 1 to end

↓

Calculate prefixSum[i

↓

Repeat until end of array

↓

Prefix sum array ready for queries

We start with the input array and build a new array where each element is the sum of all elements up to that index.

Execution Sample

DSA Javascript

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

This code creates a prefix sum array from the input array by adding each element to the sum of all previous elements.

Execution Table

Step	Operation	Index i	prefixSum Array	Calculation	Visual State
1	Initialize prefixSum[0]	0	[2]	prefixSum[0] = input[0] = 2	2 -> null
2	Calculate prefixSum[1]	1	[2, 6]	prefixSum[1] = prefixSum[0] + input[1] = 2 + 4 = 6	2 -> 6 -> null
3	Calculate prefixSum[2]	2	[2, 6, 12]	prefixSum[2] = prefixSum[1] + input[2] = 6 + 6 = 12	2 -> 6 -> 12 -> null
4	Calculate prefixSum[3]	3	[2, 6, 12, 20]	prefixSum[3] = prefixSum[2] + input[3] = 12 + 8 = 20	2 -> 6 -> 12 -> 20 -> null
5	End loop	-	[2, 6, 12, 20]	All prefix sums calculated	2 -> 6 -> 12 -> 20 -> null

💡 Loop ends after processing all elements of input array

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	-	0	1	2	3	-
prefixSum	[]	[2]	[2, 6]	[2, 6, 12]	[2, 6, 12, 20]	[2, 6, 12, 20]

Key Moments - 3 Insights

Why do we set prefixSum[0] equal to input[0] before the loop?

Because prefixSum[0] represents the sum of the first element only, so we start with input[0] to build the rest step-by-step as shown in step 1 of the execution table.

Why do we add prefixSum[i-1] to input[i] instead of just input[i]?

Because prefixSum[i-1] already contains the sum of all elements before index i, adding input[i] extends the sum up to index i, as seen in steps 2 to 4.

What happens if the input array is empty?

The loop does not run and prefixSum remains empty, so no prefix sums are calculated. This is implied by the exit note in the execution table.

Visual Quiz - 3 Questions

Look at the execution table, what is prefixSum after step 3?

A [2, 6, 12]

B [2, 4, 6]

C [2, 6, 18]

D [2, 10, 12]

💡 Hint

Check the 'prefixSum Array' column at step 3 in the execution table.

At which step does the prefixSum array first contain the sum of the first two elements?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for when prefixSum includes the sum of input[0] + input[1] in the execution table.

If input array changes to [1, 3, 5], what will prefixSum[2] be?

A 5

B 8

C 9

D 3

💡 Hint

Calculate prefixSum[2] = prefixSum[1] + input[2] with new input values.

Concept Snapshot

Prefix Sum Array:
- Create new array same size as input
- prefixSum[0] = input[0]
- For i=1 to end: prefixSum[i] = prefixSum[i-1] + input[i]
- Each prefixSum[i] stores sum of input[0..i]
- Useful for fast range sum queries

Full Transcript

The prefix sum array is built by starting with the first element of the input array. We create a new array where each element at index i is the sum of all elements from index 0 to i in the input. We set prefixSum[0] equal to input[0]. Then, for each index from 1 to the end, we add the current input element to the previous prefix sum. This process continues until the entire prefix sum array is filled. If the input is empty, no prefix sums are calculated. This method helps quickly find sums of subarrays later.

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