Prefix Sum Array in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the prefix sum array with the first element of the input array.

DSA Rust

let mut prefix_sum = vec![0; nums.len()];
prefix_sum[0] = [1];

Drag options to blanks, or click blank then click option'

Aprefix_sum[1]

B0

Cnums[1]

Dnums[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Setting prefix_sum[0] to 0 instead of nums[0]

Using prefix_sum[1] before it is initialized

The prefix sum array starts with the first element of the input array, so prefix_sum[0] should be nums[0].

2fill in blank

medium

Complete the code to calculate the prefix sum for each element starting from the second element.

DSA Rust

for i in 1..nums.len() {
    prefix_sum[i] = prefix_sum[i - 1] [1] nums[i];
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition

Using division which is not correct for prefix sums

Each prefix sum is the sum of the previous prefix sum and the current element, so use +.

3fill in blank

hard

Fix the error in the code to correctly compute the prefix sum array.

DSA Rust

let mut prefix_sum = vec![0; nums.len()];
prefix_sum[0] = nums[0];
for i in 1..nums.len() {
    prefix_sum[i] = prefix_sum[i - 1] [1] nums[i];
}

Drag options to blanks, or click blank then click option'

A*

B+

C-

D=

Attempts:

3 left

💡 Hint

Common Mistakes

Using prefix_sum[i] instead of prefix_sum[i - 1]

Using wrong operator like - or *

The code mistakenly uses prefix_sum[i] on the right side instead of prefix_sum[i - 1]. The blank should be + and the code should use prefix_sum[i - 1].

4fill in blank

hard

Fill both blanks to create a function that returns the prefix sum array for a given vector.

DSA Rust

fn prefix_sum_array(nums: &Vec<i32>) -> Vec<i32> {
    let mut prefix_sum = vec![0; nums.len()];
    prefix_sum[0] = nums[0];
    for i in 1..nums.len() {
        prefix_sum[i] = prefix_sum[i [1]] [2] nums[i];
    }
    prefix_sum
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using i+1 instead of i-1 for previous index

Using subtraction or multiplication instead of addition

To compute prefix sums, subtract 1 from i to get the previous prefix sum index, then add the current element.

5fill in blank

hard

Fill all three blanks to create a function that returns the prefix sum array and handles empty input safely.

DSA Rust

fn prefix_sum_array_safe(nums: &Vec<i32>) -> Vec<i32> {
    if nums.is_empty() {
        return vec![];
    }
    let mut prefix_sum = vec![0; nums.len()];
    prefix_sum[0] = nums[[1]];
    for i in 1..nums.len() {
        prefix_sum[i] = prefix_sum[i [2]] [3] nums[i];
    }
    prefix_sum
}

Drag options to blanks, or click blank then click option'

A0

B-

C+

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using nums[1] for first element

Using i+1 instead of i-1 for previous index

Using wrong operator instead of +

The first prefix sum is nums[0]. The loop uses i-1 for previous prefix sum index and adds the current element.

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