LeetCode Problem 303
Link of the Problem to try -: Link
Given an integer array nums, handle multiple queries of the following type:
- Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (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] <= 1050 <= left <= right < nums.length- At most
104calls will be made tosumRange.
Solution:
Efficient Range Sum Queries using Prefix Sums
While this problem may initially seem challenging, the solution is remarkably elegant. The key is to shift the heavy lifting from the query phase to the initialization phase using a Prefix Sum array.
The Strategy
Instead of calculating the sum from scratch every time a range is requested, we use two steps:
- The Constructor: During initialization, we create a Prefix Sum array. Each index i in this new array stores the cumulative sum of all elements from the beginning of the original array up to i.
- The sumRange Method: To find the sum between a left and right pointer, we simply use the precalculated values. The sum of the range is calculated as:
- Sum(left, right) = PrefixSum[right] - PrefixSum[left - 1]
Why This is Better
By pre-calculating the sums in the constructor, we transform the sumRange operation from a slow O(n) search into a lightning-fast O(1) constant-time lookup. This approach is highly efficient for applications where the data remains the same but the number of queries is high.
Code:
class NumArray {
int[] ans ;
public NumArray(int[] nums) {
ans = new int[nums.length];
int pre =0;
for(int i=0;i<nums.length;i++){
pre += nums[i];
ans[i] = pre;
}
}
public int sumRange(int left, int right) {
if(left == 0) return ans[right];
return ans[right]-ans[left-1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(left,right);
*/
