Prefix Sum Array in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Sum Array Construction

What is the output of the following TypeScript code that builds a prefix sum array?

DSA Typescript

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

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

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

C [3, 3, 7, 8, 13]

D [3, 1, 4, 1, 5]

💡 Hint

Remember that each element in the prefix sum array is the sum of all elements up to that index.

The prefix sum array stores cumulative sums. Starting with 3, then 3+1=4, then 4+4=8, then 8+1=9, and finally 9+5=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 reverses the array elements.

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.

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

🔧 Debug

advanced

Identify the Error in Prefix Sum Code

What error will the following TypeScript code produce when trying to build a prefix sum array?

DSA Typescript

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

A [2, 4, 6]

B TypeError: Cannot read property '-1' of undefined

C SyntaxError: Unexpected token

D [2, 6, 12]

💡 Hint

Check what happens when i = 0 in prefixSum[i - 1].

Accessing prefixSum[-1] is undefined, so adding undefined to arr[0] causes a TypeError.

🚀 Application

advanced

Using Prefix Sum to Find Subarray Sum

Given a prefix sum array prefixSum = [2, 5, 9, 14, 20], what is the sum of the subarray from index 2 to 4 (inclusive)?

A 11

B 9

C 15

D 20

💡 Hint

Use prefixSum[end] - prefixSum[start - 1] to find subarray sums.

Sum from index 2 to 4 (inclusive) = prefixSum[4] - prefixSum[1] = 20 - 5 = 15.

📝 Syntax

expert

Correct Prefix Sum Array Initialization

Which option correctly initializes and builds a prefix sum array in TypeScript for arr = [1, 2, 3, 4]?

A

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

B

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

C

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

D

const prefixSum = new Array(arr.length).fill(0);
for(let i=0; i<arr.length; i++) {
  prefixSum[i] = prefixSum[i-1] + arr[i];
}
console.log(prefixSum);

💡 Hint

Check how the first element is set and how the loop starts.

Option A correctly initializes prefixSum with the first element and starts loop from i=1, avoiding undefined access.

Option A and D access prefixSum[-1] at i=0 causing errors.

Option A creates prefixSum with an extra 0 at start, which changes the array length and output.

Practice

1. What is the main purpose of a prefix sum array in algorithms?

easy

A. To quickly find the sum of elements between any two indices

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the maximum element in the array

Solution

1. Step 1: Understand what prefix sum array stores

   A prefix sum array stores cumulative sums of elements from the start up to each index.

2. Step 2: Identify the use of prefix sums

   Using prefix sums, we can find the sum of any subarray quickly by subtracting two prefix sums.

3. Final Answer:

   To quickly find the sum of elements between any two indices -> Option A

4. Quick Check:

   Prefix sum array = fast range sum queries [OK]

Hint: Prefix sums help answer range sum queries fast [OK]

Common Mistakes:

• Confusing prefix sum with sorting
• Thinking prefix sum reverses array
• Assuming prefix sum finds max element

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

easy

A. const prefix = []; for(let i=0; i

B. const prefix = [0]; for(let i=0; i

C. const prefix = [arr[0]]; for(let i=1; i

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

Solution

1. Step 1: Check initialization and loop indexing

   const prefix = [0]; for(let i=0; i

2. Step 2: Identify errors in other options

   const prefix = []; for(let i=0; i

3. Final Answer:

   const prefix = [0]; for(let i=0; i -> Option B

4. Quick Check:

   Prefix sum array starts with 0 and accumulates sums [OK]

Hint: Start prefix with 0 and add arr[i] in loop [OK]

Common Mistakes:

• Accessing array out of bounds
• Not initializing prefix[0] to 0
• Using negative indices

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

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

medium

A. [2, 6, 12, 20]

B. [0, 2, 4, 6, 8]

C. [0, 2, 6, 12, 20]

D. [2, 4, 6, 8, 0]

Solution

1. Step 1: Calculate prefix sums step-by-step

   prefix[0] = 0 prefix[1] = 0 + 2 = 2 prefix[2] = 2 + 4 = 6 prefix[3] = 6 + 6 = 12 prefix[4] = 12 + 8 = 20

2. Step 2: Confirm final prefix array

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

3. Final Answer:

   [0, 2, 6, 12, 20] -> Option C

4. Quick Check:

   Sum accumulates correctly in prefix array [OK]

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

Common Mistakes:

• Forgetting initial 0 in prefix
• Adding wrong elements in loop
• Off-by-one errors in indexing

4. The following TypeScript code attempts to create a prefix sum array but has a bug. What is the error?

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

medium

A. prefix array is not initialized with 0 at index 0

B. Loop runs one time too many

C. arr[i] is accessed out of bounds

D. prefix array is declared with wrong type

Solution

1. Step 1: Check prefix array initialization

   The prefix array is empty initially, so prefix[0] is undefined.

2. Step 2: Identify impact on prefix sum calculation

   prefix[i] is undefined for i=0, so prefix[1] = undefined + arr[0] results in NaN.

3. Final Answer:

   prefix array is not initialized with 0 at index 0 -> Option A

4. Quick Check:

   Initialize prefix[0] = 0 to avoid NaN [OK]

Hint: Always start prefix array with 0 at index 0 [OK]

Common Mistakes:

• Not initializing prefix[0]
• Assuming empty array has prefix[0]
• Ignoring NaN results

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 from index 2 to 5 (inclusive)?

hard

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

B. Calculate prefix sums, then sum = prefix[6] - 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 indexing

   Prefix sum array prefix has prefix[0] = 0, prefix[i] = sum of arr[0] to arr[i-1].

2. Step 2: Calculate sum from index 2 to 5

   Sum = prefix[6] - prefix[2], because prefix[6] sums arr[0..5], prefix[2] sums arr[0..1].

3. Final Answer:

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

4. Quick Check:

   Sum of arr[2..5] = prefix[6] - prefix[2] [OK]

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

Common Mistakes:

• Off-by-one errors in prefix indices
• Subtracting wrong prefix sums
• Confusing inclusive/exclusive ranges