Find Pivot Index LeetCode 724 Deep Dive

LeetCode 724 — Find Pivot Index asks you to return the leftmost index in the array where the sum of all numbers strictly to the left equals the sum of all numbers strictly to the right. The element at the pivot index itself is not included in either sum. If no such index exists, return -1.

This problem is a classic application of the prefix sum pattern. The naive approach checks every index by computing left and right sums independently for each candidate, resulting in O(n²) time. The efficient approach precomputes the total sum and maintains a running left sum, reducing the problem to a single O(n) scan with O(1) extra space.

Edge cases matter here: an index of 0 is a valid pivot if the total sum of elements from index 1 onward equals 0, because the left side is empty (sum = 0). Similarly, the last index is a valid pivot if all preceding elements sum to 0. Always handle these boundary cases with the same formula — no special-casing needed.

The key insight is that you do not need to recompute the left and right sums from scratch at every index. Instead, compute the totalSum of the entire array once in O(n). Then maintain a running leftSum initialized to 0. At each index i, the rightSum is totalSum minus leftSum minus nums[i] — computed in O(1).

After checking whether leftSum equals rightSum at index i, update leftSum by adding nums[i] before moving to index i+1. This way leftSum always represents the sum of all elements strictly to the left of the current index, and rightSum is derived from it in constant time using the total sum.

The algorithm terminates as soon as the first pivot is found, returning that index immediately. If the full array is traversed without finding a pivot, return -1. Both the time complexity and space complexity are optimal: O(n) time for the initial sum and single scan, O(1) extra space since only totalSum and leftSum are stored.

The algorithm is concise: one pass to compute totalSum, one pass to find the pivot. Both passes are O(n), making the overall complexity O(n). The pivot check and leftSum update inside the loop are O(1) each, so no nested loops are needed.

It is critical that leftSum is updated AFTER the pivot check at each index. Before the check, leftSum must represent the sum of elements strictly to the LEFT of index i, which excludes nums[i]. After a failed check, add nums[i] to leftSum before advancing to the next index.

This approach is also naturally correct for the leftmost pivot requirement: the loop iterates left to right and returns at the first match, so the result is always the smallest valid index without any additional tracking.

Formally, leftSum at index i equals prefix[i], where prefix[i] is the sum of nums[0..i-1]. The rightSum equals totalSum minus prefix[i] minus nums[i], which equals totalSum minus prefix[i+1]. The pivot condition leftSum == rightSum becomes prefix[i] == totalSum - prefix[i+1], or equivalently 2*prefix[i] + nums[i] == totalSum.

This alternate formulation — 2*leftSum + nums[i] == totalSum — avoids computing rightSum as a separate variable. It checks balance using only leftSum, nums[i], and totalSum. Both formulations are mathematically equivalent; choose whichever feels more readable in your implementation.

Understanding the prefix-sum foundation makes it easier to generalize: any problem asking for a balance point, equilibrium index, or split condition where left equals right can often be solved with this pattern. The same idea appears in problems like find the winner of an array game, minimum operations to equalize array halves, and more.

Consider nums = [1, 7, 3, 6, 5, 6]. The total sum is 1+7+3+6+5+6 = 28. Now scan left to right, maintaining leftSum = 0 initially and computing rightSum at each step.

At i=0: rightSum = 28 - 0 - 1 = 27. leftSum (0) != rightSum (27), so update leftSum to 0+1=1. At i=1: rightSum = 28 - 1 - 7 = 20. leftSum (1) != rightSum (20), update leftSum to 1+7=8. At i=2: rightSum = 28 - 8 - 3 = 17. leftSum (8) != rightSum (17), update leftSum to 8+3=11.

At i=3: rightSum = 28 - 11 - 6 = 11. leftSum (11) == rightSum (11) — pivot found! Return 3. Verify manually: left of index 3 = 1+7+3 = 11; right of index 3 = 5+6 = 11. Correct.

Python: def pivotIndex(nums): total=sum(nums); left=0; for i,n in enumerate(nums): if left==total-left-n: return i; left+=n; return -1. The built-in sum() computes totalSum in O(n), then the for loop runs one more O(n) pass. Total: O(n) time, O(1) space. Clean and concise — five lines of logic.

Java: public int pivotIndex(int[] nums) { int total=0; for(int n:nums) total+=n; int left=0; for(int i=0;i<nums.length;i++) { if(left==total-left-nums[i]) return i; left+=nums[i]; } return -1; }. Same structure: first loop accumulates total, second loop checks pivot. Both loops are O(n); space is O(1).

Both solutions handle all edge cases naturally: empty-left pivot (index 0) works because left=0 and right=total-0-nums[0]=total-nums[0]; empty-right pivot (last index) works because after all additions left equals total-nums[last]. No special-casing needed for any boundary.

LeetCode 724 belongs to the prefix sum balance family. Range Sum Query Immutable (LeetCode 303) is the foundational prefix sum problem, teaching the precomputed prefix array pattern that underlies all prefix sum techniques. Subarray Sum Equals K (LeetCode 560) combines prefix sums with a hash map to count subarrays summing to a target in O(n).

Product of Array Except Self (LeetCode 238) applies a similar left-and-right precomputation idea to products rather than sums, using the same single-pass derivation principle. The prefix sum balance family also includes problems like partition equal subset sum, split array largest sum, and minimum difference between sums of two halves.

Mastering the pivot index problem builds intuition for recognizing balance conditions: whenever a problem asks for a split point where left and right aggregates are equal, think prefix sum and total-minus-left derivation. This pattern is one of the most reliable O(n) techniques for array problems involving cumulative aggregates.