Prefix Sum Array in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Prefix Sum Array?

A Prefix Sum Array is an array where each element at index i stores the sum of all elements from the start up to index i of the original array. It helps to quickly calculate the sum of any subarray.

beginner

How do you compute the prefix sum array for an input array [2, 4, 6, 8]?

Start with the first element: prefixSum[0] = 2.
Then add each element to the sum of all previous elements:
prefixSum[1] = 2 + 4 = 6
prefixSum[2] = 6 + 6 = 12
prefixSum[3] = 12 + 8 = 20
So, prefix sum array = [2, 6, 12, 20].

intermediate

How can a prefix sum array help find the sum of elements between two indices i and j quickly?

The sum from index i to j can be found by subtracting prefixSum[i-1] from prefixSum[j].
That is, sum(i to j) = prefixSum[j] - prefixSum[i-1].
If i = 0, then sum is just prefixSum[j].

beginner

What is the time complexity to build a prefix sum array of size n?

The time complexity is O(n) because you need to iterate through the array once to compute the cumulative sums.

intermediate

Why is prefix sum array useful in algorithms?

It allows quick calculation of sums over any subarray in constant time after a one-time O(n) preprocessing. This speeds up problems involving multiple sum queries.

What does the element at index i in a prefix sum array represent?

A Sum of all elements from index i to the end of the array

B Value of the original array at index i

C Sum of all elements from index 0 to i in the original array

D Difference between elements at i and i-1

Each prefix sum element stores the sum of all elements from the start up to that index.

How do you find the sum of elements between indices 2 and 5 using a prefix sum array?

A prefixSum[5] - prefixSum[1]

B prefixSum[5] + prefixSum[2]

C prefixSum[2] - prefixSum[5]

D prefixSum[5] - prefixSum[2]

Sum(i to j) = prefixSum[j] - prefixSum[i-1], so for i=2 and j=5, subtract prefixSum[1] from prefixSum[5].

What is the time complexity to answer a sum query using a prefix sum array?

A O(n)

B O(1)

C O(log n)

D O(n^2)

After building the prefix sum array, each sum query can be answered in constant time.

If the original array is empty, what is the prefix sum array?

A Array with negative values

B Array with one zero

C Array with one element equal to the sum

D Empty array

If there are no elements, the prefix sum array is also empty.

Which of these is NOT a benefit of using a prefix sum array?

A Less memory usage than original array

B Faster sum queries

C Preprocessing in linear time

D Simplifies subarray sum calculations

Prefix sum array uses extra memory equal to the original array size, so it does not reduce memory usage.

Explain how to build a prefix sum array from a given integer array.

Think about adding each element to the sum of all previous elements.

Describe how a prefix sum array helps in finding the sum of any subarray quickly.

Subtract the prefix sum before the start index from the prefix sum at the end index.

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