Skip to main content

Range Sum Query - Immutable

Problem​

Given an integer array nums, handle multiple queries of the following type:

  1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

 

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

 

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Solution​

class NumArray {
    constructor(nums) {
        this.nums = nums;
        this.dp = [0];
        for (let i = 0; i < nums.length; i++) {
            this.dp.push(nums[i] + this.dp[i]);
        }
    }

    sumRange(left, right) {
        return this.dp[right + 1] - this.dp[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */

We will implement a DP solution. Let dp[i] be the sum of nums[0:i] (note that dp[0] = 0 since num[0:0] is the empty array). Observe that the sum of nums[i:j] is dp[j] - dp[i].

For example, if nums = [1, 2, 3], then dp = [0, 1, 3, 6], and so sumRange(1, 2) = dp[3] - dp[1] = 6 - 1 = 5, which is the desired result (ie. sum of nums[1:3] = 5).