Prefix Sum Array in DSA Java

Mental Model

A prefix sum array stores the sum of all elements from the start up to each position. It helps quickly find sums of any part of the original array.

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

Original array:  [1] -> [2] -> [3] -> [4] -> [5]
Prefix sums:     [1] -> [3] -> [6] -> [10] -> [15]

Dry Run Walkthrough

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

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

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

Prefix sums: [1] -> null

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

Step 2: Add second element to previous prefix sum: 1 + 2 = 3

Prefix sums: [1] -> [3] -> null

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

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

Prefix sums: [1] -> [3] -> [6] -> null

Why: Continue accumulating sums to build prefix array

Step 4: Add fourth element to previous prefix sum: 6 + 4 = 10

Prefix sums: [1] -> [3] -> [6] -> [10] -> null

Why: Keep adding elements to get running totals

Step 5: Add fifth element to previous prefix sum: 10 + 5 = 15

Prefix sums: [1] -> [3] -> [6] -> [10] -> [15] -> null

Why: Final prefix sum includes all elements

Result:

Prefix sums: [1] -> [3] -> [6] -> [10] -> [15] -> null

Annotated Code

DSA Java

public class PrefixSumArray {
    // Build prefix sum array from input array
    public static int[] buildPrefixSum(int[] arr) {
        int n = arr.length;
        if (n == 0) return new int[0];
        int[] prefix = new int[n];
        prefix[0] = arr[0]; // first prefix sum is first element
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + arr[i]; // add current element to previous sum
        }
        return prefix;
    }

    // Print array in readable format
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i != arr.length - 1) System.out.print(" -> ");
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4, 5};
        System.out.print("Original array: ");
        printArray(input);
        int[] prefixSum = buildPrefixSum(input);
        System.out.print("Prefix sums:    ");
        printArray(prefixSum);
    }
}

prefix[0] = arr[0]; // first prefix sum is first element

initialize prefix sum with first element

prefix[i] = prefix[i - 1] + arr[i]; // add current element to previous sum

accumulate sum up to current index

Output

Original array: 1 -> 2 -> 3 -> 4 -> 5 -> null

Prefix sums:    1 -> 3 -> 6 -> 10 -> 15 -> 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; prefix sums reduce it to O(1) after O(n) preprocessing

Edge Cases

empty array

returns empty prefix sum array without error

DSA Java

if (n == 0) return new int[0];

single element array

prefix sum array equals the original single element

DSA Java

prefix[0] = arr[0];

When to Use This Pattern

When you need to find sums of many subarrays quickly, use prefix sum arrays to speed up repeated sum queries.

Common Mistakes

Mistake: Starting prefix sum from index 1 without initializing index 0
Fix: Always set prefix[0] = arr[0] before looping from index 1

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

Summary

Creates an array where each element is the sum of all elements up to that index in the original array.

Use when you want to quickly find sums of any subarray multiple times.

The key is to store running totals so you can subtract to get any sub-sum instantly.

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