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.
The idea is to calculate the total sum of the array elements first. Then, we iterate over the array while maintaining a running sum (prefix sum) of the elements. For each element, we can compute the right sum as rightSum = totalSum - leftSum - nums[i]. If the leftSum equals rightSum at any index, that's our pivot index.
This approach optimizes the solution to a single pass after calculating the total sum initially.
In this C solution, we first calculate the total sum of the array. We then iterate through the array, comparing the left sum to totalSum - leftSum - nums[i] at each index to determine if it's the pivot point.
Time Complexity: O(n) where n is the number of elements in the array. We traverse the array twice (once for total sum and once for left sums).
Space Complexity: O(1) as no extra space is used beyond auxiliary variables.
This method employs two pointers, one starting from the beginning and another from the end of the array. Both pointers attempt to reach a common point that becomes the pivot index. The trick is to equalize the progressive sums they each encounter by advancing the pointer pointing to the smaller running sum.
This solution attempts to find the pivot using two pointers from either end of the array, balancing their cumulative sums until they converge.
Time Complexity: Worst case O(n) as each element gets accessed once by either pointer.
Space Complexity: O(1) with additional variables for maintaining the sums and pointers.
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) where n is the number of elements in the array. We traverse the array twice (once for total sum and once for left sums). Space Complexity: O(1) as no extra space is used beyond auxiliary variables. |
| Two-Pointer Approach | Time Complexity: Worst case O(n) as each element gets accessed once by either pointer. Space Complexity: O(1) with additional variables for maintaining the sums and pointers. |
| 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 |
Find Pivot Index - Leetcode 724 - Python • NeetCode • 72,464 views views
Watch 9 more video solutions →Practice Find Pivot Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor