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] <= 1000Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/
The Find Pivot Index problem asks you to locate an index where the sum of all elements to the left equals the sum of all elements to the right. A brute-force approach would recompute left and right sums for every index, but this leads to unnecessary repeated work.
A more efficient idea is to use the concept of prefix sums. First compute the total sum of the array. Then iterate through the array while maintaining a leftSum. At each index, you can derive the right-side sum using the relationship between the total sum, the current value, and the accumulated left sum.
If the left sum equals the computed right sum at any position, that index is the pivot. This approach avoids recalculating sums for each position and processes the array in a single pass after computing the total.
The optimized strategy runs in O(n) time with O(1) additional space, making it ideal for coding interviews and large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Running Sum / Prefix Sum Idea | O(n) | O(1) |
| Brute Force (recompute sums for each index) | O(n^2) | O(1) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Create an array sumLeft where sumLeft[i] is the sum of all the numbers to the left of index i.
Create an array sumRight where sumRight[i] is the sum of all the numbers to the right of index i.
For each index i, check if sumLeft[i] equals sumRight[i]. If so, return i. If no such i is found, return -1.
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.
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.
1class Solution {
2 public int pivotIndex(int[] nums) {
3 int totalSum = 0, leftSum = 0;
4 for
This Java solution calculates the total sum of elements and uses a left sum to check for the pivot index by comparing it to the right sum calculated on the fly.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of array balance or prefix sum problem is common in technical interviews. It tests understanding of cumulative sums, space optimization, and efficient single-pass algorithms.
Prefix sums help avoid recomputing subarray sums repeatedly. By keeping track of the cumulative sum while iterating, you can quickly determine whether the left and right portions of the array are balanced at each index.
The problem can be solved using only the input array and a few variables for sums. No additional data structures are required when using the running sum or prefix sum technique.
The optimal approach uses a running sum with the total array sum. By tracking the left-side sum during iteration, the right-side sum can be derived instantly, allowing the pivot index check in constant time per element.
Java's solution balances sums from both sides, using a two-pointer method to potentially identify a common pivot index.