Prefix Sum

Overview

Prefix Sum (also called cumulative sum) is a powerful technique that precomputes cumulative sums of array elements, enabling O(1) range sum queries. Instead of calculating sum from scratch each time, you build a prefix array once and use it for all queries.

The key insight: sum of subarray nums[i..j] equals prefix[j+1] - prefix[i], where prefix[k] represents sum of elements from index 0 to k-1. This transforms O(n) range queries into O(1) lookups.

Prefix sum is particularly useful for:

• Range sum queries
• Subarray sum problems
• Equilibrium index problems
• 2D range queries
• Multiple query optimization

Pattern 1: Basic Prefix Sum

Build prefix sum array and query ranges.

function buildPrefixSum(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  
  return prefix;
}

function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left];
}

Time: O(n) build, O(1) query, Space: O(n)

Example usage:

const nums = [1, 2, 3, 4, 5];
const prefix = buildPrefixSum(nums);
// prefix = [0, 1, 3, 6, 10, 15]

// Sum from index 1 to 3: prefix[4] - prefix[1] = 10 - 1 = 9
console.log(rangeSum(prefix, 1, 3)); // 9 (2 + 3 + 4)

Pattern 2: Subarray Sum Equals K

Count subarrays with sum exactly K using prefix sum.

function subarraySum(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1); // Empty subarray has sum 0
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    
    // If (sum - k) exists, we found subarray with sum k
    if (prefixSum.has(sum - k)) {
      count += prefixSum.get(sum - k)!;
    }
    
    // Update prefix sum frequency
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

Time: O(n), Space: O(n)

Explanation: If current prefix sum is S and we've seen prefix sum S - k before, then the subarray between those positions has sum k.

Pattern 3: Maximum Size Subarray Sum Equals K

Find maximum length subarray with sum K.

function maxSubArrayLen(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, -1); // Sum 0 at index -1
  
  let sum = 0;
  let maxLen = 0;
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    
    if (prefixSum.has(sum - k)) {
      maxLen = Math.max(maxLen, i - prefixSum.get(sum - k)!);
    }
    
    // Only store first occurrence for maximum length
    if (!prefixSum.has(sum)) {
      prefixSum.set(sum, i);
    }
  }
  
  return maxLen;
}

Time: O(n), Space: O(n)

Pattern 4: Equilibrium Index

Find index where sum of left elements equals sum of right elements.

function findEquilibriumIndex(nums: number[]): number {
  const totalSum = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;
  
  for (let i = 0; i < nums.length; i++) {
    const rightSum = totalSum - leftSum - nums[i];
    
    if (leftSum === rightSum) {
      return i;
    }
    
    leftSum += nums[i];
  }
  
  return -1;
}

Time: O(n), Space: O(1)

Using prefix sum:

function findEquilibriumIndexPrefix(nums: number[]): number {
  const prefix = buildPrefixSum(nums);
  const totalSum = prefix[nums.length];
  
  for (let i = 0; i < nums.length; i++) {
    const leftSum = prefix[i];
    const rightSum = totalSum - prefix[i + 1];
    
    if (leftSum === rightSum) {
      return i;
    }
  }
  
  return -1;
}

Pattern 5: Range Sum Query (Immutable)

Answer multiple range sum queries efficiently.

class NumArray {
  private prefix: number[];
  
  constructor(nums: number[]) {
    this.prefix = new Array(nums.length + 1).fill(0);
    
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }
  
  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

Time: O(n) construction, O(1) query, Space: O(n)

Pattern 6: Range Sum Query (Mutable)

Support updates and range queries using Fenwick Tree or Segment Tree.

Fenwick Tree (Binary Indexed Tree):

class FenwickTree {
  private tree: number[];
  private n: number;
  
  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(this.n + 1).fill(0);
    
    for (let i = 0; i < this.n; i++) {
      this.update(i, nums[i]);
    }
  }
  
  private updateIndex(index: number, delta: number): void {
    index++;
    while (index <= this.n) {
      this.tree[index] += delta;
      index += index & -index;
    }
  }
  
  update(index: number, val: number): void {
    const oldVal = this.prefixSum(index) - this.prefixSum(index - 1);
    this.updateIndex(index, val - oldVal);
  }
  
  private prefixSum(index: number): number {
    index++;
    let sum = 0;
    while (index > 0) {
      sum += this.tree[index];
      index -= index & -index;
    }
    return sum;
  }
  
  sumRange(left: number, right: number): number {
    return this.prefixSum(right) - this.prefixSum(left - 1);
  }
}

Time: O(log n) update, O(log n) query, Space: O(n)

Pattern 7: 2D Prefix Sum

Precompute 2D prefix sums for rectangle sum queries.

class NumMatrix {
  private prefix: number[][];
  
  constructor(matrix: number[][]) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    this.prefix = Array(rows + 1)
      .fill(null)
      .map(() => Array(cols + 1).fill(0));
    
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        this.prefix[i + 1][j + 1] = 
          matrix[i][j] +
          this.prefix[i][j + 1] +
          this.prefix[i + 1][j] -
          this.prefix[i][j];
      }
    }
  }
  
  sumRegion(row1: number, col1: number, row2: number, col2: number): number {
    return (
      this.prefix[row2 + 1][col2 + 1] -
      this.prefix[row1][col2 + 1] -
      this.prefix[row2 + 1][col1] +
      this.prefix[row1][col1]
    );
  }
}

Time: O(rows cols) construction, O(1) query, Space: O(rows cols)

Pattern 8: Product of Array Except Self

Use prefix and suffix products.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(1);
  
  // Prefix product
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] * nums[i - 1];
  }
  
  // Suffix product
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix;
    suffix *= nums[i];
  }
  
  return result;
}

Time: O(n), Space: O(1) excluding output

Pattern 9: Continuous Subarray Sum

Check if array has continuous subarray with sum multiple of K.

function checkSubarraySum(nums: number[], k: number): boolean {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, -1);
  
  let sum = 0;
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const remainder = sum % k;
    
    if (prefixSum.has(remainder)) {
      if (i - prefixSum.get(remainder)! > 1) {
        return true;
      }
    } else {
      prefixSum.set(remainder, i);
    }
  }
  
  return false;
}

Time: O(n), Space: O(min(n, k))

Key insight: If two prefix sums have same remainder mod K, the subarray between them is divisible by K.

Pattern 10: Maximum Sum of Two Non-Overlapping Subarrays

Find maximum sum of two non-overlapping subarrays of given lengths.

function maxSumTwoNoOverlap(nums: number[], firstLen: number, secondLen: number): number {
  const prefix = buildPrefixSum(nums);
  const n = nums.length;
  
  // Precompute maximum subarray sum ending at each position
  const maxFirst = new Array(n).fill(0);
  const maxSecond = new Array(n).fill(0);
  
  // Maximum firstLen subarray ending at i
  for (let i = firstLen - 1; i < n; i++) {
    const sum = prefix[i + 1] - prefix[i - firstLen + 1];
    maxFirst[i] = Math.max(
      i > 0 ? maxFirst[i - 1] : 0,
      sum
    );
  }
  
  // Maximum secondLen subarray ending at i
  for (let i = secondLen - 1; i < n; i++) {
    const sum = prefix[i + 1] - prefix[i - secondLen + 1];
    maxSecond[i] = Math.max(
      i > 0 ? maxSecond[i - 1] : 0,
      sum
    );
  }
  
  let maxSum = 0;
  
  // Try firstLen before secondLen
  for (let i = firstLen - 1; i < n - secondLen; i++) {
    const firstSum = prefix[i + 1] - prefix[i - firstLen + 1];
    const secondSum = maxSecond[n - 1] - (i >= secondLen - 1 ? maxSecond[i] : 0);
    maxSum = Math.max(maxSum, firstSum + secondSum);
  }
  
  // Try secondLen before firstLen
  for (let i = secondLen - 1; i < n - firstLen; i++) {
    const secondSum = prefix[i + 1] - prefix[i - secondLen + 1];
    const firstSum = maxFirst[n - 1] - (i >= firstLen - 1 ? maxFirst[i] : 0);
    maxSum = Math.max(maxSum, firstSum + secondSum);
  }
  
  return maxSum;
}

Time: O(n), Space: O(n)

Pattern 11: Subarray Sums Divisible by K

Count subarrays with sum divisible by K.

function subarraysDivByK(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1);
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    const remainder = ((sum % k) + k) % k; // Handle negative
    
    if (prefixSum.has(remainder)) {
      count += prefixSum.get(remainder)!;
    }
    
    prefixSum.set(remainder, (prefixSum.get(remainder) || 0) + 1);
  }
  
  return count;
}

Time: O(n), Space: O(min(n, k))

Pattern 12: Maximum Points You Can Obtain from Cards

Pick K cards from ends, maximize sum using prefix sum.

function maxScore(cardPoints: number[], k: number): number {
  const n = cardPoints.length;
  const prefixLeft = buildPrefixSum(cardPoints);
  
  // Build suffix sum
  const suffixRight = new Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    suffixRight[i] = suffixRight[i + 1] + cardPoints[i];
  }
  
  let maxSum = 0;
  
  // Try all combinations: i from left, (k-i) from right
  for (let i = 0; i <= k; i++) {
    const leftSum = prefixLeft[i];
    const rightSum = suffixRight[n - (k - i)];
    maxSum = Math.max(maxSum, leftSum + rightSum);
  }
  
  return maxSum;
}

Time: O(k), Space: O(n)

When to Use Prefix Sum

Use prefix sum when:

• Problem involves range sum queries
• Need to count subarrays with specific sum
• Multiple queries on same array
• 2D range queries (rectangle sums)
• Equilibrium or balance problems
• Need O(1) range queries after O(n) preprocessing

Template (1D Prefix Sum)

function prefixSumTemplate(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  
  return prefix;
}

function queryRange(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left];
}

Template (2D Prefix Sum)

function build2DPrefix(matrix: number[][]): number[][] {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const prefix = Array(rows + 1)
    .fill(null)
    .map(() => Array(cols + 1).fill(0));
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      prefix[i + 1][j + 1] = 
        matrix[i][j] +
        prefix[i][j + 1] +
        prefix[i + 1][j] -
        prefix[i][j];
    }
  }
  
  return prefix;
}

Time and Space Complexity Summary

• Build prefix sum: O(n) time, O(n) space
• Range query: O(1) time
• Subarray sum count: O(n) time, O(n) space
• 2D prefix sum: O(rows cols) time, O(rows cols) space
• 2D range query: O(1) time

Practice Tips

1. Index offset - prefix[i+1] represents sum from 0 to i
2. Handle negatives - Use mod arithmetic carefully
3. Map vs array - Use Map when sum range is large
4. Edge cases - Empty subarray (sum = 0), single element
5. 2D inclusion-exclusion - Remember to add back double-subtracted area

Common Mistakes

1. Index errors - prefix[i+1] vs prefix[i] confusion
2. Not initializing - Forgetting prefix[0] = 0
3. Negative mod - Not handling negative remainders
4. Overlapping subarrays - Not checking non-overlap condition
5. 2D formula - Wrong inclusion-exclusion in 2D

Related Concepts

• Sliding Window - Alternative for some subarray problems
• Hash Map - Used with prefix sum for counting
• Fenwick Tree - For mutable range queries
• Segment Tree - For complex range queries

Prefix sum is essential for range query optimization. Master these patterns, and you'll efficiently solve subarray sum and range query problems in coding interviews.