Prefix Sum Array in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Prefix Sum Array?

A Prefix Sum Array is a new array where each element at index i is the sum of all elements from the start up to index i in the original array. It helps to quickly find the sum of any subarray.

beginner

How do you calculate the prefix sum array for [2, 4, 6, 8]?

Start with the first element: 2. Then add each next element to the sum so far: [2, 6 (2+4), 12 (6+6), 20 (12+8)].

intermediate

Why is a prefix sum array useful?

It allows you to find the sum of any part of the array quickly by subtracting two prefix sums instead of adding many elements each time.

intermediate

Write the formula to find the sum of elements from index i to j using a prefix sum array.

Sum(i to j) = prefixSum[j] - prefixSum[i - 1] (if i > 0), else prefixSum[j] if i = 0.

beginner

What is the time complexity to build a prefix sum array of size n?

The time complexity is O(n) because you calculate each prefix sum by adding the current element to the previous prefix sum once.

What does the element at index i in a prefix sum array represent?

A Sum of elements from index i to the end of the array

B Sum of elements from index 0 to i in the original array

C Value of the element at index i in the original array

D Difference between elements at i and i-1

Each prefix sum element stores the total sum from the start up to that index.

How do you find the sum of elements between indices 2 and 4 using a prefix sum array?

A prefixSum[4] - prefixSum[1]

B prefixSum[4] + prefixSum[2]

C prefixSum[2] - prefixSum[4]

D prefixSum[4] - prefixSum[2]

Sum from 2 to 4 = prefixSum[4] - prefixSum[1], subtracting sum before index 2.

What is the time complexity to get the sum of any subarray using a prefix sum array?

A O(n^2)

B O(n)

C O(1)

D O(log n)

Using prefix sums, subarray sums can be found instantly with subtraction.

If the original array is empty, what is the prefix sum array?

A Empty array

B [0]

C Array with one element 1

D Undefined

An empty original array results in an empty prefix sum array.

Which of these is NOT a benefit of using prefix sum arrays?

A Helps in solving range sum problems

B Faster subarray sum queries

C Simple to build in O(n) time

D Less memory usage than original array

Prefix sum arrays use extra memory equal to the original array size.

Explain how to build a prefix sum array from a given array and how it helps in finding subarray sums.

Think about adding elements one by one and how subtraction helps.

Describe the formula to get the sum of elements between two indices i and j using a prefix sum array and why it works.

Consider what prefixSum stores and how to exclude elements before i.

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