Prefix Sum Array in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Sum Array Construction

What is the output of the following Rust code that builds a prefix sum array from the input array?

DSA Rust

fn main() {
    let arr = vec![3, 1, 4, 1, 5];
    let mut prefix_sum = vec![0; arr.len() + 1];
    for i in 0..arr.len() {
        prefix_sum[i + 1] = prefix_sum[i] + arr[i];
    }
    println!("{:?}", prefix_sum);
}

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

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

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

D [3, 4, 8, 9, 14, 19]

💡 Hint

Remember the prefix sum array starts with 0 and each next element is the sum of all previous elements in the input array.

The prefix sum array starts with 0. Each element at index i+1 is the sum of all elements from index 0 to i in the original array. So for arr = [3,1,4,1,5], prefix_sum = [0,3,4,8,9,14].

🧠 Conceptual

intermediate

Purpose of Prefix Sum Array

What is the main advantage of using a prefix sum array when working with an array of numbers?

A It compresses the array to use less memory.

B It sorts the array elements in ascending order.

C It finds the maximum element in the array efficiently.

D It allows quick calculation of the sum of any subarray in constant time after preprocessing.

💡 Hint

Think about how prefix sums help with repeated sum queries on subarrays.

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

🔧 Debug

advanced

Identify the Error in Prefix Sum Calculation

What error does the following Rust code produce when trying to build a prefix sum array?

DSA Rust

fn main() {
    let arr = vec![2, 4, 6];
    let mut prefix_sum = vec![0; arr.len()];
    for i in 1..arr.len() {
        prefix_sum[i] = prefix_sum[i - 1] + arr[i];
    }
    println!("{:?}", prefix_sum);
}

A The first element of prefix_sum remains 0, so the prefix sums are incorrect.

B Index out of bounds panic at runtime.

C Compilation error due to mutable borrow.

D The code runs correctly and prints [0, 2, 6].

💡 Hint

Check how prefix_sum is initialized and how the loop starts.

The prefix_sum vector has length equal to arr, so prefix_sum[0] is 0 and never updated. The loop starts at i=1, so prefix_sum[1] = prefix_sum[0] + arr[1] = 0 + 4 = 4, but prefix_sum[0] should be arr[0]. This causes incorrect prefix sums.

❓ Predict Output

advanced

Output After Using Prefix Sum to Query Subarray Sum

Given the prefix sum array, what is the output of the code that calculates the sum of elements from index 1 to 3 (inclusive) in the original array?

DSA Rust

fn main() {
    let arr = vec![1, 2, 3, 4, 5];
    let mut prefix_sum = vec![0; arr.len() + 1];
    for i in 0..arr.len() {
        prefix_sum[i + 1] = prefix_sum[i] + arr[i];
    }
    let start = 1;
    let end = 3;
    let sub_sum = prefix_sum[end + 1] - prefix_sum[start];
    println!("{}", sub_sum);
}

A 6

B 9

C 10

D 7

💡 Hint

Sum from index 1 to 3 means sum of elements 2, 3, and 4.

The sum is arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9. Using prefix sums, sub_sum = prefix_sum[4] - prefix_sum[1] = 10 - 1 = 9.

🧠 Conceptual

expert

Time Complexity of Multiple Range Sum Queries Using Prefix Sum

If you have an array of size n and you want to answer m queries asking for the sum of elements between indices i and j, what is the overall time complexity using a prefix sum array?

A O(n + m), where n is for building prefix sums and m for queries

B O(n^2), due to nested loops for each query

C O(m log n), using binary search on prefix sums

D O(n * m), because each query sums elements individually

💡 Hint

Building prefix sums takes linear time, each query is constant time.

Building the prefix sum array takes O(n). Each query can be answered in O(1) by subtracting two prefix sums. So total is O(n + m).

Practice

1. What does a prefix sum array represent for a given array arr?

easy

A. An array where each element is the difference between consecutive elements 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 sum of all elements up to that index 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 original 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, describing cumulative sums.

3. Final Answer:

   An array where each element is the sum of all elements up to that index in arr -> Option C

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 between elements
• Assuming prefix sum stores only the last element's value

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

easy

A. let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; }

B. let mut prefix = vec![0; arr.len()]; for i in 0..arr.len() { prefix[i] = arr[i] + prefix[i+1]; }

C. let prefix = arr.iter().map(|x| *x).collect::();

D. let mut prefix = vec![0; arr.len()]; prefix[0] = 0; for i in 1..arr.len() { prefix[i] = prefix[i-1] * arr[i]; }

Solution

1. Step 1: Check initialization and first element assignment

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } initializes prefix with zeros, sets prefix[0] = arr[0], which is correct.

2. Step 2: Verify loop logic for prefix sums

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } loops from 1 to end, adding prefix[i-1] + arr[i], correctly building prefix sums.

3. Final Answer:

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } -> Option A

4. Quick Check:

   Correct prefix sum loop syntax [OK]

Hint: Start prefix[0] = arr[0], then add previous prefix + current arr [OK]

Common Mistakes:

• Using prefix[i+1] inside loop causing out-of-bounds
• Multiplying instead of adding elements
• Not initializing prefix[0] before loop

3. Given the Rust code below, what is the printed output?

let arr = vec![2, 4, 6, 8];
let mut prefix = vec![0; arr.len()];
prefix[0] = arr[0];
for i in 1..arr.len() {
    prefix[i] = prefix[i-1] + arr[i];
}
println!("{:?}", prefix);

medium

A. [2, 8, 14, 22]

B. [2, 4, 6, 8]

C. [0, 2, 6, 12]

D. [2, 6, 12, 20]

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

   The prefix array is [2, 6, 12, 20], matching [2, 6, 12, 20].

3. Final Answer:

   [2, 6, 12, 20] -> Option D

4. Quick Check:

   Sum accumulates correctly [OK]

Hint: Add each element to previous prefix sum [OK]

Common Mistakes:

• Printing original array instead of prefix
• Starting prefix sums from zero incorrectly
• Miscomputing sums by skipping elements

4. Identify the error in the following Rust code that attempts to create a prefix sum array and fix it:

let arr = vec![1, 3, 5];
let mut prefix = vec![0; arr.len()];
for i in 0..arr.len() {
    prefix[i] = prefix[i-1] + arr[i];
}
println!("{:?}", prefix);

medium

A. The loop starts at 0 but uses prefix[i-1], causing out-of-bounds; start loop at 1 and set prefix[0] = arr[0]

B. The vector prefix is not mutable; add mut keyword

C. The arr vector is empty; initialize with values

D. The println! macro is missing a semicolon

Solution

1. Step 1: Identify cause of out-of-bounds error

   At i=0, prefix[i-1] is prefix[-1], which is invalid in Rust and causes panic.

2. Step 2: Fix loop and initialization

   Set prefix[0] = arr[0] before loop, then loop from i=1 to arr.len()-1 to safely access prefix[i-1].

3. Final Answer:

   The loop starts at 0 but uses prefix[i-1], causing out-of-bounds; start loop at 1 and set prefix[0] = arr[0] -> Option A

4. Quick Check:

   Indexing prefix[i-1] at i=0 causes error [OK]

Hint: Avoid negative indexing; initialize first element before loop [OK]

Common Mistakes:

• Starting loop at 0 and accessing prefix[i-1]
• Not initializing prefix[0] before loop
• Ignoring Rust's strict bounds checking

5. You have an array arr = [3, 1, 4, 1, 5, 9, 2]. Using a prefix sum array, how would you efficiently find the sum of elements between indices 2 and 5 (inclusive)?

hard

A. Calculate prefix sums, then sum = prefix[5] + prefix[2]

B. Calculate prefix sums, then sum = prefix[5] - prefix[1]

C. Calculate prefix sums, then sum = prefix[5] - prefix[2]

D. Calculate prefix sums, then sum = prefix[6] - prefix[2]

Solution

1. Step 1: Understand prefix sum usage for range sums

   Sum from index l to r = prefix[r] - prefix[l-1], assuming prefix sums start at index 0.

2. Step 2: Apply to given indices 2 to 5

   Sum = prefix[5] - prefix[1], since prefix[1] is sum up to index 1.

3. Final Answer:

   Calculate prefix sums, then sum = prefix[5] - prefix[1] -> 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[start] instead of prefix[start-1]
• Adding prefix values instead of subtracting
• Using wrong indices for prefix subtraction