Prefix Sum Array in DSA Go - 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 this Go code?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{3, 1, 4, 1, 5}
  prefix := make([]int, len(arr))
  prefix[0] = arr[0]
  for i := 1; i < len(arr); i++ {
    prefix[i] = prefix[i-1] + arr[i]
  }
  fmt.Println(prefix)
}

A [3 4 5 6 7]

B [3 1 4 1 5]

C [3 4 8 9 14]

D [0 3 4 8 9]

💡 Hint

Think about how each element in the prefix array sums all previous elements including itself.

The prefix sum array stores cumulative sums. Each element is the sum of all elements up to that index in the original array.

🧠 Conceptual

intermediate

Purpose of Prefix Sum Array

What is the main advantage of using a prefix sum array when querying sums of subarrays?

A It allows sum queries in constant time after preprocessing.

B It sorts the array to speed up queries.

C It compresses the array to use less memory.

D It reverses the array to simplify calculations.

💡 Hint

Think about how prefix sums help avoid repeated addition.

Prefix sum arrays let you find the sum of any subarray quickly by subtracting two prefix sums, avoiding repeated addition.

🔧 Debug

advanced

Identify the Bug in Prefix Sum Code

What error will this Go code produce when building a prefix sum array?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{2, 4, 6}
  prefix := make([]int, len(arr))
  for i := 1; i < len(arr); i++ {
    prefix[i] = prefix[i-1] + arr[i]
  }
  fmt.Println(prefix)
}

A runtime error: index out of range

B [2 6 12]

C syntax error: missing colon

D [0 2 6]

💡 Hint

Check the loop boundaries and array indexing carefully.

The loop uses i <= len(arr), which tries to access prefix[len(arr)] and arr[len(arr)], both out of range.

❓ Predict Output

advanced

Prefix Sum Array with Negative Numbers

What is the output of the prefix sum array after running this Go code with negative numbers?

DSA Go

package main
import "fmt"
func main() {
  arr := []int{5, -2, 3, -1, 4}
  prefix := make([]int, len(arr))
  prefix[0] = arr[0]
  for i := 1; i < len(arr); i++ {
    prefix[i] = prefix[i-1] + arr[i]
  }
  fmt.Println(prefix)
}

A [5 -2 3 -1 4]

B [5 7 10 9 13]

C [0 5 3 6 5]

D [5 3 6 5 9]

💡 Hint

Add each element to the sum of all previous elements including negatives.

Prefix sums include negative numbers, so sums can decrease or increase accordingly.

🚀 Application

expert

Using Prefix Sum to Count Subarrays with Sum Zero

Given an integer array, which approach uses prefix sums to count how many subarrays have a sum of zero?

A Sort the array and count pairs that sum to zero.

B Use a map to store prefix sums and count how many times each sum appears; increment count when a prefix sum repeats.

C Use two nested loops to check all subarrays and sum them directly.

D Reverse the array and count zeros in the reversed array.

💡 Hint

Think about how repeated prefix sums indicate zero-sum subarrays.

If prefix sums repeat, the elements between those indices sum to zero. Counting repeats helps find zero-sum subarrays efficiently.

Practice

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

easy

A. To find the maximum element in the array

B. To sort the array elements in ascending order

C. To reverse the array elements efficiently

D. To quickly find the sum of elements in any subarray

Solution

1. Step 1: Understand prefix sum array concept

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

2. Step 2: Use prefix sums for subarray sums

   Using prefix sums, sum of any subarray can be found quickly by subtracting two prefix sums.

3. Final Answer:

   To quickly find the sum of elements in any subarray -> Option D

4. Quick Check:

   Prefix sum array helps fast subarray sums [OK]

Hint: Prefix sums store cumulative sums for fast subarray queries [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly initializes a prefix sum array prefix from an integer slice arr?

easy

A. prefix := make([]int, len(arr))
for i := 0; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

B. prefix := make([]int, len(arr)+1)
for i := 1; i <= len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i-1]
}

C. prefix := make([]int, len(arr)+1)
for i := 0; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

D. prefix := make([]int, len(arr))
for i := 1; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

Solution

1. Step 1: Check prefix array size and indexing

   Prefix sum array usually has length one more than original to handle zero prefix sum at start.

2. Step 2: Verify loop and indexing logic

   Loop from 1 to len(arr), prefix[i] = prefix[i-1] + arr[i-1] correctly accumulates sums.

3. Final Answer:

   prefix := make([]int, len(arr)+1) for i := 1; i <= len(arr); i++ { prefix[i] = prefix[i-1] + arr[i-1] } -> Option B

4. Quick Check:

   Correct prefix sum initialization uses offset indexing [OK]

Hint: Prefix array length = original length + 1, loop starts at 1 [OK]

Common Mistakes:

• Using prefix array same length as original
• Starting loop at 0 and accessing prefix[-1]
• Incorrect indexing of arr inside loop

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

arr := []int{2, 4, 6, 8}
prefix := make([]int, len(arr)+1)
for i := 1; i <= len(arr); i++ {
  prefix[i] = prefix[i-1] + arr[i-1]
}
fmt.Println(prefix)

medium

A. [0 2 6 12 20]

B. [2 6 12 20 28]

C. [0 2 4 6 8]

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

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

3. Final Answer:

   [0 2 6 12 20] -> Option A

4. Quick Check:

   Sum accumulates correctly in prefix array [OK]

Hint: Start prefix with 0, add elements cumulatively [OK]

Common Mistakes:

• Forgetting initial zero in prefix array
• Adding wrong elements at each step
• Confusing prefix array length

4. Identify the error in this Go code that tries to build a prefix sum array:

arr := []int{1, 3, 5}
prefix := make([]int, len(arr))
for i := 1; i < len(arr); i++ {
  prefix[i] = prefix[i-1] + arr[i]
}
fmt.Println(prefix)

medium

A. prefix array size should be len(arr)+1

B. Loop should start from i=0 instead of i=1

C. prefix[0] is not initialized before use

D. arr indexing is out of range

Solution

1. Step 1: Check prefix array initialization

   Prefix array is size len(arr), which can work but prefix[0] must be set before use.

2. Step 2: Analyze loop and prefix[0]

   Loop starts at i=1, prefix[1] = prefix[0] + arr[1]. prefix[0] is zero by default in Go, but it should be explicitly set to arr[0] before the loop.

3. Step 3: Check correctness of prefix sums

   prefix[0] is zero, but arr[0] is never added, so prefix sums are incomplete.

4. Final Answer:

   prefix[0] is not initialized before use -> Option C

5. Quick Check:

   Missing prefix[0] initialization causes wrong sums [OK]

Hint: Initialize prefix[0] before loop to avoid wrong sums [OK]

Common Mistakes:

• Not initializing prefix[0]
• Wrong prefix array size
• Incorrect loop start index

5. Given an integer slice arr, how can you use a prefix sum array to find the sum of elements between indices l and r (inclusive) efficiently?

hard

A. sum = prefix[r+1] - prefix[l]

B. sum = prefix[r] - prefix[l-1]

C. sum = prefix[r] + prefix[l]

D. sum = prefix[r+1] + prefix[l-1]

Solution

1. Step 1: Understand prefix sum indexing

   Prefix sum array usually has length len(arr)+1 with prefix[0]=0, prefix[i] = sum of arr[0..i-1].

2. Step 2: Calculate subarray sum using prefix sums

   Sum from l to r = prefix[r+1] - prefix[l] because prefix[r+1] sums up to arr[r].

3. Final Answer:

   sum = prefix[r+1] - prefix[l] -> Option A

4. Quick Check:

   Subarray sum = prefix[r+1] - prefix[l] [OK]

Hint: Use prefix[r+1] - prefix[l] for sum between l and r [OK]

Common Mistakes:

• Using prefix[r] - prefix[l-1] without offset
• Adding prefix sums instead of subtracting
• Confusing indices by 1