LeetCode - 303. Range Sum Query - Immutable

Thoughts:

I choose to use the prefix sum algorithm to solve this problem. So I can calculate the sum of elements in a range of an array in O(1). Rather than iterate elements in O(n) every time.

What is Prefix Sum?:

Prefix sum is an algorithm that allows me to calculate the sum of elements in a range of an array in O(1). But it requiers O(n) when initialize the prefix sum array. So, if the array is mutable, it will take more time to update and recalculate the prefix sum array. Then it will be O(n) for each update, because this algorithm is not suitable for mutable arrays.

Thoughts visuzlization:

origin: [-2, 0, 3, -5, 2]

prefixSums: [-2, -2, 1, -4, -2]

prefixSums[0]: -2
prefixSums[1]: -2 + 0 = -2
prefixSums[2]: -2 + 0 + 3 = 1
prefixSums[3]: -2 + 0 + 3 + -5 = -4
prefixSums[4]: -2 + 0 + 3 + -5 + 2 = -2

sumRange(2, 4): prefixSums[4] - prefixSums[1] = -2 - (-2) = 0
(need to include the left and right elements, so I need to substract the left index by 1)

sumRange(0, 3): prefixSums[3] - 0 = -4
(prefixSums[-1] is out of boundary, so it is 0)

Code:

/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
  this.prefixSums = [];
  let currSum = 0;
  for (let num of nums) {
    currSum += num;
    this.prefixSums.push(currSum);
  }
};

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
  const l = left < 1 ? 0 : this.prefixSums[left - 1];
  const r = this.prefixSums[right];
  return r - l;
};

Reference

Original link