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.
Input: nums = [-2, 0, 3, -5, 2, -1]
Query 1: [0, 2]
Output: 1
Explanation: sum of elements from index 0 and index 2 are -2 + 0 +3 = 1
Query 2: [2, 5]
Output: -1
Explanation: sum of elements from index 2 and index 5 are 3 - 5 + 2 -1 = -1
Contents
- Solution 1 - Iterate through elements from left index to right index
- Solution 2 - Prepare prefix-sum as part of constructor initialization
In this approach, we are going to assign nums input array passed to the constructor to a class variable arr, then
in the sumRange(int left, int right) method, we will loop through from left index to right index (inclusive)
and compute sum.
public class NumArray {
private final int[] arr;
public NumArray(int[] nums) {
this.arr = nums;
}
public int sumRange(int left, int right) {
int sum = 0;
for(int i=left; i<=right; i++) { // i<= right - because problem says right index inclusive
sum += arr[i];
}
return sum;
}
}
Complexity Analysis:
Time complexity: O(n * m) where n is the input array nums length, and m is the number of times
sumRange will get called.
Everytime sumRange is called, we are going through array from left to right indexes.
Space complexity: O(n) - input array passed to constructor is maintained in a class variable.
In this approach, we are going to pre compute prefix sum inside constructor, so that we can return sumRange in constant time.
We are going to implement prefix sum first. For example if if the input array is
[1 ,2 ,3 ,4 ,5] then the prefix sum array will be [1, 3, 6, 10, 15], what we did is at every index i,
we took sum of elements before current element and added current element to that.
| input array |
1 |
2 |
3 |
4 |
5 |
| prefix sum |
1 |
1 +2 = 3 |
3 +3 = 6 |
6 +4 = 10 |
10 +5 = 15 |
Once we have the pre computed prefix sum, then we will compute sumRange using:
sum = prefixsum [right] - prefixsum[left-1];
At right index of prefix sum array, it contains the sum from index 0 to index right,
since we want sum from left index to right index, we can subtract the value before left-1 index.
(There is one edge case if left = 0 then, we dont need to subtract left-1 as it is out of bounds or we can subtract 0)
public class NumArray {
private final int[] arr;
public NumArray(int[] nums) {
arr = new int[nums.length];
arr[0] = nums[0];
for(int i=1; i<nums.length; i++) {
arr[i] = nums[i] + arr[i-1];
}
}
public int sumRange(int left, int right) {
return arr[right] - (left ==0 ? 0 : arr[left-1]);
}
}
Complexity Analysis:
Time complexity: O(n) where n is the input array nums length, since we are looping through input array only once
when computing prefix sum array.
Everytime sumRange is called, it returns in constant time.
Space complexity: O(n) - space used by the prefix sum array.
Above implementations source code can be found at
GitHub link for Java code