Arrays - Find Pivot Index

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.

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

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

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

Solution using two pointers

In this approach, what we are going to do is compute the total sum of array total, then keep checking left side elements sum and right side elements for every element we loop through, if they match at an index, then we have found the answer, otherwise we just return -1.

Implementation details

We will create a function usingTwoPointers that takes input argument nums.
In the first step, we are going to compute the total sum of elements and store it in a variable total.
Create two variable leftSum to keep track left side elements sum and rightSum to hold right side elements sum.
Then, loop through each element in the array and compute leftSum and rightSum:
- To compute leftSum keep adding current elements that we are looping through.
- To compute rightSum, since we already know total and leftSum, we can compute right elements sum as: rightSum = total - leftSum - nums[i]; // since we want strictly right side sum, we have to subtract current element
For any index i, if leftSum matches to rightSum, then we have found answer at index i, otherwise return -1 at the end.

public class FindPivotIndex { static int usingTwoPointers(int[] nums) { int total = 0; for(int i=0; i<nums.length; i++) { total += nums[i]; } int leftSum = 0; for(int i=0;i <nums.length; i++) { int rightSum = total - nums[i] - leftSum; if(leftSum == rightSum) { return i; } leftSum += nums[i]; } return -1; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Contents

Implementation details

Complexity Analysis: