Prefix Sum problem

what is a class and object in java

Problem Statement

Given an array of integers and an integer k. Find the total number of continuous subarrays whose sum equals k. Solve this problem using a prefix sum.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2

Note:
The length of the array is in the range [1, 20000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Analysis of the Problem Statement

The problem statement says that we are given an array of integers and an integer k and. We have to count the number of subarrays whose sum equals k.

Input/ Output

Let nums = [1, 2, -1, 2, 3, -4], k = 3
Output: 4
The subarrays are, [1, 2], [2, -1, 2], [3], [1, 2, -1, 2, 3, -4].

Naive Method

The naive method is to run three nested loops, two loops will take all the possible combinations of subarrays and the third loop will calculate the sum. If the sum equals k, we will increment the count variable and lastly, we will return the count variable.

This above solution will take O(n3) and constraints are too large. This solution will not be accepted and you will get a TLE error.

We have to think of an Optimized Solution. Code for the Naive method is given


int subarraySum(vector& nums, int k) {
         int count = 0;
         for(int i = 0; i < nums.size(); i++){
             for(int j = i; j < nums.size(); j++)
             {
                 int sum = 0;
                 for(int k = i; k <= j; k++){
                     sum = sum + nums[k];
                 }
                 if(sum == k){
                     count++;
                 }
             }
         }
         return count;
}

Optimized Solution using Prefix Sum Algorithm


We will use the concept of the Prefix Sum Algorithm to optimize this problem solution which we have already discussed. Instead of calculating the sum for every possible range, we can use prefixSum[ ] to compute the same.

We will not create a new array for prefix sum, instead, we will convert the given array to a prefix sum array in the same way we did in the previous problem.

After that we will simply check whether nums[i] == k if found we will increment the count, this will consider the case that sum of 1st I elements equals k.

Now we have to check for other subarrays too. For that, we will run a nested loop, and we will check for all possibilities, this we can do by subtracting the current prefix sum with the prefixSum[i], if it found to be the same with k, we will simply increment the count again.

The time complexity of prefix sum algorithm

Time Complexity of this Algorithm will be O(n2) and Space Complexity will be O(1).
prefix sum solution is better than the previous solution and will get accepted too.

Code
int subarraySum(vector& nums, int k) {
         int count = 0 , sum = 0;
        
         for(int i = 1; i < nums.size(); i++) {
             nums[i] += nums[i-1];
         }  
        
         for(int i = 0; i < nums.size(); i++) 
         {
             if(nums[i] == k) count++;
             for(int j = i+1; j < nums.size(); j++) 
             {
                 if(nums[j] - nums[i] == k) count++;
                 }
         }
         return count;
}


Wait Wait.. !! I know the above solution got accepted and it has ended your worries, but still, the above solution takes quadratic complexity which is not considered to be good in the programming world.

Think of an approach that can reduce its complexity further..?

As we are in the learning process, we should always discuss the most optimized solution too. So that it can help us in building logic for other problems too.

Best Solution(MasterStroke)

The solution which we are going to discuss is a bit tricky. I will try my best to make you understand. First, let us do some simple Mathematics observation.

nums[ ] = { 1, 2, -1, 2, 3, -4}

Let us consider this simple array, How many subarrays are present in the above array which sums 3.

Subarrays : [1,2], [2, -1, 2], [3], [1, 2, -1, 2, 3, -4]

Prefix Sum Array of the above array.

prefixSum[ ] = {1, 3, 2, 4, 7, 3}

Observation

We observe that prefixSum[3] = 4 and prefixSum[1] = 1, since the difference of both arrays gives us 3, so there must be a subarray between them whose sum results in 3. This is obvious intuition and as we guess there is a subarray present between them [2,-1,2], whose sum results in 3.

Let us take another example, prefixSum[4] = 7 and prefixSum[3] = 4, a difference of both gives us 3, so there must be a subarray present again whose sum results in 3 and the subarray is [3].

I hope you all get why this is happening since array comprises both positive and negative integers. There is always a chance that if we add something to the current subarray, it can give us the desired k. This would not be possible if the array consists only of positive integers because the overall sum of subarrays will gradually increase.

This is the main logic of our masterstroke Algorithm if we find some element in the prefix sum array whose difference gives us k. There is always a subarray present in it whose sum results in k.

Now the question arises, how we will store the previous sums so that we can find it easily whether (prefixSum[i] – k) is present or not. The answer to this question is hash-map.

Code  
int subarraySum(vector& nums, int k) {        
         unordered_map m;
         int s = 0, cnt = 0;
         
m[0] = 1;
         for(int i = 0; i < nums.size(); i++) {   
             s = s + nums[i];
             if(m.find(s-k) != m.end()){
                 cnt = cnt + m[s-k];
             }
             m[s]++;
         }
         return cnt;
}

We have used unordered_map here, so this will work as our hash-map. Initially, the key to all map values is 0. So we first update m[0] = 1.

This is obvious because we can get two consecutive 3’s so the difference between it will give 0 and since 0 is present in hash-map, we will increment our result.

We are using the concept of the Prefix Sum Algorithm which we have discussed earlier. The concept is the same but logic is a bit different which we have already discussed. We will check if (nums[i]-k) is present in the hash-map, if yes we will add its value to count or else we will create a new key.

Time complexity (prefix sum problem)

Time Complexity of MasterStroke Solution is just O(n) since find() function in unordered_map works in O(1).

Space Complexity changes to O(n), since we are using a map of size n.

This Algorithm is a bit complex but believes me it’s simple Maths and a bit of Observation if you don’t understand it please go through it once and try to understand what I am trying to say, and please do the observations as well.

That’s all Folks..!!!

Tagged : / /

Leave a Reply

Your email address will not be published. Required fields are marked *