Given an integer array nums, handle multiple queries of the following type:
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
Bruteforce approach
The bruteforce solution for this question would , when ever a sumRange query is called compute the sum from given start and end index and return the sum.
Time complexity for this approach will be O(number of time function called * n) - here we are computing the sum for every query
Optimized solution
Instead of calculating the sum for every query , we can have a precomputed sum array , where prefix[i] will be the sum of array from 0 to i . Using this precomputed array for every query we can return the sum in O(1) time complexity.
Psuedo code
- Created a prefix array of size of the given array.
- Compute the prefix array where prefix[i] will give the sum of array from 0 to i(inclusive)
- Now for every query requested , do the following:
- If left is 0 , directly return prefix[right]
- else return prefix[right] - prefix[left-1] - because prefix of right will be sum of original array from 0 to right , so we have to substract sum of array from 0 to left-1 from prefix[right]
Code
class NumArray:
def __init__(self, nums: List[int]):
self.length = len(nums)
self.prefixsum = [0]*self.length
self.prefixsum[0] = nums[0]
for i in range(1,self.length):
self.prefixsum[i] = self.prefixsum[i-1]+nums[i]
self.total = self.prefixsum[-1]
def sumRange(self, left: int, right: int) -> int:
if left == 0:
return self.prefixsum[right]
return self.prefixsum[right]-self.prefixsum[left-1]
Please like this post and share if you found this post helpful.
Top comments (0)