481. Find Pivot Index
You are given an integer array nums. An index i is a pivot if the sum of every element strictly to its left equals the sum of every element strictly to its right — the element at i itself belongs to neither side.
Edges follow the same rule with empty sides: for index 0 the left sum is 0, and for the last index the right sum is 0.
Return the leftmost pivot index, or -1 if the array has none.
Example 1:
Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: At index 3 the left side is 1 + 7 + 3 = 11 and the right side is 5 + 6 = 11. No earlier index balances, so 3 is the answer.
Example 2:
Input: nums = [2, 1, -1]
Output: 0
Explanation: Index 0 has an empty left side (sum 0), and the right side is 1 + (-1) = 0. Both sides match immediately, so the leftmost pivot is 0.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -1000 ≤ nums[i] ≤ 1000
Hints:
Recomputing both side sums for every index works but repeats a huge amount of addition — that's the O(n²) trap.
If you know the total of the whole array and the running sum `left` of everything before index i, the right side is forced: right = total − left − nums[i]. One comparison per index.
Sweep left to right, testing `left == total − left − nums[i]` before adding nums[i] into `left`. Return the first index that balances.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 7, 3, 6, 5, 6]
Expected output: 3