Prefix Sum Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this prefix sum array code?

Consider the following JavaScript code that creates a prefix sum array from an input array. What will be printed?

DSA Javascript

const arr = [2, 4, 6, 8];
const prefixSum = [];
prefixSum[0] = arr[0];
for (let i = 1; i < arr.length; i++) {
  prefixSum[i] = prefixSum[i - 1] + arr[i];
}
console.log(prefixSum);

A [2, 4, 6, 8]

B [2, 6, 12, 20]

C [2, 6, 10, 18]

D [0, 2, 6, 12]

💡 Hint

Remember each element in prefixSum is the sum of all elements up to that index in arr.

The prefix sum array stores cumulative sums. Starting with 2, then 2+4=6, then 6+6=12, then 12+8=20.

❓ Predict Output

intermediate

What is the value of prefixSum[3] after running this code?

Given the code below, what is the value stored at prefixSum[3]?

DSA Javascript

const arr = [1, 3, 5, 7, 9];
const prefixSum = [0];
for (let i = 0; i < arr.length; i++) {
  prefixSum[i + 1] = prefixSum[i] + arr[i];
}
console.log(prefixSum[3]);

A 9

B 16

C 6

D 8

💡 Hint

prefixSum[3] is sum of arr[0] + arr[1] + arr[2]

prefixSum[3] = arr[0] + arr[1] + arr[2] = 1 + 3 + 5 = 9, but since prefixSum starts with 0 at index 0, prefixSum[3] is sum of first 3 elements, which is 9.

🔧 Debug

advanced

Why does this prefix sum code produce incorrect results?

Look at this code snippet. It tries to build a prefix sum array but the output is wrong. What is the bug?

DSA Javascript

const arr = [1, 2, 3, 4];
const prefixSum = [];
for (let i = 0; i < arr.length; i++) {
  prefixSum[i] = prefixSum[i - 1] + arr[i];
}
console.log(prefixSum);

A arr[i] is not added correctly because of wrong index

B The loop should start from i = 1 instead of 0

C prefixSum[-1] is undefined on first iteration causing NaN values

D prefixSum array is not initialized with zeros

💡 Hint

Check what happens when i = 0 and prefixSum[i - 1] is accessed.

At i=0, prefixSum[-1] is undefined, so adding arr[0] results in NaN. This breaks the prefix sum calculation.

🚀 Application

advanced

How to find sum of elements between indices 2 and 5 using prefix sum array?

Given a prefix sum array prefixSum where prefixSum[i] is sum of elements from index 0 to i-1 in original array, how do you find sum of elements from index 2 to 5 (inclusive)?

A prefixSum[6] - prefixSum[2]

B prefixSum[5] - prefixSum[2]

C prefixSum[5] + prefixSum[2]

D prefixSum[6] + prefixSum[2]

💡 Hint

Sum from i to j = prefixSum[j+1] - prefixSum[i]

prefixSum array is 1-indexed for sums, so sum from 2 to 5 is prefixSum[6] - prefixSum[2].

🧠 Conceptual

expert

What is the time complexity to build and query prefix sum array for range sums?

If you have an array of size n, what is the time complexity to build a prefix sum array and then answer m queries asking for sum of elements between two indices?

A Building: O(n^2), Querying: O(1) per query

B Building: O(1), Querying: O(n) per query

C Building: O(n), Querying: O(n) per query

D Building: O(n), Querying: O(1) per query

💡 Hint

Think about how prefix sums are computed and how queries use them.

Building prefix sum array requires one pass O(n). Each query uses two prefix sums to get range sum in O(1).

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 from the start up to that index in arr.

B. An array where each element is the product of all elements from the start 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 in arr up to that index.

Solution

1. Step 1: Understand prefix sum array 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 from the start up to that index in arr. correctly describes this sum accumulation behavior.

3. Final Answer:

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

4. Quick Check:

   Prefix sum = cumulative sum [OK]

Hint: Prefix sum means cumulative addition from start [OK]

Common Mistakes:

• Confusing prefix sum with product or max
• Thinking prefix sum stores differences
• Assuming prefix sum stores original values

2. Which of the following JavaScript code snippets correctly initializes a prefix sum array prefix for an input array arr?

easy

A. const prefix = []; for(let i=0; i<arr.length; i++) { prefix[i] = arr[i] * prefix[i-1]; }

B. const prefix = [0]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; }

C. const prefix = [arr[0]]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; }

D. const prefix = []; for(let i=0; i<arr.length; i++) { prefix[i] = arr[i] - prefix[i-1]; }

Solution

1. Step 1: Check initialization of prefix sum array

   Prefix sum starts with first element of arr, so prefix[0] = arr[0].

2. Step 2: Verify loop logic for prefix sums

   Each prefix[i] = prefix[i-1] + arr[i] correctly accumulates sums.

3. Final Answer:

   const prefix = [arr[0]]; for(let i=1; i<arr.length; i++) { prefix[i] = prefix[i-1] + arr[i]; } -> Option C

4. Quick Check:

   Initialize with arr[0], then add previous prefix [OK]

Hint: Start prefix with arr[0], then add previous sums [OK]

Common Mistakes:

• Starting prefix with 0 instead of arr[0]
• Using multiplication instead of addition
• Accessing prefix[-1] which is undefined

3. What will be the output of the following JavaScript code?

const arr = [2, 4, 6, 8];
const prefix = [arr[0]];
for(let i = 1; i < arr.length; i++) {
  prefix[i] = prefix[i-1] + arr[i];
}
console.log(prefix);

medium

A. [2, 6, 10, 18]

B. [2, 4, 6, 8]

C. [2, 8, 14, 22]

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].

3. Final Answer:

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

4. Quick Check:

   Sum accumulates correctly [OK]

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

Common Mistakes:

• Adding elements incorrectly or skipping first element
• Confusing prefix array with original array
• Off-by-one errors in loop

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

const arr = [1, 3, 5, 7];
const prefix = [];
for(let i = 0; i < arr.length; i++) {
  prefix[i] = prefix[i-1] + arr[i];
}
console.log(prefix);

medium

A. prefix array is not initialized with first element, causing prefix[-1] to be undefined.

B. The loop should start from i = 1 instead of 0.

C. The code uses addition instead of multiplication.

D. The array arr is empty, so prefix will be empty.

Solution

1. Step 1: Analyze prefix[-1] usage at i=0

   At i=0, prefix[i-1] is prefix[-1], which is undefined, causing NaN result.

2. Step 2: Fix initialization to avoid undefined

   Initialize prefix[0] = arr[0] before loop or handle i=0 separately.

3. Final Answer:

   prefix array is not initialized with first element, causing prefix[-1] to be undefined. -> Option A

4. Quick Check:

   Accessing prefix[-1] causes undefined [OK]

Hint: Initialize prefix[0] before loop to avoid undefined [OK]

Common Mistakes:

• Starting loop at 0 without initializing prefix[0]
• Ignoring undefined prefix[-1] access
• Assuming prefix[-1] is zero automatically

5. Given an array arr = [3, 1, 4, 1, 5], how can you use a prefix sum array to efficiently find the sum of elements between indices 1 and 3 (inclusive)?

hard

A. Calculate prefix sums, then subtract prefix[0] from prefix[4].

B. Calculate prefix sums, then subtract prefix[0] from prefix[3].

C. Calculate prefix sums, then subtract prefix[0] from prefix[2].

D. Calculate prefix sums, then subtract prefix[1] from prefix[3].

Solution

1. Step 1: Build prefix sum array for arr

   prefix = [3, 4, 8, 9, 14] where prefix[i] = sum of arr[0..i].

2. Step 2: Calculate sum from index 1 to 3

   Sum = prefix[3] - prefix[0] = 9 - 3 = 6 (elements 1,4,1).

3. Final Answer:

   Calculate prefix sums, then subtract prefix[0] from prefix[3]. -> Option B

4. Quick Check:

   Sum(1 to 3) = prefix[3] - prefix[0] [OK]

Hint: Sum(i to j) = prefix[j] - prefix[i-1] [OK]

Common Mistakes:

• Subtracting prefix[i] instead of prefix[i-1]
• Using wrong indices for subtraction
• Not building prefix sums first