java

Pivot index

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0, leftsum = 0;
        for (int x: nums) sum += x;
        for (int i = 0; i < nums.length; ++i) {
            if (leftsum == sum - leftsum - nums[i]) return i;
            leftsum += nums[i];
        }
        return -1;
    }
}

Output

Input:
nums = [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.
Also, 3 is the first index where this occurs.

Intuition and Algorithm

We need to quickly compute the sum of values to the left and the right of every index.

Let's say we knewÂ SÂ as the sum of the numbers, and we are at indexÂ i. If we knew the sum of numbersÂ leftsumÂ that are to the left of indexÂ i, then the other sum to the right of the index would just beÂ S - nums[i] - leftsum.

As such, we only need to know aboutÂ leftsumÂ to check whether an index is a pivot index in constant time. Let's do that: as we iterate through candidate indexesÂ i, we will maintain the correct value ofÂ leftsum.

Complexity Analysis

Time Complexity:Â $O(N)$ , whereÂ $N$ Â is the length ofÂ nums.
Space Complexity:Â $O(1)$ , the space used byÂ leftsumÂ andÂ S.

Was this helpful?