Find Pivot Index Solution

Problem

Given an array of integers, find the leftmost index where the sum of all elements strictly to its left equals the sum of all elements strictly to its right. The element at the pivot index is excluded from both sums.

Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: At index 3, left sum = 1+7+3 = 11 and right sum = 5+6 = 11.

Counter-example: nums = [1, 2, 3] → output -1, because no index has equal left and right sums (at index 1, left=1, right=3).

Intuition

The problem asks for a balance point in the array where the weight on each side is equal. The key insight is that you don't need to recompute both sums at every step — if you know the total and the running left sum, the right sum is always total - left_sum - nums[i], letting you find the pivot in a single pass.

Approach 1 — Brute Force

At each index, independently sum all elements to the left and all elements to the right using inner loops, then compare.

Iterate over every index i from left to right.
Sum all elements before index i into left_sum.
Sum all elements after index i into right_sum.
If they are equal, return i.
If no index satisfies the condition, return -1.

1class Solution:
2    def pivotIndex(self, nums: List[int]) -> int:
3        for i in range(len(nums)):
4            left_sum = sum(nums[:i])    # sum of everything strictly left
5            right_sum = sum(nums[i+1:]) # sum of everything strictly right
6            if left_sum == right_sum:
7                return i
8        return -1

Time: O(n²) — each of the n indices triggers O(n) work to compute sums.
Space: O(1) — no extra storage beyond running counters.

Approach 2 — Prefix Sum (Single Pass)

Compute the total sum once, then walk left to right. At each index, the right sum is derivable in O(1) from the running left sum and the total, avoiding all redundant recomputation.

Compute total as the sum of all elements.
Initialize left_sum = 0.
For each index i, check if left_sum == total - left_sum - nums[i]; this is the right sum without recomputing it.
If equal, return i immediately — we are iterating left to right so this is the leftmost pivot.
Add nums[i] to left_sum before moving to the next index.
Return -1 if the loop exhausts without finding a pivot.

1class Solution:
2    def pivotIndex(self, nums: List[int]) -> int:
3        total = sum(nums)
4        left_sum = 0
5        for i, num in enumerate(nums):
6            # right sum = everything except left side and the pivot itself
7            if left_sum == total - left_sum - num:
8                return i
9            left_sum += num  # update AFTER the check so pivot is excluded
10        return -1

Time: O(n) — one pass to sum, one pass to find the pivot.
Space: O(1) — only two integer variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only acceptable for n < 1000 in a throwaway context
Prefix Sum	O(n)	O(1)	Always — this is the expected interview solution

Common Mistakes

Using total - left_sum instead of total - left_sum - nums[i] — this silently includes the pivot element in the right sum, so you compare "left side" vs "right side + pivot" and will produce wrong results on most inputs.
Updating left_sum before the comparison — writing left_sum += nums[i] before the if check means left_sum already contains nums[i], turning the left sum into "left side including pivot" rather than "strictly left."
Using nums[i+1:] correctly in Python but writing nums[i:] in the brute force — nums[i:] includes the pivot itself in the right sum slice; always start the right slice at i+1.
Assuming a unique pivot — the problem asks for the leftmost index, implying multiple valid pivots may exist (e.g., [0, 0, 0] has pivots at 0, 1, and 2). Iterating left-to-right and returning immediately handles this correctly without any extra logic.
Missing the all-zeros edge case mentally — for nums = [0], left_sum = 0 and total - 0 - 0 = 0, so index 0 is correctly returned; some developers mistakenly return -1 thinking an empty left/right side can't "equal" anything.

Find Pivot Index — Solution