Prefix Sum: Patterns, Complexity & Interview Use Cases

Prefix sum (also called cumulative sum) is a technique that precomputes the sum of elements from the start of the array to each index, enabling O(1) range sum queries.

Why This Matters in Interviews

Prefix sum is important because:

• Range queries: Efficiently answer sum queries on subarrays
• Optimization: Reduces O(n) queries to O(1)
• Problem patterns: Many problems can use prefix sums
• Foundation: Basis for more advanced techniques (2D prefix sum, difference array)

Interviewers use prefix sum to assess your ability to optimize solutions and your understanding of preprocessing techniques.

Core Concepts

• Prefix sum array: Cumulative sum from start to each index
• Range sum query: Sum of subarray [i, j] = prefix[j] - prefix[i-1]
• Preprocessing: O(n) time to build prefix array
• Query time: O(1) after preprocessing
• 2D prefix sum: Extension to matrices
• Difference array: Inverse operation for range updates

Detailed Explanation

Basic Prefix Sum

1class PrefixSum {
2  private prefix: number[];
3  
4  constructor(arr: number[]) {
5    this.prefix = new Array(arr.length + 1);
6    this.prefix[0] = 0;
7    
8    for (let i = 0; i < arr.length; i++) {
9      this.prefix[i + 1] = this.prefix[i  arri

Example

// Array: [1, 3, 5, 7, 9]
// Prefix: [0, 1, 4, 9, 16, 25]

// Sum of [1, 3] (indices 1 to 3):
// prefix[4] - prefix[1] = 16 - 1 = 15
// Which is: 3 + 5 + 7 = 15 ✓

Examples

Subarray Sum Equals K

1function subarraySum(nums: number[], k: number): number {
2  const prefixSum = new Map<number, number>();
3  prefixSum.set(0, 1); // Empty subarray has sum 0
4  let sum = 0;
5  let count = 0;
6  
7  for (const num of nums) {
8    sum += num;
9    const needed = sum - k;
10    
11    // If prefix sum "needed" exists, we found subarray

Maximum Size Subarray Sum Equals K

1function maxSubArrayLen(nums: number[], k: number): number {
2  const prefixSum = new Map<number, number>();
3  prefixSum.set(0, -1); // Sum 0 at index -1
4  let sum = 0;
5  let maxLength = 0;
6  
7  for (let i = 0; i < nums.length; i++) {
8    sum += nums[i];

2D Prefix Sum

1class PrefixSum2D {
2  private prefix: number[][];
3  
4  constructor(matrix: number[][]) {
5    const rows = matrix.length;
6    const cols = matrix[0].length;
7    this.prefix = Array(rows + 1).fill(null).map(() => Array(cols + 1).fill(0)

Difference Array (Range Updates)

1class DifferenceArray {
2  private diff: number[];
3  
4  constructor(length: number) {
5    this.diff = new Array(length).fill(0);
6  }
7  
8  // Update range [left, right] by adding value
9  updateRange(left: number, right: number, value: number): void {
10    this.diff[left] += value;
11    if (right + 1 < difflength

Common Pitfalls

• Off-by-one errors: Wrong indices in range queries. Fix: Be careful with inclusive/exclusive
• Not initializing: Forgetting prefix[0] = 0. Fix: Always initialize first element
• Index confusion: 0-indexed vs 1-indexed. Fix: Be consistent
• Not handling negatives: Prefix sum can be negative. Fix: Handle in hash map lookups
• Memory issues: Large arrays consume memory. Fix: Consider space-time trade-offs

Interview Questions

Beginner

Q: What is prefix sum and how does it help with range sum queries?

A:

Prefix Sum is a precomputed array where each element stores the sum of all elements from the start to that index.

How it works:

// Original array
arr = [1, 3, 5, 7, 9]

// Prefix sum array
prefix = [0, 1, 4, 9, 16, 25]
         // prefix[i] = sum of arr[0..i-1]

Range Sum Query:

// Sum of subarray [i, j] (inclusive)
sum = prefix[j + 1] - prefix[i]

// Example: Sum of [1, 3]
// prefix[4] - prefix[1] = 16 - 1 = 15
// Which is: 3 + 5 + 7 = 15 ✓

Benefits:

• Preprocessing: O(n) time to build
• Query: O(1) time per query
• Multiple queries: Very efficient for many queries

Example:

Without prefix sum: O(n) per query
With prefix sum: O(1) per query (after O(n) preprocessing)

Intermediate

Q: Use prefix sum to find the number of subarrays with sum equal to k. Handle negative numbers.

A:

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

// Example:
// nums = [1, 1, 1], k = 2
// 
// i=0: sum=1, needed=-1, count=0, map={0:1, 1:1}
// i=1: sum=2, needed=0, count=1, map={0:1, 1:1, 2:1}
// i=2: sum=3, needed=1, count=2, map={0:1, 1:1, 2:1, 3:1}
// 
// Result: 2 subarrays ([1,1] and [1,1] from different positions)

// For maximum length subarray
function maxSubArrayLen(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, -1);
  let sum = 0;
  let maxLength = 0;
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    
    const needed = sum - k;
    if (prefixSum.has(needed)) {
      const length = i - prefixSum.get(needed)!;
      maxLength = Math.max(maxLength, length);
    }
    
    // Store first occurrence for maximum length
    if (!prefixSum.has(sum)) {
      prefixSum.set(sum, i);
    }
  }
  
  return maxLength;
}

Key insight:

• Prefix sum difference: If prefix[j] - prefix[i] = k, then subarray [i+1, j] has sum k
• Hash map lookup: Store prefix sums to find needed value in O(1)
• Handles negatives: Works with negative numbers

Senior

Q: Design a system to answer range sum queries on a 2D matrix with millions of queries. Handle matrix updates and optimize for both query and update operations.

A:

class RangeSumQuery2D {
  private prefix: number[][];
  private matrix: number[][];
  private rows: number;
  private cols: number;
  
  constructor(matrix: number[][]) {
    this.matrix = matrix;
    this.rows = matrix.length;
    this.cols = matrix[0].length;
    this.buildPrefix();
  }
  
  private buildPrefix(): void {
    this.prefix = Array(this.rows + 1)
      .fill(null)
      .map(() => Array(this.cols + 1).fill(0));
    
    for (let i = 0; i < this.rows; i++) {
      for (let j = 0; j < this.cols; j++) {
        this.prefix[i + 1][j + 1] =
          this.matrix[i][j] +
          this.prefix[i][j + 1] +
          this.prefix[i + 1][j] -
          this.prefix[i][j];
      }
    }
  }
  
  // O(1) query
  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]
    );
  }
  
  // O(rows * cols) update - rebuild prefix
  update(row: number, col: number, val: number): void {
    const diff = val - this.matrix[row][col];
    this.matrix[row][col] = val;
    
    // Update prefix sums
    for (let i = row + 1; i <= this.rows; i++) {
      for (let j = col + 1; j <= this.cols; j++) {
        this.prefix[i][j] += diff;
      }
    }
  }
  
  // Optimized with Binary Indexed Tree (Fenwick Tree)
  class RangeSumQuery2DOptimized {
    private bit: number[][];
    private matrix: number[][];
    
    constructor(matrix: number[][]) {
      this.matrix = matrix;
      this.bit = Array(matrix.length + 1)
        .fill(null)
        .map(() => Array(matrix[0].length + 1).fill(0));
      
      // Build BIT
      for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
          this.updateBIT(i, j, matrix[i][j]);
        }
      }
    }
    
    private updateBIT(row: number, col: number, delta: number): void {
      for (let i = row + 1; i <= this.matrix.length; i += i & -i) {
        for (let j = col + 1; j <= this.matrix[0].length; j += j & -j) {
          this.bit[i][j] += delta;
        }
      }
    }
    
    private queryBIT(row: number, col: number): number {
      let sum = 0;
      for (let i = row + 1; i > 0; i -= i & -i) {
        for (let j = col + 1; j > 0; j -= j & -j) {
          sum += this.bit[i][j];
        }
      }
      return sum;
    }
    
    sumRegion(row1: number, col1: number, row2: number, col2: number): number {
      return (
        this.queryBIT(row2, col2) -
        this.queryBIT(row1 - 1, col2) -
        this.queryBIT(row2, col1 - 1) +
        this.queryBIT(row1 - 1, col1 - 1)
      );
    }
    
    update(row: number, col: number, val: number): void {
      const diff = val - this.matrix[row][col];
      this.matrix[row][col] = val;
      this.updateBIT(row, col, diff);
    }
    
    // Time: O(log m * log n) for both query and update
  }
  
  // For very sparse updates: Lazy propagation
  class RangeSumQuery2DLazy {
    private prefix: number[][];
    private updates: Array<{r1: number, c1: number, r2: number, c2: number, val: number}>;
    
    constructor(matrix: number[][]) {
      this.prefix = this.buildPrefix(matrix);
      this.updates = [];
    }
    
    sumRegion(row1: number, col1: number, row2: number, col2: number): number {
      // Apply pending updates
      this.applyUpdates();
      
      return (
        this.prefix[row2 + 1][col2 + 1] -
        this.prefix[row1][col2 + 1] -
        this.prefix[row2 + 1][col1] +
        this.prefix[row1][col1]
      );
    }
    
    updateRange(r1: number, c1: number, r2: number, c2: number, val: number): void {
      // Lazy update: store for later
      this.updates.push({ r1, c1, r2, c2, val });
      
      // Apply if too many pending
      if (this.updates.length > 100) {
        this.applyUpdates();
      }
    }
    
    private applyUpdates(): void {
      // Apply all pending updates to prefix
      // Rebuild prefix if needed
      this.updates = [];
    }
  }
}

Features:

1. 2D prefix sum: O(1) queries, O(rows*cols) updates
2. Binary Indexed Tree: O(log m * log n) for both
3. Lazy updates: Batch updates for efficiency
4. Optimization: Choose based on query/update ratio

• Prefix sum: Precompute cumulative sums for O(1) range queries
• Range sum: prefix[j+1] - prefix[i] gives sum of [i, j]
• Subarray problems: Use with hash map to find subarrays with given sum
• 2D prefix sum: Extend to matrices for rectangle queries
• Difference array: Inverse operation for range updates
• Time complexity: O(n) preprocessing, O(1) queries
• Applications: Range queries, subarray problems, matrix queries