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..!!!

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

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