Working with Prefix Sum

1. Building Prefix Sum Array

Step	Description	Code Example
Initialization	Start with the first element of the input array as the first element of prefix sum array.	`const arr = [1, 2, 3, 4, 5];<br>const prefix = [arr[0]];`
Iteration	For each subsequent element, add the current element to the previous prefix sum.	`for (let i = 1; i < arr.length; i++) {<br> prefix[i] = prefix[i - 1] + arr[i];<br>}`
Result	The prefix sum array contains cumulative sums up to each index.	`console.log(prefix); // [1, 3, 6, 10, 15]`

Note: The prefix sum array can be used to efficiently compute range sums.

2. Computing Range Sum Queries

Operation	Description	Time Complexity	Space Complexity
Naive Approach	Compute sum for each query by iterating from start to end index.	O(n) per query	O(1)
Prefix Sum	Precompute prefix sums to answer queries in O(1).	O(1) per query	O(n)

Example: Prefix Sum Implementation

const nums = [1, 3, 5, 7, 9];
let prefixSum = [0];

// Build prefix sum array
for (let i = 0; i < nums.length; i++) {
  prefixSum[i + 1] = prefixSum[i] + nums[i];
}

// Range sum from index 1 to 3
const rangeSum = prefixSum[4] - prefixSum[1]; // 7 + 9 = 16

Note: The prefix sum array is 1-indexed to simplify range queries.

3. Finding Subarray Sum Equals K

Given an array of integers and a target sum k, find the number of subarrays whose sum equals k.

Approach	Description	Time Complexity	Space Complexity
Brute Force	Check all possible subarrays and calculate their sums.	`O(n^2)`	`O(1)`
Prefix Sum + Hash Map	Use prefix sums and a hash map to store counts of prefix sums. For each element, check if `prefixSum - k` exists in the map.	`O(n)`	`O(n)`

Example: Using Prefix Sum with Hash Map

function subarraySum(nums, k) {
    let count = 0;
    let prefixSum = 0;
    const sumMap = new Map();
    sumMap.set(0, 1); // Initialize with 0 to handle subarrays starting from index 0

    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        const target = prefixSum - k;
        if (sumMap.has(target)) {
            count += sumMap.get(target);
        }
        sumMap.set(prefixSum, (sumMap.get(prefixSum) || 0) + 1);
    }

    return count;
}

// Example usage:
const nums = [1, 2, 3, -1, 2];
const k = 3;
console.log(subarraySum(nums, k)); // Output: 3

Note: The hash map stores the frequency of prefix sums encountered so far. For each element, we check if prefixSum - k has been seen before. If yes, it means there are subarrays ending at the current index with sum k.

4. Finding Continuous Subarray Sum

Given an array of integers and a target sum, find a contiguous subarray that sums to the target.

Approach	Description	Time Complexity	Space Complexity
Brute Force	Check all possible subarrays using nested loops.	O(n²)	O(1)
Prefix Sum + Hash Map	Use prefix sums and a hash map to store previous sums for O(1) lookup.	O(n)	O(n)

Example: Prefix Sum with Hash Map

function subarraySum(nums, target) {
    const prefixSum = new Map();
    prefixSum.set(0, -1); // Initialize with sum 0 at index -1
    let sum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (prefixSum.has(sum - target)) {
            return [prefixSum.get(sum - target) + 1, i];
        }
        prefixSum.set(sum, i);
    }
    
    return [];
}

Note: The prefix sum approach works best when all elements are non-negative or when we're looking for a specific sum. For arrays with negative numbers, the hash map approach is preferred.

5. Finding Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Input	Output	Description
nums = [1, 2, 3, 4]	`[24, 12, 8, 6]`	Each element is the product of all other elements
nums = [2, 3, 4, 5]	`[60, 40, 30, 24]`	Product of all elements except self

Example: Product of Array Except Self

function productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    // First pass: compute left products
    result[0] = 1;
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // Second pass: compute right products and multiply
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

// Example usage:
const nums = [1, 2, 3, 4];
console.log(productExceptSelf(nums)); // Output: [24, 12, 8, 6]

Note: The solution avoids using division and runs in O(n) time with O(1) extra space (not counting the output array).

6. Finding Maximum Size Subarray Sum

Property	Description	Notes
maxSubarraySum	Maximum sum of any contiguous subarray	Uses Kadane's algorithm variant
maxSubarraySize	Length of the subarray with maximum sum	Can be computed alongside maxSum

Example: Finding Maximum Size Subarray Sum

function maxSubarraySum(arr) {
  let maxSum = -Infinity;
  let currentSum = 0;
  let maxSize = 0;

  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];
    if (currentSum > maxSum) {
      maxSum = currentSum;
      maxSize = i + 1;
    }
    if (currentSum < 0) {
      currentSum = 0;
    }
  }

  return { maxSum, maxSize };
}

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const result = maxSubarraySum(nums);
console.log(result); // { maxSum: 6, maxSize: 4 }

Note: This approach uses Kadane's algorithm to find the maximum sum subarray and tracks its size.

7. Finding Contiguous Array with Equal 0s and 1s

This problem involves finding the longest contiguous subarray with an equal number of 0s and 1s.

Approach	Description	Time Complexity	Space Complexity
Prefix Sum with HashMap	Transform 0s to -1s, compute prefix sums, and use a hash map to track first occurrence of each sum.	`O(n)`	`O(n)`

Example: Finding Subarray with Equal 0s and 1s

function findMaxLength(nums) {
    const sumIndexMap = new Map();
    sumIndexMap.set(0, -1); // Initialize with sum 0 at index -1
    let maxLength = 0;
    let prefixSum = 0;

    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i] === 0 ? -1 : 1;
        if (sumIndexMap.has(prefixSum)) {
            const length = i - sumIndexMap.get(prefixSum);
            maxLength = Math.max(maxLength, length);
        } else {
            sumIndexMap.set(prefixSum, i);
        }
    }

    return maxLength;
}

// Example usage:
const nums = [0, 1, 0];
console.log(findMaxLength(nums)); // Output: 2

Note: The key insight is to treat 0s as -1s, so that any subarray with equal 0s and 1s will have a prefix sum of 0.

8. Computing 2D Prefix Sum

Operation	Description	Time Complexity	Space Complexity
Preprocessing	Build 2D prefix sum array from input matrix	`O(m × n)`	`O(m × n)`
Range Query	Get sum of submatrix from (r1, c1) to (r2, c2)	`O(1)`	`O(1)`

Example: 2D Prefix Sum Construction

function build2DPrefixSum(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const prefix = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      prefix[i][j] = matrix[i-1][j-1] + 
                         prefix[i-1][j] + 
                         prefix[i][j-1] - 
                         prefix[i-1][j-1];
    }
  }

  return prefix;
}

Example: Range Sum Query

function rangeSum(prefix, r1, c1, r2, c2) {
  return prefix[r2+1][c2+1] - 
         prefix[r1][c2+1] - 
         prefix[r2+1][c1] + 
         prefix[r1][c1];
}

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

const prefix = build2DPrefixSum(matrix);
console.log(rangeSum(prefix, 0, 0, 1, 1)); // Sum of 1+2+4+5 = 12

Note: The prefix sum array is 1-indexed to simplify boundary checks. The original matrix indices are offset by 1 when accessing the prefix array.

9. Implementing Range Sum Query 2D

Operation	Description	Time Complexity	Space Complexity
RangeSumQuery2D	Preprocesses a 2D matrix to support O(1) range sum queries	O(mn)	O(mn)

Example: Range Sum Query 2D Implementation

class RangeSumQuery2D {
  constructor(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    this.prefixSum = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; 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 rsq2d = new RangeSumQuery2D(matrix);
console.log(rsq2d.sumRegion(2, 1, 4, 3)); // Output: 8

Note: The prefix sum array is 1-indexed to simplify the calculation. The sumRegion method uses inclusion-exclusion principle to compute the sum of a rectangular region.

10. Finding Subarray Sums Divisible by K

Use the prefix sum technique with modular arithmetic to find subarrays whose sums are divisible by a given integer K.

Property	Description	Usage
prefixSum[i]	Sum of elements from index 0 to i	Used for calculating subarray sums
mod[i]	Modulo of prefixSum[i] by K	Determines equivalence classes for sums

Example: Subarray Sums Divisible by K

const nums = [4, 5, 0, -2, -3, 1];
const K = 5;

let prefixSum = 0;
let count = 0;
let modMap = new Map();
modMap.set(0, 1); // Initialize with 0

for (let i = 0; i < nums.length; i++) {
    prefixSum += nums[i];
    let mod = ((prefixSum % K) + K) % K;
    if (modMap.has(mod)) {
        count += modMap.get(mod);
    }
    modMap.set(mod, (modMap.get(mod) || 0) + 1);
}

console.log(count); // Output: 7

Note: The modulo operation is adjusted to handle negative numbers correctly by adding K before applying the modulo.

Key Points

If two prefix sums have the same modulo with K, their difference is divisible by K.
Use a hash map to store the frequency of each modulo value.
This approach reduces time complexity from O(n²) to O(n).

11. Finding Minimum Size Subarray Sum

Given an array of positive integers and a target sum, find the minimum length of a contiguous subarray whose sum is at least the target.

Property	Description	Example
Input	An array of positive integers and a target sum	`[2, 3, 1, 2, 4, 3]`, target = `7`
Output	Minimum length of subarray with sum >= target	`2` (subarray `[4, 3]`)

Example: Finding Minimum Size Subarray Sum

function minSubArrayLen(target, nums) {
    let left = 0;
    let sum = 0;
    let minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];

        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

// Example usage:
const nums = [2, 3, 1, 2, 4, 3];
const target = 7;
console.log(minSubArrayLen(target, nums)); // Output: 2

Note: This approach uses the sliding window technique to achieve O(n) time complexity.

12. Finding Maximum Average Subarray

Given an array of integers and a subarray length k, find the contiguous subarray of length k with the maximum average value.

Property	Description	Example
array	Input array of integers	`[1, 4, 2, 10, 23, 3, 1, 0, 5]`
k	Length of the subarray to consider	`4`
maxAverage	Maximum average of any subarray of length k	`7.75`

Example: Finding Maximum Average Subarray

function maxAverageSubarray(arr, k) {
  let sum = 0;
  
  // Calculate sum of first window
  for (let i = 0; i < k; i++) {
    sum += arr[i];
  }
  
  let maxAvg = sum / k;
  
  // Slide the window and update max average
  for (let i = k; i < arr.length; i++) {
    sum = sum - arr[i - k] + arr[i];
    maxAvg = Math.max(maxAvg, sum / k);
  }
  
  return maxAvg;
}

// Example usage
const arr = [1, 4, 2, 10, 23, 3, 1, 0, 5];
const k = 4;
console.log(maxAverageSubarray(arr, k)); // Output: 7.75

Note: This approach uses the sliding window technique to efficiently compute the maximum average subarray in O(n) time complexity.