Watch 10 video solutions for Find Pivot Index, a easy level problem involving Array, Prefix Sum. This walkthrough by NeetCode has 72,464 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Example 1:
Input: nums = [1,7,3,6,5,6] Output: 3 Explanation: The pivot index is 3. Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 Right sum = nums[4] + nums[5] = 5 + 6 = 11
Example 2:
Input: nums = [1,2,3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement.
Example 3:
Input: nums = [2,1,-1] Output: 0 Explanation: The pivot index is 0. Left sum = 0 (no elements to the left of index 0) Right sum = nums[1] + nums[2] = 1 + -1 = 0
Constraints:
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/
Problem Overview: You are given an integer array nums. The pivot index is the position where the sum of elements on the left equals the sum of elements on the right. Return the leftmost such index. If none exists, return -1.
Approach 1: Prefix Sum Approach (O(n) time, O(n) space)
This method explicitly builds prefix sums to quickly compute the sum of elements before any index. Create a prefix array where prefix[i] stores the sum of elements from index 0 to i. For each index i, the left sum is prefix[i-1] and the right sum is prefix[n-1] - prefix[i]. Iterate through the array and compare these two values. The first index where both sums match is the pivot index. The key idea is that prefix sums let you calculate subarray sums in constant time instead of recomputing them repeatedly.
This approach is easy to reason about and useful when you want clear separation between preprocessing and query logic. However, it requires an additional array of size n, which increases space usage. The technique is widely used in problems involving cumulative sums and range queries, especially when working with array data.
Approach 2: Running Sum / Two-Pointer Style Scan (O(n) time, O(1) space)
A more space-efficient solution avoids the extra prefix array. First compute the total sum of the array. Then iterate from left to right while maintaining a running leftSum. At index i, the right side sum equals totalSum - leftSum - nums[i]. If leftSum equals that value, you found the pivot index. Otherwise, add nums[i] to leftSum and continue.
This works because the total sum allows you to derive the right portion dynamically while scanning the array once. Conceptually it behaves like a balanced scan from both sides: the left side grows while the computed right side shrinks. The algorithm performs a single pass and constant extra work per element. It is a classic application of the prefix sum concept combined with a linear scan similar to patterns seen in two pointers problems.
Recommended for interviews: The running-sum version is the expected solution. It achieves O(n) time with O(1) space and demonstrates that you understand how prefix sums eliminate repeated calculations. Mentioning the explicit prefix array first can show your reasoning process, but optimizing it to constant space signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Array | O(n) | O(n) | When clarity matters or when prefix sums will be reused for multiple range queries |
| Running Sum / Two-Pointer Style Scan | O(n) | O(1) | Best general solution; optimal for interviews and large arrays |