Find Pivot Index
EasyPrompt
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 = 11Example 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/
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each possible pivot index and, for each one, calculates the sum of elements to its left and the sum of elements to its right by iterating through the respective subarrays. It's straightforward but inefficient.
Algorithm
- Iterate through each index
ifrom0tonums.length - 1. - For each
i, initializeleftSumandrightSumto 0. - Calculate
leftSumby iterating from indexj = 0toi - 1and summing upnums[j]. - Calculate
rightSumby iterating from indexk = i + 1tonums.length - 1and summing upnums[k]. - If
leftSumis equal torightSum, theniis a pivot index. Since we need the leftmost one, we can returniimmediately. - If the loop completes without finding any pivot index, return -1.
Walkthrough
The core idea is to test every index to see if it's a pivot. For each index i, we perform two separate summations. First, we sum all elements from the beginning of the array up to i-1 to get the leftSum. Second, we sum all elements from i+1 to the end of the array to get the rightSum. If leftSum equals rightSum, we've found our pivot. Since the problem asks for the leftmost pivot index, the first one we find is the answer. If we iterate through all indices and don't find a match, it means no pivot index exists, and we return -1.
class Solution { public int pivotIndex(int[] nums) { for (int i = 0; i < nums.length; i++) { int leftSum = 0; for (int j = 0; j < i; j++) { leftSum += nums[j]; } int rightSum = 0; for (int k = i + 1; k < nums.length; k++) { rightSum += nums[k]; } if (leftSum == rightSum) { return i; } } return -1; }}Complexity
Time
O(n^2) - For each of the `n` elements in the array, we iterate through the array again to calculate the left and right sums. This results in a nested loop structure.
Space
O(1) - We only use a few variables to store the sums and loop counters, so the space used is constant.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient due to repeated calculations.
The time complexity of O(n^2) makes it unsuitable for large arrays.
This method improves upon the brute-force approach by pre-calculating sums. We create an array for prefix sums (sum from the start up to the current index). This allows for O(1) lookup of the left sum for any potential pivot. The right sum can then be deduced from the total sum and the prefix sum at the current index.
Algorithm
- Create a
prefixSumarray of the same size asnums. - Fill the
prefixSumarray such thatprefixSum[i]is the sum of all elements fromnums[0]tonums[i]. - Calculate the
totalSumof the array, which is simplyprefixSum[n-1]. - Iterate through each index
ifrom0tonums.length - 1. - For each index
i, theleftSumisprefixSum[i-1](or 0 ifi=0). - The
rightSumcan be calculated astotalSum - prefixSum[i]. - If
leftSumequalsrightSum, returni. - If the loop finishes, return -1.
Walkthrough
To optimize the repeated sum calculations of the brute-force method, we can precompute the sums. We create a prefixSum array where prefixSum[i] stores the sum of nums[0]...nums[i]. With this array, for any index i, the left sum is prefixSum[i-1] (or 0 if i=0). The total sum of the array is prefixSum[n-1]. The right sum for index i is totalSum - prefixSum[i]. We can then iterate through the indices once, check the condition in O(1) time, and return the first match.
class Solution { public int pivotIndex(int[] nums) { int n = nums.length; if (n == 0) return -1; int[] prefixSum = new int[n]; prefixSum[0] = nums[0]; for (int i = 1; i < n; i++) { prefixSum[i] = prefixSum[i-1] + nums[i]; } int totalSum = prefixSum[n-1]; for (int i = 0; i < n; i++) { int leftSum = (i == 0) ? 0 : prefixSum[i-1]; int rightSum = totalSum - prefixSum[i]; if (leftSum == rightSum) { return i; } } return -1; }}Complexity
Time
O(n) - We perform two separate passes through the array: one to build the prefix sum array and another to find the pivot index. This simplifies to O(n).
Space
O(n) - We need an extra array of size `n` to store the prefix sums.
Trade-offs
Pros
Significant improvement in time complexity over the brute-force approach.
The logic is still relatively easy to follow.
Cons
Requires extra space proportional to the size of the input array.
This is the most optimal approach. It first calculates the total sum of the array. Then, it iterates through the array once, maintaining a running sum of elements to the left. The right sum can be deduced at each step using the total sum, the left sum, and the current element's value, avoiding the need for extra space.
Algorithm
- First, iterate through the array once to calculate the
totalSumof all its elements. - Initialize a variable
leftSumto 0. - Iterate through the array again with index
ifrom0tonums.length - 1. - In each iteration, check if the current
leftSumis equal to therightSum. TherightSumcan be calculated on the fly astotalSum - leftSum - nums[i]. - If
leftSum == totalSum - leftSum - nums[i], we have found the pivot index, so returni. - If the condition is not met, update
leftSumby adding the current element:leftSum += nums[i]. - If the loop completes without finding a pivot, return -1.
Walkthrough
This approach is the most efficient in terms of both time and space. The key insight is that if we know the totalSum of the array and the leftSum up to a certain index i, we can find the rightSum without iterating again. The rightSum is simply totalSum - leftSum - nums[i].
The algorithm proceeds in two main steps. First, we compute the totalSum of all elements in nums. Second, we iterate through nums from left to right, maintaining a leftSum variable, which starts at 0. In each iteration for index i, we check if the current leftSum is equal to the calculated rightSum. If it is, we've found the pivot. After the check, we update leftSum by adding nums[i] to prepare for the next index.
class Solution { public int pivotIndex(int[] nums) { int totalSum = 0; for (int num : nums) { totalSum += num; } int leftSum = 0; for (int i = 0; i < nums.length; i++) { // The right sum is totalSum - leftSum - nums[i] if (leftSum == totalSum - leftSum - nums[i]) { return i; } leftSum += nums[i]; } return -1; }}Complexity
Time
O(n) - The algorithm involves two passes through the array: one to calculate the total sum and another to find the pivot. This is linear time complexity.
Space
O(1) - We only use a couple of variables (`totalSum`, `leftSum`) to store sums, regardless of the input array size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Efficient for large datasets.
Cons
Requires two passes over the array, though it's still linear time.
Solutions
Solution
class Solution {public int pivotIndex(int[] nums) { int left = 0, right = Arrays.stream(nums).sum(); for (int i = 0; i < nums.length; ++i) { right -= nums[i]; if (left == right) { return i; } left += nums[i]; } return -1; }}/** * @param {number[]} nums * @return {number} */ var pivotIndex = function ( nums,) { let left = 0, right = nums.reduce((a, b) => a + b); for (let i = 0; i < nums.length; ++i) { right -= nums[i]; if (left == right) { return i; } left += nums[i]; } return -1;};class Solution {public: int pivotIndex(vector<int> &nums) { int left = 0, right = accumulate(nums.begin(), nums.end(), 0); for (int i = 0; i < nums.size(); ++i) { right -= nums[i]; if (left == right) { return i; } left += nums[i]; } return -1; }};class Solution: def pivotIndex(self, nums: List[int]) -> int: left, right = 0, sum(nums) for i, x in enumerate(nums): right -= x if left == right: return i left += x return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.