Prefix Sum · 156Easy
Find Pivot Index
Given an array nums, return the leftmost index where the sum of everything strictly to its left equals the sum of everything strictly to its right. Return -1 if no such index exists.
Constraints
- 1 <= nums.length <= 10^4
- -1000 <= nums[i] <= 1000
Examples
pivotIndex([1, 7, 3, 6, 5, 6]) -> 3 pivotIndex([1, 2, 3]) -> -1 pivotIndex([2, 1, -1]) -> 0 // empty left side sums to 0 pivotIndex([1]) -> 0 // single element, both sides empty pivotIndex([-1, 1, 0]) -> 2 // the last index qualifies the same way pivotIndex([0, 0, 0]) -> 0 // every index qualifies — return the leftmost
Edge cases
- Index 0 is valid — the empty left side sums to 0.
- The last index is valid the same way.
- Return the LEFTMOST qualifying index.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — recompute both side sums at every index.
- Target
- O(n) time, O(1) space — one pass with a running left sum, comparing it against (total - left - nums[i]).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/21-prefix-sum/156-find-pivot-index.js ./practice c 156