Prefix Sum Array in DSA Go

Mental Model

A prefix sum array stores the running total of elements up to each position, so you can quickly find sums of any part of the original array.

Analogy: Imagine a row of buckets where each bucket holds the total amount of water collected from the first bucket up to that bucket. To find how much water is between two buckets, you just subtract the totals.

Original array:  [2] -> [4] -> [5] -> [7] -> [3]
Prefix sums:     [2] -> [6] -> [11] -> [18] -> [21]

Dry Run Walkthrough

Input: array: [2, 4, 5, 7, 3]

Goal: Create a prefix sum array to quickly find sums of any subarray

Step 1: Start prefix sum array with first element same as original

Prefix sums: [2] -> null

Why: The first prefix sum is just the first element itself

Step 2: Add second element to previous prefix sum: 2 + 4 = 6

Prefix sums: [2] -> [6] -> null

Why: Each prefix sum includes all elements up to that index

Step 3: Add third element to previous prefix sum: 6 + 5 = 11

Prefix sums: [2] -> [6] -> [11] -> null

Why: Keep accumulating sums to build prefix array

Step 4: Add fourth element to previous prefix sum: 11 + 7 = 18

Prefix sums: [2] -> [6] -> [11] -> [18] -> null

Why: Continue running total for prefix sums

Step 5: Add fifth element to previous prefix sum: 18 + 3 = 21

Prefix sums: [2] -> [6] -> [11] -> [18] -> [21] -> null

Why: Final prefix sum includes all elements

Result:

Prefix sums: [2] -> [6] -> [11] -> [18] -> [21] -> null

Annotated Code

DSA Go

package main

import "fmt"

// prefixSum creates a prefix sum array from input array
func prefixSum(arr []int) []int {
    if len(arr) == 0 {
        return []int{}
    }
    prefix := make([]int, len(arr))
    prefix[0] = arr[0] // start with first element
    for i := 1; i < len(arr); i++ {
        prefix[i] = prefix[i-1] + arr[i] // add current element to running total
    }
    return prefix
}

func main() {
    arr := []int{2, 4, 5, 7, 3}
    prefix := prefixSum(arr)
    // print prefix sums in arrow format
    for i, val := range prefix {
        if i < len(prefix)-1 {
            fmt.Printf("%d -> ", val)
        } else {
            fmt.Printf("%d -> null\n", val)
        }
    }
}

prefix[0] = arr[0] // start with first element

initialize prefix sum with first element of original array

prefix[i] = prefix[i-1] + arr[i] // add current element to running total

accumulate sum by adding current element to previous prefix sum

Output

2 -> 6 -> 11 -> 18 -> 21 -> null

Complexity Analysis

Time: O(n) because we process each element once to build prefix sums

Space: O(n) because we create a new array to store prefix sums

vs Alternative: Without prefix sums, summing any subarray takes O(k) time, but with prefix sums it takes O(1) after O(n) preprocessing

Edge Cases

empty array

returns empty prefix sum array

DSA Go

if len(arr) == 0 {
        return []int{}
    }

single element array

prefix sum array is same as original array

DSA Go

prefix[0] = arr[0] // start with first element

When to Use This Pattern

When you need to find sums of many subarrays quickly, use prefix sums to reduce repeated addition work.

Common Mistakes

Mistake: Starting prefix sum array without initializing the first element
Fix: Always set prefix[0] = arr[0] before looping

Mistake: Adding arr[i] to arr[i-1] instead of prefix[i-1]
Fix: Add current element to prefix[i-1], not to arr[i-1]

Summary

It creates an array where each element is the sum of all elements before it in the original array.

Use it when you want to quickly find the sum of any part of an array multiple times.

The key is to keep a running total so you don't add the same numbers over and over.

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