Prefix Sum Array in DSA Java - Execution Trace

Concept Flow - Prefix Sum Array

Start with original array

↓

Create prefix sum array of same size

↓

Set prefix[0

↓

For each index i from 1 to end

↓

Calculate prefix[i

↓

Prefix sum array ready for queries

Build a new array where each element prefix[i] is the sum of all elements from the original array up to and including index i.

Execution Sample

DSA Java

int[] arr = {2, 4, 6, 8};
int[] prefix = new int[arr.length];
if (arr.length > 0) {
    prefix[0] = arr[0];
    for (int i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
}

Calculate prefix sums for the array {2,4,6,8} step-by-step.

Execution Table

Step	Operation	Index i	prefix[i-1]	arr[i]	prefix[i]	Prefix Sum Array State
1	Initialize prefix[0]	0	N/A	2	2	[2, _, _, _]
2	Calculate prefix[1]	1	2	4	6	[2, 6, _, _]
3	Calculate prefix[2]	2	6	6	12	[2, 6, 12, _]
4	Calculate prefix[3]	3	12	8	20	[2, 6, 12, 20]
5	End loop	N/A	N/A	N/A	N/A	[2, 6, 12, 20]

💡 Loop ends after i reaches array length 4

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	N/A	0	1	2	3	4 (loop ends)
prefix[0]	undefined	2	2	2	2	2
prefix[1]	undefined	undefined	6	6	6	6
prefix[2]	undefined	undefined	undefined	12	12	12
prefix[3]	undefined	undefined	undefined	undefined	20	20
prefix array	[_, _, _, _]	[2, _, _, _]	[2, 6, _, _]	[2, 6, 12, _]	[2, 6, 12, 20]	[2, 6, 12, 20]

Key Moments - 3 Insights

Why do we start prefix[0] with arr[0] instead of 0?

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

Why do we add prefix[i-1] and arr[i] to get prefix[i]?

Because prefix[i-1] already holds the sum of all elements before i, adding arr[i] extends the sum to include the current element. See steps 2 to 4 in execution_table.

What happens if the original array is empty?

The code as shown throws ArrayIndexOutOfBoundsException on prefix[0]=arr[0]. Add if(arr.length > 0) before that line. The loop does not run.

Visual Quiz - 3 Questions

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

A 6

B 20

C 12

D 2

💡 Hint

Check the 'prefix[i]' column at step 3 in execution_table.

At which step does the prefix sum array become [2, 6, 12, 20]?

A Step 4

B Step 2

C Step 3

D Step 1

💡 Hint

Look at the 'Prefix Sum Array State' column in execution_table.

If arr[1] was changed from 4 to 5, what would prefix[1] be after step 2?

A 5

B 7

C 6

D 9

💡 Hint

prefix[1] = prefix[0] + arr[1], so add prefix[0] (2) and new arr[1] (5).

Concept Snapshot

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

Full Transcript

Prefix Sum Array builds a new array where each element is the sum of all elements up to that index in the original array. We start by setting prefix[0] equal to arr[0]. Then for each index i from 1 to the end, we add the previous prefix sum prefix[i-1] to the current element arr[i] to get prefix[i]. This way, prefix[i] holds the sum of elements from index 0 to i. The process stops when we reach the end of the array. This technique helps quickly find sums of any subarray later. The example uses arr = {2,4,6,8} and shows prefix sums calculated step-by-step resulting in prefix = {2,6,12,20}.

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 up to that index in arr

B. An array where each element is the product of all elements 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 up to that index in arr

Solution

1. Step 1: Understand prefix sum definition

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

2. Step 2: Compare options with definition

   Only An array where each element is the sum of all elements up to that index in arr matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   Prefix sum = cumulative sum [OK]

Hint: Prefix sum means cumulative sum from start to current index [OK]

Common Mistakes:

• Confusing prefix sum with product or max operations
• Thinking prefix sum stores differences
• Mixing prefix sum with suffix sum

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

easy

A. int[] prefix = new int[arr.length]; for(int i=0; i

B. int[] prefix = new int[arr.length]; prefix[0] = 0; for(int i=1; i

C. int[] prefix = new int[arr.length]; prefix[0] = arr[0]; for(int i=1; i

D. int[] prefix = new int[arr.length]; for(int i=0; i

Solution

1. Step 1: Check initialization of prefix array

   Prefix sum array must start with prefix[0] = arr[0] to include first element sum.

2. Step 2: Verify loop calculation

   Loop from i=1 to end adds previous prefix sum plus current arr element, which is correct.

3. Final Answer:

   int[] prefix = new int[arr.length]; prefix[0] = arr[0]; for(int i=1; i -> Option C

4. Quick Check:

   Initialize first element, then add previous sums [OK]

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

Common Mistakes:

• Starting prefix[0] with 0 instead of arr[0]
• Multiplying instead of adding elements
• Reversing array elements instead of summing

3. What is the output of the following Java code?

int[] arr = {2, 4, 6, 8};
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for(int i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}
System.out.println(java.util.Arrays.toString(prefix));

medium

A. [2, 6, 12, 20]

B. [2, 4, 6, 8]

C. [0, 2, 6, 12]

D. [2, 8, 14, 22]

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: Verify final prefix array

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

3. Final Answer:

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

4. Quick Check:

   Sum accumulates: 2, 6, 12, 20 [OK]

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

Common Mistakes:

• Printing original array instead of prefix sum
• Starting prefix sum with 0 incorrectly
• Adding wrong elements in loop

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

int[] arr = {1, 3, 5};
int[] prefix = new int[arr.length];
prefix[0] = 0;
for(int i = 1; i <= arr.length; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. Loop condition should be i < arr.length instead of i <= arr.length

B. prefix[0] should be initialized to arr[0] instead of 0

C. Array index arr[i] will cause an error when i equals arr.length

D. All of the above

Solution

1. Step 1: Check loop boundary

   The loop uses i <= arr.length, which causes index out of bounds because valid indices are 0 to arr.length-1.

2. Step 2: Check prefix[0] initialization and array access

   prefix[0] should be arr[0] to start sums correctly; also arr[i] access fails at i = arr.length.

3. Step 3: Combine all errors

   All issues cause runtime errors or incorrect prefix sums.

4. Final Answer:

   All of the above -> Option D

5. Quick Check:

   Loop bounds, initialization, and indexing errors combined [OK]

Hint: Check loop limits and array indices carefully [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing prefix[0] incorrectly
• Accessing array out of bounds

5. Given an integer array arr of length 5: {3, 1, 4, 1, 5}, you want to find the sum of elements from index 1 to 3 (inclusive) efficiently using a prefix sum array. Which expression correctly calculates this sum using the prefix sum array prefix where prefix[i] is the sum of elements from index 0 to i?

hard

A. prefix[3] - prefix[2]

B. prefix[3] - prefix[0]

C. prefix[3] - prefix[1]

D. prefix[3] - prefix[0] + arr[1]

Solution

1. Step 1: Understand prefix sum usage for range sums

   Sum from index l to r = prefix[r] - prefix[l-1]. Here l=1, r=3.

2. Step 2: Apply formula with given indices

   Sum = prefix[3] - prefix[0]. prefix[0] is sum up to index 0, so subtracting it leaves sum from 1 to 3.

3. Final Answer:

   prefix[3] - prefix[0] -> Option B

4. Quick Check:

   Range sum = prefix[r] - prefix[l-1] [OK]

Hint: Range sum = prefix[end] - prefix[start - 1] [OK]

Common Mistakes:

• Subtracting prefix at wrong index
• Adding extra elements unnecessarily
• Confusing inclusive indices