How to apply Prefix Sum in an array?
In this article, we will discuss the Prefix Sum technique. It’s a straightforward approach that is easy to understand and apply to the questions. Once you get a hold of this technique it will be easy to solve the variation of it as well. Let’s dig deeper.
Issue without Prefix Sum technique:-
Given an integer array of size N and a list of ranges of size M, find the sum of all the values in every given range.
int[] arr = [13, 4, 2, 9, 7, 10, 23, 7, 0, 15];
int[][] range = [[2,5],[0,4],[6,8],[1,7]];As you might have already guessed, we have to iterate through the range array, and for each range, we have to iterate through our array and find the sum.
for(int i=0;i<M;i++){
int s = range[i][0];
int e = range[i][1];
int sum = 0;
for(int j=s;j<=e;j++){
sum += arr[j];
}
}Time Complexity of this approach will be O(N*M).
Now let’s see the better approach.
Prefix sum is a technique used in computer programming to efficiently compute the sum of a contiguous subarray in an array. All the ranges which we saw in the above question is a contiguous subarrays. So that’s the cue to use the Prefix Sum technique for the above question.
The prefix sum algorithm creates a new array that stores the cumulative sum of elements from the original array up to each index. In other words, each element of the new array is the sum of all the elements in the original array up to that index.
If we try to derive a formula it will be like the one below. For all i>0,
prefixSum[i] = prefixSum[i-1] + arr[i]
By using this technique, let’s solve the question we discussed above more optimally.
As mentioned in the above diagram, if we want a sum from the range 6–8, we can find the sum till e=8 and subtract the sum till s-1 from it. The prefix sum array will give us the sum till e=8 and s-1 directly as prefixSum[8] and prefixSum[s-1].
The derived formula from the above explanation is,
Sum(s,e) = prefixSum[e] — prefixSum[s-1]
if s=0, then Sum(s,e) = prefixSum[e]
int[] prefixSum = new int[N];
prefixSum[0] = arr[0]
for(int i=1;i<N;i++){
prefixSum[i] = prefixSum[i-1] + arr[i];
}
int[] sumArr = new int[M];
for(int i=0;i<M;i++){
int s = range[i][0];
int e = range[i][1];
int sum = s == 0 ? prefixSum[e] : prefixSum[s-1] - prefixSum[e];
sumArr.push(sum);
}Time Complexity of this approach will be O(N+M).
That’s all folks!! If you clearly understand the above concept, you are never gonna forget about Prefix Sum. To strengthen your knowledge, you must practice at least 5–10 problems related to the prefix sum. You can find a few of the most frequently asked questions in the below link. Please do try it out and leave comments, if you have any doubts.
Leave a few claps if you like the article🙏. Stay tuned for the article on the “Carry Forward” method.
