Prefix Sum Problem Solving Using JavaScript

The prefix sum (or cumulative sum) technique is a powerful approach for solving array-related problems efficiently, especially those involving range sum queries. Here’s a guide with 5 top problems solvable using prefix sums in JavaScript.

What is Prefix Sum?

A prefix sum is a technique where we create an auxiliary array where each element at index i represents the sum of all elements from the start of the original array up to index i.

function createPrefixSum(arr) {
  const prefix = new Array(arr.length);
  prefix[0] = arr[0];
  for (let i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
  }
  return prefix;
}

Top 5 Prefix Sum Problems

1. Range Sum Query (Immutable)

Problem: Given an integer array nums, handle multiple queries of the type: calculate the sum of elements between indices left and right inclusive.

Solution:

class NumArray {
  constructor(nums) {
    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, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

2. Find Pivot Index

Problem: Find the pivot index where the sum of numbers to the left equals the sum of numbers to the right.

Solution:

function pivotIndex(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    if (leftSum === total - leftSum - nums[i]) {
      return i;
    }
    leftSum += nums[i];
  }
  return -1;
}

3. Subarray Sum Equals K

Problem: Find the total number of continuous subarrays whose sum equals to k.

Solution:

function subarraySum(nums, k) {
  const prefixSum = { 0: 1 };
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    if (prefixSum[sum - k]) {
      count += prefixSum[sum - k];
    }
    prefixSum[sum] = (prefixSum[sum] || 0) + 1;
  }
  return count;
}

4. Maximum Subarray (Kadane’s Algorithm)

Problem: Find the contiguous subarray with the largest sum.

Solution:

function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

5. Product of Array Except Self

Problem: Return an array where each element is equal to the product of all other elements in the array.

Solution:

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);
  let left = 1,
    right = 1;

  for (let i = 0; i < n; i++) {
    result[i] *= left;
    left *= nums[i];

    result[n - 1 - i] *= right;
    right *= nums[n - 1 - i];
  }
  return result;
}

When to Use Prefix Sum

• Range sum queries (sum between indices)
• Problems involving cumulative operations
• Finding equilibrium points
• Subarray problems (sum/product)
• Problems that can be optimized from O(n²) to O(n)

Prefix sums are particularly useful when you need to answer many range queries on an array that remains static (doesn’t change between queries).