Prefix Sum Array in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Sum Array Construction

What is the output of the prefix sum array after running the following code?

DSA Python

arr = [3, 1, 4, 1, 5]
prefix_sum = [0] * len(arr)
prefix_sum[0] = arr[0]
for i in range(1, len(arr)):
    prefix_sum[i] = prefix_sum[i-1] + arr[i]
print(prefix_sum)

A [3, 1, 4, 1, 5]

B [3, 4, 8, 9, 14]

C [0, 3, 4, 8, 9]

D [3, 4, 5, 6, 7]

💡 Hint

Remember each element in prefix sum is sum of all previous elements including current.

The prefix sum array stores cumulative sums. Starting with 3, then 3+1=4, then 4+4=8, then 8+1=9, then 9+5=14.

🧠 Conceptual

intermediate

Purpose of Prefix Sum Array

What is the main advantage of using a prefix sum array in algorithms?

A To reverse the array elements without extra space.

B To sort the array elements in ascending order.

C To quickly calculate the sum of any subarray in constant time after preprocessing.

D To find the maximum element in the array efficiently.

💡 Hint

Think about how prefix sums help with repeated sum queries.

Prefix sum arrays allow quick calculation of sums of any subarray by subtracting prefix sums, making sum queries O(1) after O(n) preprocessing.

❓ Predict Output

advanced

Output of Prefix Sum Code

What is the output of the following code?

DSA Python

arr = [2, 4, 6]
prefix_sum = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix_sum[i + 1] = prefix_sum[i] + arr[i]
print(prefix_sum)

A [0, 2, 6, 12]

B TypeError: unsupported operand type(s) for +: 'int' and 'list'

C IndexError: list index out of range

D [2, 6, 12, 0]

💡 Hint

Check the first iteration and the index used for prefix_sum.

The code correctly computes prefix_sum with an extra leading 0. prefix_sum[0] = 0, prefix_sum[1] = 0 + 2 = 2, prefix_sum[2] = 2 + 4 = 6, prefix_sum[3] = 6 + 6 = 12. Output: [0, 2, 6, 12], which is option A.

❓ Predict Output

advanced

Output of Prefix Sum Query

Given the prefix sum array prefix_sum = [0, 3, 7, 12, 18], what is the sum of elements from index 1 to 3 (inclusive) in the original array?

DSA Python

prefix_sum = [0, 3, 7, 12, 18]
start = 1
end = 3
result = prefix_sum[end + 1] - prefix_sum[start]
print(result)

A 9

B 12

C 7

D 15

💡 Hint

Sum from i to j = prefix_sum[j+1] - prefix_sum[i].

The sum from index 1 to 3 is prefix_sum[4] - prefix_sum[1] = 18 - 3 = 15. The code computes prefix_sum[end + 1] - prefix_sum[start] = 18 - 3 = 15.

Original array derived: arr = [3, 4, 5, 6], sum arr[1:4] = 4+5+6=15.

So correct answer is 15 (option D).

🧠 Conceptual

expert

Space Complexity of Prefix Sum Array

What is the space complexity of storing a prefix sum array for an input array of size n?

A O(n)

B O(1)

C O(n^2)

D O(log n)

💡 Hint

Consider how many elements the prefix sum array stores compared to the input.

The prefix sum array stores one value per element of the input array, so it requires linear space O(n).