Prefix Sum Array in DSA Typescript

Mental Model

A prefix sum array stores sums of elements from the start up to each position, so you can quickly find sums of any part of the original array.

Analogy: Imagine a row of buckets where each bucket holds the total water collected from the first bucket up to that bucket. To find water between any two buckets, you just subtract the totals.

Original array: [2] [4] [5] [7] [1]
Prefix sums:  [2] [6] [11] [18] [19]

Dry Run Walkthrough

Input: array: [2, 4, 5, 7, 1]

Goal: Create a prefix sum array to quickly find sums of any subarray

Step 1: Start prefix sum array with first element same as original

Prefix sums: [2] null null null null

Why: The first prefix sum is just the first element itself

Step 2: Add second element to previous prefix sum: 2 + 4 = 6

Prefix sums: [2] [6] null null null

Why: Sum from start to second element is sum of first two elements

Step 3: Add third element to previous prefix sum: 6 + 5 = 11

Prefix sums: [2] [6] [11] null null

Why: Sum from start to third element includes first three elements

Step 4: Add fourth element to previous prefix sum: 11 + 7 = 18

Prefix sums: [2] [6] [11] [18] null

Why: Sum from start to fourth element includes first four elements

Step 5: Add fifth element to previous prefix sum: 18 + 1 = 19

Prefix sums: [2] [6] [11] [18] [19]

Why: Sum from start to fifth element includes all elements

Result:

Prefix sums: [2] [6] [11] [18] [19]

Annotated Code

DSA Typescript

class PrefixSumArray {
  private prefixSums: number[] = [];

  constructor(private arr: number[]) {
    this.buildPrefixSums();
  }

  private buildPrefixSums(): void {
    if (this.arr.length === 0) return;
    this.prefixSums[0] = this.arr[0];
    for (let i = 1; i < this.arr.length; i++) {
      this.prefixSums[i] = this.prefixSums[i - 1] + this.arr[i];
    }
  }

  // Returns sum from index left to right inclusive
  public rangeSum(left: number, right: number): number {
    if (left === 0) return this.prefixSums[right];
    return this.prefixSums[right] - this.prefixSums[left - 1];
  }

  public printPrefixSums(): void {
    console.log(this.prefixSums.join(' '));
  }
}

// Driver code
const arr = [2, 4, 5, 7, 1];
const psa = new PrefixSumArray(arr);
psa.printPrefixSums();

this.prefixSums[0] = this.arr[0];

Initialize first prefix sum with first element

for (let i = 1; i < this.arr.length; i++) {

Loop through array from second element to end

this.prefixSums[i] = this.prefixSums[i - 1] + this.arr[i];

Add current element to previous prefix sum to build current prefix sum

if (left === 0) return this.prefixSums[right];

If sum starts from index 0, return prefix sum at right

return this.prefixSums[right] - this.prefixSums[left - 1];

Otherwise subtract prefix sum before left to get range sum

Output

2 6 11 18 19

Complexity Analysis

Time: O(n) because we build prefix sums by traversing the array once

Space: O(n) because we store prefix sums for each element

vs Alternative: Without prefix sums, range sum queries take O(k) time for k elements; prefix sums reduce this to O(1) per query after O(n) preprocessing

Edge Cases

empty array

prefix sum array remains empty, no sums to compute

DSA Typescript

if (this.arr.length === 0) return;

single element array

prefix sum array has one element same as original

DSA Typescript

this.prefixSums[0] = this.arr[0];

range sum with left = 0

returns prefix sum at right index directly

DSA Typescript

if (left === 0) return this.prefixSums[right];

When to Use This Pattern

When you need to answer many sum queries on parts of an array quickly, use prefix sum arrays to preprocess sums for fast lookups.

Common Mistakes

Mistake: Starting prefix sums from index 1 instead of 0 causing undefined values
Fix: Always initialize prefixSums[0] with arr[0] before looping

Mistake: Forgetting to handle the case when left index is zero in range sum queries
Fix: Add a condition to return prefixSums[right] directly if left is zero

Summary

It creates an array where each element is the sum of all elements up to that position in the original array.

Use it when you want to quickly find the sum of any part of an array multiple times.

The key is that each prefix sum builds on the previous one, so you only add one new element each step.

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