Topic Overview

Prefix Sum

Master prefix sum technique: precompute cumulative sums to answer range sum queries in O(1) time after O(n) preprocessing.

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

class PrefixSum {
  private prefix: number[];
  
  constructor(arr: number[]) {
    this.prefix = new Array(arr.length + 1);
    this.prefix[0] = 0;
    
    for (let i = 0; i < arr.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + arr[i];
    }
  }
  
  // Sum of subarray [left, right] (inclusive)
  rangeSum(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
  
  // Sum from start to index
  sumTo(index: number): number {
    return this.prefix[index + 1];
  }
}

// Time: O(n) preprocessing, O(1) query
// Space: O(n)

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

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;
    const needed = sum - k;
    
    // If prefix sum "needed" exists, we found subarray
    if (prefixSum.has(needed)) {
      count += prefixSum.get(needed)!;
    }
    
    // Update prefix sum count
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

// Time: O(n)
// Space: O(n)

Maximum Size Subarray Sum Equals 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 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 of prefix sum
    if (!prefixSum.has(sum)) {
      prefixSum.set(sum, i);
    }
  }
  
  return maxLength;
}

2D Prefix Sum

class PrefixSum2D {
  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];
      }
    }
  }
  
  // Sum of rectangle from (r1, c1) to (r2, c2) inclusive
  rangeSum(r1: number, c1: number, r2: number, c2: number): number {
    return (
      this.prefix[r2 + 1][c2 + 1] -
      this.prefix[r1][c2 + 1] -
      this.prefix[r2 + 1][c1] +
      this.prefix[r1][c1]
    );
  }
}

// Time: O(rows * cols) preprocessing, O(1) query
// Space: O(rows * cols)

Difference Array (Range Updates)

class DifferenceArray {
  private diff: number[];
  
  constructor(length: number) {
    this.diff = new Array(length).fill(0);
  }
  
  // Update range [left, right] by adding value
  updateRange(left: number, right: number, value: number): void {
    this.diff[left] += value;
    if (right + 1 < this.diff.length) {
      this.diff[right + 1] -= value;
    }
  }
  
  // Get final array after all updates
  getArray(): number[] {
    const result: number[] = [];
    let current = 0;
    
    for (const delta of this.diff) {
      current += delta;
      result.push(current);
    }
    
    return result;
  }
}

// Usage
const diff = new DifferenceArray(5);
diff.updateRange(1, 3, 5);  // Add 5 to indices 1-3
diff.updateRange(2, 4, 3);  // Add 3 to indices 2-4
const result = diff.getArray();
// Result: [0, 5, 8, 8, 3, 0]

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

Key Takeaways

  • 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

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.