🗓️ Day 11: Prefix Sum Technique

🧠 Concept Deep Dive

The Prefix Sum technique is a powerful tool used to compute the sum of elements in a subarray efficiently. Instead of summing elements repeatedly for each query (which costs O(n)), you precompute cumulative sums in a new array so that any range sum can be found in O(1) time.

🔹 Key Idea

Given an array nums, build a prefix sum array prefix[] where:

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

Then, the sum of a subarray from index i to j can be computed as:

sum(i, j) = prefix[j + 1] - prefix[i]

🔹 When to Use Prefix Sum

• When there are multiple sum queries on the same array
• When you're asked to find the sum over a range many times
• When you're optimizing nested loops that sum values over a window

📖 Example 1: Range Sum Query

Problem:

Given an integer array nums, design a class that supports sum queries from index i to j (inclusive).

Approach:

Precompute the prefix sum array in the constructor, then answer each query in O(1).

class NumArray {
  private prefix: number[];

  constructor(nums: number[]) {
    this.prefix = [0];
    for (let num of nums) {
      this.prefix.push(this.prefix[this.prefix.length - 1] + num);
    }
  }

  sumRange(i: number, j: number): number {
    return this.prefix[j + 1] - this.prefix[i];
  }
}

Example:

Input: nums = [-2, 0, 3, -5, 2, -1]
Query: sumRange(0, 2)
Output: 1  // -2 + 0 + 3 = 1

📖 Example 2: Count Subarrays with Sum Equal to K

Problem:

Given an array nums and an integer k, return the total number of subarrays whose sum equals k.

Approach:

Use a prefix sum and a hash map to track how many times a certain prefix sum has occurred.

function subarraySum(nums: number[], k: number): number {
  const map = new Map<number, number>();
  map.set(0, 1);
  let count = 0, sum = 0;

  for (let num of nums) {
    sum += num;
    if (map.has(sum - k)) {
      count += map.get(sum - k)!;
    }
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
}

Example:

Input: nums = [1, 1, 1], k = 2
Output: 2  // [1,1] appears twice

🔬 Real-world Analogy

Imagine you’re on a road trip and you note your total distance traveled at every hour. If you want to find out how far you drove between hour 2 and hour 5, you just subtract the reading at hour 2 from the reading at hour 5. That’s how prefix sums work — fast and efficient distance calculations.

📊 Big O Complexity

🧪 LeetCode-style Homework

Problem: Range Sum Query - Immutable

Design a class to support range sum queries efficiently.

Function Signature:

class NumArray {
  constructor(nums: number[])
  sumRange(i: number, j: number): number
}

Hint: Use the prefix sum array. Don’t forget to add an initial 0.

🗓️ Summary

• Prefix Sum is best for sum queries over subarrays
• Use it to reduce repeated sum calculations
• Great for range problems and subarray optimizations

🔮 Up Next

▶️ Day 12: Two Pointers Technique