Prefix Sum

The Prefix Sum is a technique used to simplify the computation of the sum of elements in a subarray. It is particularly useful in problems involving multiple queries about subarray sums, where recalculating the sum from scratch each time would be inefficient.

How Prefix Sum Works

The idea behind the prefix sum is to preprocess an array so that each element at index i in a new array represents the sum of elements from the start of the array up to index i.

Pseudocode

Image Src : Medium

Here’s the pseudocode to compute the prefix sum array:

// Function to compute the prefix sum array
function computePrefixSum(arr) {
    const prefixSum = new Array(arr.length).fill(0);
    prefixSum[0] = arr[0];
    
    for (let i = 1; i < arr.length; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    
    return prefixSum;
}

// Function to calculate the sum of elements between indices l and r
function subarraySum(prefixSum, l, r) {
    if (l === 0) return prefixSum[r];
    return prefixSum[r] - prefixSum[l - 1];
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const prefixSum = computePrefixSum(arr);

console.log("Prefix Sum Array:", prefixSum); // Output: [1, 3, 6, 10, 15]

const sum = subarraySum(prefixSum, 1, 3);
console.log("Sum of subarray arr[1..3]:", sum); // Output: 9

Prefix Sum on 2D Grid

Prefix Sum is a simple yet powerful technique to calculate the sum of elements in a submatrix of a 2D grid efficiently. By precomputing the sums of all submatrices that start at the top-left corner and extend to any other cell, we can quickly answer range sum queries.

Introduction

Given a 2D matrix, we want to perform two types of operations efficiently:

1. Precompute: Precompute the sum of elements for all submatrices.
2. Range Query: Find the sum of elements in a submatrix defined by its top-left and bottom-right corners.

Prefix Sum Array

The Prefix Sum Array for a 2D grid is constructed by summing all the elements from the top-left corner (0, 0) to any cell (i, j). The value at any cell (i, j) in the prefix sum array represents the sum of all elements from (0, 0) to (i, j) in the original matrix.

Prefix Sum Formula

To calculate the sum of elements in any submatrix defined by (row1, col1) to (row2, col2), we use the following formula:

• Prefix[row2][col2]: Sum of elements from (0, 0) to (row2, col2).
• - Prefix[row1-1][col2]: Subtract the sum above row1.
• - Prefix[row2][col1-1]: Subtract the sum left of col1.
• + Prefix[row1-1][col1-1]: Add back the overlapping top-left region.

Implementation

Let's see how to implement a 2D prefix sum in JavaScript.

class NumMatrix {
    constructor(matrix) {
        const rows = matrix.length;
        const cols = matrix[0].length;
        this.prefixSum = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));

        // Compute the prefix sum matrix
        for (let i = 1; i <= rows; i++) {
            for (let j = 1; j <= cols; j++) {
                this.prefixSum[i][j] = matrix[i - 1][j - 1] 
                                       + this.prefixSum[i - 1][j]
                                       + this.prefixSum[i][j - 1]
                                       - this.prefixSum[i - 1][j - 1];
            }
        }
    }

    sumRegion(row1, col1, row2, col2) {
        return this.prefixSum[row2 + 1][col2 + 1]
             - this.prefixSum[row1][col2 + 1]
             - this.prefixSum[row2 + 1][col1]
             + this.prefixSum[row1][col1];
    }
}

// Example usage:
const matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5]
];

const numMatrix = new NumMatrix(matrix);
console.log(numMatrix.sumRegion(2, 1, 4, 3)); // Output: 8
console.log(numMatrix.sumRegion(1, 1, 2, 2)); // Output: 11
console.log(numMatrix.sumRegion(1, 2, 2, 4)); // Output: 12

Prefix Sum with HashMap Pattern

Explanation

The Prefix Sum with HashMap technique is useful for efficiently solving subarray-related problems where you need to find subarrays with a specific property, such as a target sum or certain divisibility conditions.

Approach

1. Maintain a running sum (prefix sum) while traversing the array.
2. Use a HashMap (or an object in JavaScript) to store the frequency of prefix sums encountered so far.
3. The key insight is that if the difference between the current prefix sum and a target value has been seen before, then the subarray between these points sums to the target.

Key Steps

• Initialize a HashMap to store (prefix_sum, count) pairs.
• Track the current prefix sum as you iterate through the array.
• Check if the difference (prefix_sum - target) exists in the HashMap, which would indicate a subarray with the desired sum.
• Update the HashMap with the current prefix sum after each iteration.

Problems

• Subarray Sum Equals K
• Subarray Sums Divisible by K
• Binary Subarrays With Sum
• Count of Interesting Subarrays
• Continuous Subarray Sum
• Minimum Operations to Reduce X to Zero
• Contiguous Array
• Count Number of Bad Pairs
• Maximum Size Subarray Sum Equals K

Example Code (JavaScript)

Here’s an example of the Subarray Sum Equals K problem using Prefix Sum with HashMap:

function subarraySum(nums, k) {
  let prefixSum = 0;
  let count = 0;
  const map = new Map();
  map.set(0, 1);  // Initialize with prefix sum 0

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

  return count;
}