Range Sum Query - Immutable
Problem Statement
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]).
Examples:
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);
numArray.sumRange(2, 5);
numArray.sumRange(0, 5);
For the first input sumRange(0,2), we have to output the sum of values present in the nums array from index 0 to index 2.
Hence sumRange(0,2)= (-2) + 0 + 3 = 1. Therefore 1 will be the output
Similarly for the the second input sumRange(2,5), the output will be : -1
sumRange(2,5)= 3 + (-5) + 2 + (-1) = -1
Similarly , for the third input sumRange(0,5), the output will be : -3
sumRange(0,5)=(-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Input : ["NumArray", "sumRange", "sumRange", "sumRange"]
[[[1, 2, 3, 4, 5, 6]], [0, 1], [1,4], [0, 5]]
Output: [null, 3, 14, 21]
Explanation
NumArray numArray = new NumArray([1,2,3,4,5,6]);
numArray.sumRange(0, 1);
numArray.sumRange(1, 4);
numArray.sumRange(0, 5);
For the first input sumRange(0,1), we have to output the sum of values present in the nums array from index 0 to index 1.Hence sumRange(0,2)= 1 + 2= 3.
Therefore 3 will be the output
Similarly for the the second input sumRange(1,4), the output will be : 14
sumRange(1,4)= 2 + 3 + 4 + 5
Similarly , for the third input sumRange(0,5), the output will be : 21
sumRange(0,5)= 1 + 2 + 3 + 4 + 5 + 6 = 21
Constraints:
1 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= left <= right < nums.length
At most 104 calls will be made to sumRange
Basic Intuition to solve the problem:
The first very basic solution that comes to mind is that we can explicitly calculate the sum of the values from index left to index right, store it in the sum variable, and output our calculated sum. With this, the idea, of a brute-force approach comes into the picture.
Brute Force Approach
The brute force approach suggests that we can run a loop from index left to index right and calculate the sum for every sumRange (left, right) function call. We can store the sum in an answer variable and will output it.
Let’s dry-run the brute force approach on sample test case 1
- The first input is “NumArray” which means we just output the NumArray on which we will perform the sumRange(left, right) operation, now the “NumArray is already given along with the input so we don’t have to do anything with this.
- The second input is the sumRange(left, right) function which means now we have to calculate the sum of values from index left to index right. In the second input, we have given left=0 and right=3. We will create a sum variable that will store the sum of the values from index 0 to index 3 and add every value of the nums array which in this left-to-right interval. Therefore , sumRange(0,2)= -2+0+3 = 1
- The third input is the sumRange function and now we have to output the value of sumRange(2,5), here left = 2 and right =5. Therefore , sumRange(2,5) = 3 - 5 + 2 - 1 = -1
- Now, the fourth and the last input is also sumRange and now we have to calculate the sumRange(0,5). Here left=0 and right = 5. Therefore sumRange(0,5) = -2 + 0 + 3 + - 5 + 2 - 1 = -3.
Steps to write Code :
1. We will create an array arr which will be a reference to the nums array, no copy at all!
2. After creating the array arr, we will jump to method Method sumRange(int left, int right). This method takes two inputs: left and right, these are the start and ending indices of the segment in the array in which we have to calculate the sum.
3. Then by the Brute Method, we will calculate the sum by applying a loop from index left to index right.
Brute Force Code for All Languages
C++
class Solution {
public:
vector<int> &arr;
// Constructor that initializes the reference to nums array
Solution(vector<int> &nums) : arr(nums) {
// don't write anything in this
}
// Method to return the sum of elements between left and right (inclusive)
int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += arr[i];
}
return sum;
}
};Java
class Solution {
private int[] arr;
// Constructor that initializes the reference to nums array
public Solution(int[] nums) {
arr = nums;
}
// Method to return the sum of elements between left and right (inclusive)
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += arr[i];
}
return sum;
}
}Python
class Solution:
def __init__(self, nums):
# Initialize the reference to the nums array
self.arr = nums
# Method to return the sum of elements between left and right (inclusive)
def sumRange(self, left, right):
return sum(self.arr[left:right+1])Javascript
class Solution {
// Constructor that initializes the reference to nums array
constructor(nums) {
this.arr = nums;
}
// Method to return the sum of elements between left and right (inclusive)
sumRange(left, right) {
let sum = 0;
for (let i = left; i <= right; i++) {
sum += this.arr[i];
}
return sum;
}
}Time Complexity : O(n)
The class Solution has two methods that contribute to its overall time complexity:
1. Constructor (Solution(vector<int>& nums)):
We are not doing anything here, hence the time complexity will be O(1)
You can create a new array and assign the values of the nums array to the newly created array. In this case time complexity for this block will be O(n) where n is the input size of the array
2. Method sumRange(int left, int right):
The method calculates the sum of the subarray between indices left and right using a for loop.
The number of iterations is proportional to the difference between right and left, i.e., (right-left + 1). In the worst case, (right-left + 1) can go up to n
Therefore, the time complexity of the sumRange method is O(n), where n is the size of the array.
Space Complexity: O(n)
Input space: O(n), n is the input array size.
Auxiliary space: O(1) we are taking a sum variable to calculate the answer for every sumRange() function call.
Since the class does not create new data structures or copy the input vector numbers, its space complexity is O(1).
Auxiliary space: The auxiliary space refers to any extra space that the algorithm uses aside from the input and output data. In this case, no additional space is used hence Auxiliary space will be O(1).
Note: If you want, you can create a new array and copy the values of the nums array into a new array and that would create a new O(n) space complexity where N is the size of the input array.
So it will be better to use a referenced array of nums to reduce space complexity.
Can we solve this problem more efficiently?
In this problem, constraints are pretty low( n is up to 104), so the brute force approach will also be accepted.
But What if we have to calculate the sumRange for q number of queries?
It means suppose we have given q number of queries which are up to 105 and in every query, we have to find out the sumRange(left, right).
Also, in the worst case, the time complexity to calculate sumRange(left, right) can be up to 104.
Now, the brute force approach will show Time Limit Exceeded, because (104 x 105 = 109) generally in programming environments, every second only 107 to 108 iterations get accepted.
Due to this, a thought comes to our mind: can we get the answer to each query sumRange() in O(1)?
The answer to this question is YES!
With another approach, we can find out the sumRange(left, right) for each query in O(1) time complexity.
Approach to calculate the sumRange(left,right) in O(1) time complexity :
Intuition :
Let's assume we have some queries like sumRange(0,4), sumRange(0,3), sumRange(0,6).
Now by brute force method, we will have to run the loop from index left to right again and again to calculate the sum for all the queries.
We can observe that there are some calculations that we are performing repeatedly
Like in the first query, we are calculating the sum from index 0 to index 4
Similarly, in the second query, we calculate the sum from index 0 to index 3.
By calculating both the sumRange queries, we can observe that the sum from index 0 to index 3 is overlapping, which means we are calculating the sum of the overlapping interval again.
This is not a big issue for the problems having low constraints (Like N is up to 104 and the number of queries q up to 104).
But if we have a number of queries up to 105 then this method will not be accepted because as we have discussed earlier it will show the Time Limit Exceeded.
Due to this problem, a thought comes into our mind is there any way exists that we can calculate the sum only one time instead of calculating the sumRange(left, right) by brute force method again and again, we can use previously calculated sum to calculate the sumRange(left, right) queries efficiently?
Now, let’s see how we can achieve this :
Suppose we have created an array from the nums array and let's say its name is array arr.
Then we are assuming arr[i] represents “the sum of all the numbers of nums array from 0 index till index i will store in arr[i] ”.
So now, for each index i from 0 to n−1, we have the cumulative sum of elements up to index i, with the help of this can we find the prefix sum of a subarray starting with index i and ending at index j?
How to find prefix sum from index i to index j
Hence we can say,
arr[right]: the sum of all the values of the nums array from the 0th index to index right.
arr[left-1]: the sum of all the values of the nums array from the 0th index to index left-1.
Let’s assume:
nums : [a,b,c,d,e]
And we want to calculate the sumRange ( 1, 4 ) ( consider 0-based indexing)
Hence right = 4 , left = 1
arr[right]= a+b+c+d+e
arr[left-1]=a
Hence sumRange(1,4) = arr[right] - arr[left-1] = a + b + c + d + e - a = b + c + d + e
Hence we have got the desired answer.
Note: If we want to calculate the sumRange(0,2) in the above array
Then the answer will be only arr[2], because in this case, left=0, hence we cannot calculate arr[left-1].
This technique is very useful to calculate the sumRange(left, right) in O(1) time complexity and we call this technique as prefix array technique
Therefore after understanding the proof it, we can generalize :
To calculate the sumRange(left, right ) then we can use a simple formula given below : sumRange(left , right)= prefix[right] - prefix[left-1]
where prefix[i]= the sum of all the values of the nums array from the 0th index to index right.
Let’s dry run this approach for sample test case 1 given in the problem.
- The first input is NumArray, which means we just output the NumArray on which we will perform the sumRange(left, right) operation. Now, the NumArray is already given along with the input, so we don’t have to do anything with this.
- Let's create the prefix array for the input array
Input array : [-2, 0, 3, -5, 2, -1]
prefix array : [-2,-2, 1, -4,-2,-3] - The second input is the sumRange function which means we have to call sumRange(left, right), and here left= 0 and right=3. Therefore we will output the value of prefix[3]=-4 (since our left =0)
- The third input is sumRange function and now we have to output the value of sumRange(2,5), Here left= 2 and right=5
Therefore we will output the value of prefix[5]- prefix[1] = -3 - (-2) = -1 - Now, the fourth and the last input is also sumRange and now we have to calculate the sumRange(0,5)
Here left=0 and right = 5, therefore we will output the value of prefix[5] = -3.
Steps to Write the Code
1. We will create a prefix array that will reference the nums array, no copy at all !
2. After the Creation of the prefix array, we will jump to method sumRange(int left, int right). This method takes two inputs: left and right, these are the start and ending indices of the segment in the array in which we have to calculate the sum.
3. In the SolutionConstructor we will calculate the prefix sum of the nums array.
Till Now, prefix[i]=nums[i] for every index (Because we have initialized the prefix array in reference to the nums array.)
Now, to calculate the sum from index 0 to index i for prefix[i], we will run a loop from index 1 to index n-1, and the transition will be prefix[i]=prefix[i]+prefix[i-1], where n is the size of the nums array.
Optimized Code for All Languages
C++
class Solution {
public:
// 'prefix' will reference the 'nums' array, no copy at all!
vector<int>& prefix;
Solution(vector<int>& nums) : prefix(nums) {
// size of the nums array
int n = nums.size();
// calculation of the prefix array
for (int i = 1; i < n; i++) {
// transition to calculate prefix till index i
prefix[i] = prefix[i] + prefix[i - 1];
}
}
int sumRange(int left, int right) {
// if left index is 0, then simply return prefix[right]
if (left == 0)
return prefix[right];
return prefix[right] - prefix[left - 1];
}
};
Java
class Solution {
private int[] prefix;
// Constructor that initializes the reference to nums array
public Solution(int[] nums) {
prefix = nums;
int n = nums.length;
// Calculation of the prefix array
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i] + prefix[i - 1];
}
}
// Method to return the sum of elements between left and right (inclusive)
public int sumRange(int left, int right) {
if (left == 0) {
return prefix[right];
}
return prefix[right] - prefix[left - 1];
}
}
Python
class Solution:
def __init__(self, nums):
# 'prefix' will reference the 'nums' array
self.prefix = nums
# Calculate prefix array
for i in range(1, len(self.prefix)):
self.prefix[i] = self.prefix[i] + self.prefix[i - 1]
def sum_range(self, left, right):
# If left index is 0, return prefix[right]
if left == 0:
return self.prefix[right]
return self.prefix[right] - self.prefix[left - 1]
Javascript
class Solution {
// Constructor to initialize the prefix sum array
constructor(nums) {
this.prefix = nums;
let n = nums.length;
// Calculate the prefix sum array
for (let i = 1; i < n; i++) {
this.prefix[i] = this.prefix[i] + this.prefix[i - 1];
}
}
// Function to calculate sumRange
sumRange(left, right) {
// If the left index is 0, return the prefix sum directly
if (left === 0) {
return this.prefix[right];
}
// Otherwise, return the difference of prefix sums
return this.prefix[right] - this.prefix[left - 1];
}
}
Time Complexity
Constructor: Solution(vector<int> &nums)
The constructor computes a prefix sum for the input array. This involves iterating over the array and updating each element to store the cumulative sum up to that index.
The time complexity for this step is O(n), where n is the size of the input array nums.
This is because we perform a single loop over all elements of the array.
Method: sumRange(int left, int right)
This function returns the sum of elements in the range [left, right] by utilizing the prefix array.
If left == 0, the sum is simply prefix[right], which is an O(1) operation.
If left > 0, the sum is calculated as prefix[right] - prefix[left - 1], which is also an O(1) operation since both accesses and the subtraction are constant time.
Hence, the time complexity for this method is O(1).
Space Complexity
The total space complexity refers to the Auxiliary space and Input space.
Input Space Complexity: O(n) (size of nums array)
Input space refers to the size of the input: In this problem, our input is a nums array hence Input space will be O(n) where n is the size of the input array.
Auxiliary Space Complexity: O(1) (no additional array of structures used)
Auxiliary space: The auxiliary space refers to any extra space that the algorithm used aside from the input and output data.
In this case, no additional space is used other than the sum variable, and the sum variable has O(1) space complexity, hence in this case Auxiliary space will be O(1).
Constructor: Solution(vector<int> &nums)
The constructor does not allocate additional space for the prefix sum array, as it references the nums array and modifies it directly.
Therefore, the space complexity remains O(1) (excluding the input size)
Note: If you want, you can create a new prefix array and that would generate a new O(n) space complexity.
n is the size of the input array.
So it will be better to use a referenced array of nums to reduce space complexity.
Key learnings from this problem
We have understood the concept of prefix array which is very useful for performing sum range operations fastly.
Also, we have understood the working and mathematical proof of the prefix array.
Learning Tip
Having learned the optimal algorithm for prefix sum, you can now apply this algorithm to different similar problems. Additionally, you can attempt to solve the following problems by utilizing this approach.
Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:
- answer.length == nums.length.
- answer[i] = |leftSum[i] - rightSum[i]|.
Where:
- leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
- rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.
Return the array answer.
You are given a 0-indexed array of strings words and a 2D array of integers queries.
Each query queries[i] = [l_i, r_i]asks us to find the number of strings present in the range l_i to r_i (both inclusive) of words that start and end with a vowel.
Return an array ans of size queries.length, where ans[i] is the answer to the ith query.
Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.