Find Pivot Index

You are given an array of integers, you need to return the pivot index of the array if it exists, else return -1.

Pivot index of an array is defined as the index where the sum of all the numbers to the left of it in the array is equal to the sum of all the numbers to the right of it in the array. If there are multiple such indices, return the left most pivot index.

Sample Input - {1, 7, 3, 6, 5, 6}
Expected Output - 3.
Explanation - The sum of elements to the left of 3rd index and to the right of 3rd index is 11.

Sample Input - {1, 2, 3, 4}
Expected Output - -1.

Algorithm

We can solve the problem in linear time using prefix sum array. A prefix sum array is one, where each index stores the sum of all the elements before it including the current element.
If the size of the array is 0, we return -1. If there is only one element, we return 0. We start iterating from index 1 to (N-1). At each iteration we do the following –
If ( prefix [ i – 1 ] == [ prefix ( N – 1 ) – prefix ( i ) ]), we return i’th index, where 1<=i<N.
Else, we return -1.

For better understanding, check out the code below.

#include <bits/stdc++.h>
using namespace std;

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

int main(){
	vector<int> arr = {1, 7, 3, 6, 5, 6};
	cout<<pivotIndex(arr);
	return 0;
}

Also, check out another popular interview problem Search in Rotated Sorted Array.

One comment

Leave a Reply

Your email address will not be published.