Find Pivot Index prefix sum problem

Leetcode Problem: Find Pivot Index

In our previous post, we solve one problem with prefix sum and now in this, we are again going to solve a problem. Given an array of integers nums, write a method that returns the “pivot” index of this array.
We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:
Input:
num = [1, 7, 3, 6, 5, 6]
Output: 3

Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.(1+7+3 = 6+5)
Also, 3 is the first index where this occurs.

Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].


Analysis of the Problem Statement


The problem statement is very clear that we have to find a pivot index in the given array where the sum of the elements to the left side of that index equals the sum of the element to the right side of it. If no such index is found, we have to return -1.

Let nums = [-1,-1,-1,0,1,1]
Output : 0

Here the sum of elements on the left side of index 0 is 0 and sum of elements on right side is also 0 ((-1) + (-1) + 0 + 1 + 1).


Naive Method


The naive method is to run three loops, one outer loop, and two inner loops, outer loop will iterate the whole array and inner loops will find the sum of elements present on the left side and right side of the current index. Lastly, we will check if both are the same or not, if found the same return that index or else we will return -1.

This above solution will take O(n^2) and this solution will not be accepted.


Code

int pivotIndex(vector& nums) {
         for(int i = 0; i < nums.size(); i++)
         {
             int left = 0, right = 0;
for(int j = 0; j < i; j++) {
left += nums[i];
}  
for(int j = i+1; j < nums.size(); j++) {
right += nums[i];
}
if(left == right) return i;  
         }
 return -1;
}


We observed that this solution takes O(n^2) time complexity. Can we solve it in O(n) time complexity ??


Prefix Sum Algorithm Approach


If we observe carefully, this problem can be solved by the Prefix Sum Algorithm which we have discussed earlier.

The idea is similar, we will store the prefix sum in a prefixSum[ ] array, and then we will calculate some formula which will give us the desired result.

Let us understand it by an example,

nums[ ] = {1, 7, 3, 6, 5, 6}

It’s prefixSum Array would be,

prefixSum[ ] = {1, 8, 11, 17, 22, 28}

Now let us take an index i = 2 so that we can find its left sum and right sum in O(1) time complexity.

Left sum : 1 + 7 = 8.
Right sum : 6 + 5 + 6 = 17.

Now let’s see how we can get this result from the prefix sum array.

Left sum : prefixSum[i-1] which is 8.
Right sum : (prefixSum[n-1] – prefixSum[i]) which is 28 – 11 = 17.

This was the main logic of this problem and now since we can calculate left and right in O(1) time complexity, overall complexity would be O(n*1). Please observe that we don’t even need an extra array to store the prefix Sum, we can convert the given array to a prefix sum array by simply adding its previous value with the current value.


Code

int pivotIndex(vector& nums) {
        
         for(int i = 1; i < nums.size(); i++) {
           nums[i] += nums[i-1];
         }
         int n =nums.size();
         int left, right;
        
         for(int i = 0; i < n; i++)
         {
             if(i == 0) left = 0;
             else left = nums[i-1];
            
             right =nums[n-1] - nums[i];
             if(left == right) return i;
         }
         return -1;
}

That’s all Folks..!!!

Tagged : /

Prefix Sum problem

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 : / /

Prefix Sum in Array

In Previous post we already discuss about sliding window technique and problem, in this post we are going to know about prefix sum technique in array

Let us Consider an example, we are given an array of integers and we have to find the range query sum of it, which means we are given some k number of Queries which takes two values l and r and we have to find the sum of elements present in this range (both inclusive). 

Let’s illustrate the problem statement more clearly, 

Let the array be, arr[5] = {4, 7, 2, 9, 5} and k = 3 is given, 

{2, 4}, { 3, 3},{  1, 5}

These are the range Queries and we have to find the sum of all the range queries

Output : 18 2 27  

Naive Method

The Naive method to solve this problem is to run two loops, first for iterating k   number of queries and second to find the actual sum between the range of the query. 

Code

void Sum (int *arr, int k)
{
	int l, r;
	for(int i = 1; i <= k; i++){
		cin >> l >> r;
		int sum = 0;
		for(int j = l; j <= r; j++){
			sum = sum + arr[j];
		}
		cout<<sum<<” “;
	}
}

Analysis of Complexity of the Naive Solution

Calculation of sum between range takes O(n) time complexity in worst case.

  To perform k number of Queries on n size Array,  Time Complexity :

O(k*n) 

But Prefix Sum Algorithm does the same task,  Time Complexity : O(n) 

Algorithm of Prefix Sum

The idea of the Prefix Sum Algorithm is to transform an array in O(n) time complexity such that the difference of (arr[l]-arr[r]) gives us the desired result.   

Since Subtraction operation takes O(1) time, so overall time complexity would be  O(n*1). 

Now the question arises, how do we transform the array to perform this task? 

Sadly, there is no magic that will transform the array for us to perform this task.  We only have to think of some calculations which will transform it. 

Don’t worry we will discuss the logic here but it is highly recommended to first think it yourself. If you found any algorithm, congrats.

But if not don’t worry, we will discuss it. 

4 7 2 9 5

This was the array we had previously,

We will create a prefix sum array where we will store the prefix sum values. Prefix sum is the sum of the array values till that point. For ex :- arr[2] = 11 ( 4 + 7).

4 11 13 22 27

This is the prefixSum[ ] array where we store prefix sum values at every index.

This prefixSum array will help us to solve the Range Sum query problem.

Let us take a query where l = 2 and r = 5.

Step 1 : We know that prefixSum[2] = 11 and prefixSum[5] = 27.

Step 2 : Calculate prefixSum[5] – prefixSum[2-1].

Finally : We got the desired result of this Query.

This looks quite simple and believes it, this Algorithm follows these steps only.

Code for prefix sum

void Sum (int *arr, int k, int n)
{
	int prefixSum[n+1];			
	int sum = 0, result;
	for(int i = 1; i <= n; i++){
		sum += arr[i];
		prefixSum[i] = sum;
	}
	for(int i = 1; i <= k; i++){
		cin >> l >> r;
		if ( l == 0) result = prefixSum[r];
		else result = prefixSum[r] - prefixSum[l-1];
		cout<<result<<” “;
	}
}

Analysis of Prefix Sum Algorithm

This is a two step Algorithm, first we create prefixSum[ ] array,

Time Complexity : O(n)

Secondly we just find the result for each Query,

Time Complexity : O(k)

Overall Time Complexity : O(n+k)

We observed that we solved the Range Query Problem in just Linear time complexity which is quite better than Quadratic Time Complexity. 

Logic Behind Prefix Sum Algorithm (MasterStroke)

We have observed that we are getting the desired result of Range Sum Query in Linear time after solving it through the prefix Sum Algorithm but why are we getting the result, what is the logic behind it?

Let us consider the example again,

4 7 2 9 5

Let us also take a query l = 3 and r = 5.

We need to find the sum of this query, which would be 2+9+5 = 16 and we can find it by simply running a loop from arr[l] to arr[r] and find its sum.

But if we observe carefully, we can also get the desired result by subtracting the total sum with the sum of the range which is not included in (l, r).

Total sum : 4 + 7 + 2 + 9 + 5 = 27

Sum of range which is not included in (l, r) : 4 + 7 = 11

Result : 27 – 11 = 16

This is the main logic of Prefix Sum Algorithm, we first pre-calculate the prefixSum and store it in array prefixSum[ ].

Now since we know the range (l, r) and also we know the total sum of the array element up to r ( prefixSum[r]), we simply need to subtract it with the sum of the elements which are not included in the range, which means prefixSum[l-1].

prefixSum[l-1] stores the sum of elements included in the range (1, l-1).

Hope you all understand the logic behind the Prefix Sum Algorithm. Prefix Sum Algorithm is quite a useful Algorithm to solve Range Query Problems and many other interview problems.

Tagged :