Array Prefix Sum and Subarray Sum Quiz Quiz

Challenge your understanding of array prefix sums and subarray sum computations with focused questions. This quiz helps you test and reinforce key techniques and problem-solving skills involving prefix sums, array manipulation, and efficient subarray sum calculations.

1. Prefix Sum Calculation

   Given the array [2, 4, 6, 8, 10], what is the prefix sum at index 3 (zero-based indexing)?

   1. 12
   2. 8
   3. 20
   4. 18

   Explanation: The prefix sum at index 3 is the sum of elements at indices 0 to 3, which is 2 + 4 + 6 + 8 = 20. Option 12 comes from summing only 2 + 4 + 6, which stops short. Option 8 is just the value at index 3, not the sum. Option 18 miscalculates the total by leaving out one value or misplacing an addition.

2. Subarray Sum Using Prefix Sums

   For an array nums = [1, 3, 5, 7, 9], how can you efficiently find the sum of the subarray from index 1 to index 3 using prefix sums?

   1. prefixSum[4] - prefixSum[1]
   2. prefixSum[2] - prefixSum[0]
   3. prefixSum[3] - prefixSum[0]
   4. prefixSum[3]

   Explanation: To find the sum from index 1 to 3, subtract prefixSum[0] from prefixSum[3], giving (1+3+5+7)-(1)=15-1=14, which matches the sum of 3+5+7. Option 'prefixSum[3]' gives the sum from index 0 to 3, including one extra value. Option 'prefixSum[4] - prefixSum[1]' calculates the sum of indices 2 to 4, which is not correct here. Option 'prefixSum[2] - prefixSum[0]' covers only indices 1 to 2.

3. Prefix Sum Utility

   Why is the prefix sum approach preferred over the naive method when calculating sums of multiple subarrays in a large array?

   1. It allows updating array elements in constant time.
   2. It enables computing any subarray sum in constant time after preprocessing.
   3. It reduces the time complexity from O(n) to O(log n) per query.
   4. It sorts the array automatically during calculation.

   Explanation: Once you have computed the prefix sum array, any subarray sum can be found in constant time using a simple subtraction; this is much faster than the naive linear approach. Reducing time complexity to O(log n) is incorrect, as prefix sums provide O(1) query time, not logarithmic. Updating array elements is not constant time in the prefix sum method unless extended with other techniques. Prefix sums do not sort the array as part of their functionality.

4. Subarray Sum Range Example

   If prefixSum = [0, 5, 8, 15, 18] for some array, what is the sum of the subarray from index 2 to index 3 inclusive?

   1. 8
   2. 10
   3. 3
   4. 7

   Explanation: The subarray sum from index 2 to 3 is calculated as prefixSum[4] - prefixSum[2] = 18 - 8 = 10. However, this covers indices 2 through 3, so the correct subarray sum based on prefixSum indices is 15 - 8 = 7. Option 3 represents incorrect subtraction. Option 10 is for prefixSum[4] - prefixSum[2], which overshoots. Option 8 comes from subtracting the wrong indices.

5. Finding Subarrays with Given Sum

   Given an array of positive integers and its prefix sum array, which technique efficiently counts the subarrays with a target sum k?

   1. Nested loops over all subarrays
   2. Comparing all prefix sum differences for k
   3. Sliding window with two pointers
   4. Brute force by recomputing sums each time

   Explanation: The optimal method for positive integers is to iterate through the prefix sum array and count the number of pairs where their difference equals k. Sliding window can work for continuous positive subarrays but is limited in scope. Nested loops and brute force recomputation are much slower. Comparing all possible prefix sum differences directly relates subarray sums to the target.