Find Pivot Index

ArrayPrefix Sum

Given an array of integers nums, write a function to find the pivot index of the array. The pivot index is the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1

Input

Output

Explanation. The pivot index is at index 3 because the sum of the elements to the left (1+7+3=11) is equal to the sum of elements to the right (5+6=11).

Example 2

Input

Output

-1

Explanation. No pivot index exists where the left and right sums are equal.

Example 3

Input

[
  [
    2,
    1,
    -1
  ]
]

Output

Explanation. The pivot index is at index 0 because there are no elements to the left and the sum of elements to the right (1+(-1)=0) is equal to the sum of elements to the left (0).

Follow-up: Can you solve this problem in `O(n)` time complexity where `n` is the length of the array? This will ensure that your solution is efficient even for large arrays.

Constraints:

1. The array will not be empty.\n2. The array will contain at least one element.\n3. The values in the array can be both positive and negative integers.

Views: 3