Find Pivot Index

Leetcode 724. Find Pivot Index

Problem

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

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

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

Source : Leetcode 724. Find Pivot Index

Solution

To solve this problem, we can go through the array and keep track of cumulative sum of elements appeared so far. Before doing this, we have to get the total sum of the array.

Now let’s say the total sum is sum and the cumulative sum is stored in sum_so_far.

At any index, sum_so_far is the cumulative sum so far before reaching to that index.

At any index, we can get the sum to the right of that index by subtracting (sum_so_far + value at that index) from the total sum, right? In other word, we can that at index i of nums array by doing sum – nums[i] – sum_so_far.

So, at the index we will find sum_so_far = sum – nums[i] – sum_so_far, that index is our pivot index!

To see the solution in action, let’s say we have an array nums and variables sum and sum_so_far as below.

At first, we loop through the array and find that our sum is 28. So, we update sum as below.

Now, for each element we have to calculate values as discussed. At i = 0, our sum_so_far is 0 and sum – nums[i] – sum_so_far is 27. So, there is no match and we increment i.

At i = 1, our sum_so_far is 1 and sum – nums[i] – sum_so_far is 20. So, there is no match and we increment i.

At i = 2, our sum_so_far is 8 and sum – nums[i] – sum_so_far is 17. So, there is no match and we increment i.

At i = 3, our sum_so_far is 11 and sum – nums[i] – sum_so_far is also 11. So, there is a match and our pivot index is i !

So, we will stop searching at this point and return i as our desired answer!

Remember, if there is no pivot index found, we will have to return -1.

Below code is straight forward and should not be too hard to understand.

Code

C++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum_so_far = 0;
        int sum = 0;
        int len = nums.size();
        
        for(int i = 0; i < len; i++)
            sum += nums[i];
        
        for(int i = 0; i < len; i++){
            if(sum_so_far == (sum - nums[i] - sum_so_far))
                return i;
            sum_so_far += nums[i];
        }
        return -1;
    }
};

Conclusion

Hope you enjoyed the solution, though it was an easy problem 🙂 Please let us know what difficulty you are facing solving leetcode problems. If you love our blog or hate it, please shout out!

Happu coding! 🙂