Prefix Sum Array in DSA Javascript - Time & Space Complexity

Time Complexity: Prefix Sum Array

O(n)

Understanding Time Complexity

We want to understand how fast we can build and use a prefix sum array.

How does the time needed change as the input array grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code creates a prefix sum array where prefix[i] is the sum of all elements from arr[0] to arr[i] inclusive.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that adds the current element to the previous sum.
• How many times: The loop runs once for each element after the first, so (n - 1) times.

How Execution Grows With Input

As the input array gets bigger, the number of additions grows roughly the same as the number of elements.

Input Size (n)	Approx. Operations
10	9 additions
100	99 additions
1000	999 additions

Pattern observation: The operations increase linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the prefix sum grows directly with the size of the input array.

Common Mistake

[X] Wrong: "Since we add sums repeatedly, the time is quadratic O(n²)."

[OK] Correct: Each addition uses the previous sum, so we do only one addition per element, not repeated sums for each element.

Interview Connect

Knowing prefix sums and their time complexity helps you quickly answer range sum queries efficiently, a common skill interviewers look for.

Self-Check

"What if we needed to build the prefix sum array multiple times for different input arrays? How would that affect the overall time complexity?"

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