Find the pivot index in an array of integers

Given an array of integers, find the index (pivot index) where the sum of values left of the index equals to the sum of values right of the index.

If no index is found whose left sum equals the right sum then return -1

Assumptions

- array.length >= 1

- Array is unsorted

- Array can contain duplicate numbers

Example

Input: [20,15,10,32,45]

Output: 3

Explanation: Sum of numbers left of index 3 (zero based - 0,1,2,3,4) 20+15+10=45. Sum of number to right of index 3 is 45 (only one number)

Hence pivot index is 3

Solution 1

1. Find total sum of all values of array.

2. Traverse array and find running sum at each index, this is the left sum.

3. At each index check if running sum equals the right sum (total sum - running sum - value at current index). Return index if left sum equals right sum.

4. Return -1 if pivot index is not found.

Code

public int pivotIndex(int[] nums) {
    //1. find total sum
    int total = 0;
    for(int num : nums) {
        total += num;
    }
    //2. find running total (left sum)
    int runningTotal = 0;
    for(int i=0; i<nums.length; i++) {
        //3. check if left sum equals right sum
        if(runningTotal == total-runningTotal-nums[i]) {
            return i;
        } else {
            runningTotal += nums[i];
        }
    }
    //4. pivot index not found
    return -1;
}

Complexity

Time Complexity O(N) - Since we are traversing the array (twice) to determine the pivot index the time complexity is O(N).

Space Complexity O(1) - No copies of the array elements are needed, hence extra space is not needed, so space complexity is O(1).