Prefix Sum Array in DSA Typescript - Execution Trace

Concept Flow - Prefix Sum Array

Start with original array

↓

Initialize prefix sum array with first element

↓

For each next element i

↓

Add current element to prefix sum of previous

↓

Store sum at prefix_sum[i

↓

Repeat until end of array

↓

Prefix sum array ready

Build prefix sum array by adding each element to the sum of all previous elements step-by-step.

Execution Sample

DSA Typescript

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

Calculate prefix sums for array [2,4,6,8], storing cumulative sums at each index.

Execution Table

Step	Operation	Index i	prefixSum[i-1]	arr[i]	prefixSum[i]	Visual State
1	Initialize prefixSum[0]	0	N/A	2	2	[2]
2	Calculate prefixSum[1]	1	2	4	6	[2, 6]
3	Calculate prefixSum[2]	2	6	6	12	[2, 6, 12]
4	Calculate prefixSum[3]	3	12	8	20	[2, 6, 12, 20]
5	End loop	N/A	N/A	N/A	N/A	Prefix sum array complete

💡 Loop ends after processing all elements; prefix sum array fully built.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	undefined	0	1	2	3	4 (loop ends)
prefixSum	[]	[2]	[2, 6]	[2, 6, 12]	[2, 6, 12, 20]	[2, 6, 12, 20]

Key Moments - 3 Insights

Why do we start prefixSum with the first element of the original array?

Because prefixSum[0] represents the sum of elements up to index 0, which is just arr[0]. This is shown in execution_table row 1 where prefixSum[0] is initialized to 2.

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

Adding prefixSum[i-1] accumulates the sum of all previous elements, so prefixSum[i] holds the total sum from start to index i. This is clear in rows 2-4 where prefixSum[i] builds on prefixSum[i-1].

What happens if the original array is empty?

The loop does not run and prefixSum remains empty. The code must handle this case separately to avoid errors, as no initialization step occurs.

Visual Quiz - 3 Questions

Look at the execution_table, what is prefixSum[2] after step 3?

A 8

B 6

C 12

D 20

💡 Hint

Check the 'prefixSum[i]' column in row 3 of execution_table.

At which step does the loop end according to the execution_table?

A Step 3

B Step 5

C Step 4

D Step 2

💡 Hint

Look for the row labeled 'End loop' in execution_table.

If arr was [1, 3, 5], what would prefixSum[1] be?

A 4

B 3

C 1

D 5

💡 Hint

prefixSum[1] = prefixSum[0] + arr[1], so sum first two elements.

Concept Snapshot

Prefix Sum Array:
- prefixSum[0] = arr[0]
- prefixSum[i] = prefixSum[i-1] + arr[i]
- Stores cumulative sums up to each index
- Useful for quick range sum queries
- Build in O(n) time by one pass

Full Transcript

Prefix Sum Array is built by starting with the first element of the original array as prefixSum[0]. Then for each next index i, prefixSum[i] is calculated by adding arr[i] to prefixSum[i-1]. This accumulates the sum of all elements up to i. The process repeats until the end of the array. The final prefixSum array holds cumulative sums, enabling fast sum queries over ranges. If the original array is empty, prefixSum remains empty and the loop does not run.

Practice

1. What is the main purpose of a prefix sum array in algorithms?

easy

A. To quickly find the sum of elements between any two indices

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the maximum element in the array

Solution

1. Step 1: Understand what prefix sum array stores

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

2. Step 2: Identify the use of prefix sums

   Using prefix sums, we can find the sum of any subarray quickly by subtracting two prefix sums.

3. Final Answer:

   To quickly find the sum of elements between any two indices -> Option A

4. Quick Check:

   Prefix sum array = fast range sum queries [OK]

Hint: Prefix sums help answer range sum queries fast [OK]

Common Mistakes:

• Confusing prefix sum with sorting
• Thinking prefix sum reverses array
• Assuming prefix sum finds max element

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

easy

A. const prefix = []; for(let i=0; i

B. const prefix = [0]; for(let i=0; i

C. const prefix = [arr[0]]; for(let i=1; i

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

Solution

1. Step 1: Check initialization and loop indexing

   const prefix = [0]; for(let i=0; i

2. Step 2: Identify errors in other options

   const prefix = []; for(let i=0; i

3. Final Answer:

   const prefix = [0]; for(let i=0; i -> Option B

4. Quick Check:

   Prefix sum array starts with 0 and accumulates sums [OK]

Hint: Start prefix with 0 and add arr[i] in loop [OK]

Common Mistakes:

• Accessing array out of bounds
• Not initializing prefix[0] to 0
• Using negative indices

3. Given the TypeScript code below, what is the output printed?

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

medium

A. [2, 6, 12, 20]

B. [0, 2, 4, 6, 8]

C. [0, 2, 6, 12, 20]

D. [2, 4, 6, 8, 0]

Solution

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

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

2. Step 2: Confirm final prefix array

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

3. Final Answer:

   [0, 2, 6, 12, 20] -> Option C

4. Quick Check:

   Sum accumulates correctly in prefix array [OK]

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

Common Mistakes:

• Forgetting initial 0 in prefix
• Adding wrong elements in loop
• Off-by-one errors in indexing

4. The following TypeScript code attempts to create a prefix sum array but has a bug. What is the error?

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

medium

A. prefix array is not initialized with 0 at index 0

B. Loop runs one time too many

C. arr[i] is accessed out of bounds

D. prefix array is declared with wrong type

Solution

1. Step 1: Check prefix array initialization

   The prefix array is empty initially, so prefix[0] is undefined.

2. Step 2: Identify impact on prefix sum calculation

   prefix[i] is undefined for i=0, so prefix[1] = undefined + arr[0] results in NaN.

3. Final Answer:

   prefix array is not initialized with 0 at index 0 -> Option A

4. Quick Check:

   Initialize prefix[0] = 0 to avoid NaN [OK]

Hint: Always start prefix array with 0 at index 0 [OK]

Common Mistakes:

• Not initializing prefix[0]
• Assuming empty array has prefix[0]
• Ignoring NaN results

5. You have an array arr = [3, 1, 4, 1, 5, 9, 2]. Using a prefix sum array, how would you efficiently find the sum of elements from index 2 to 5 (inclusive)?

hard

A. Calculate prefix sums, then sum = prefix[5] - prefix[1]

B. Calculate prefix sums, then sum = prefix[6] - prefix[1]

C. Calculate prefix sums, then sum = prefix[5] - prefix[2]

D. Calculate prefix sums, then sum = prefix[6] - prefix[2]

Solution

1. Step 1: Understand prefix sum indexing

   Prefix sum array prefix has prefix[0] = 0, prefix[i] = sum of arr[0] to arr[i-1].

2. Step 2: Calculate sum from index 2 to 5

   Sum = prefix[6] - prefix[2], because prefix[6] sums arr[0..5], prefix[2] sums arr[0..1].

3. Final Answer:

   Calculate prefix sums, then sum = prefix[6] - prefix[2] -> Option D

4. Quick Check:

   Sum of arr[2..5] = prefix[6] - prefix[2] [OK]

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

Common Mistakes:

• Off-by-one errors in prefix indices
• Subtracting wrong prefix sums
• Confusing inclusive/exclusive ranges