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.
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; }}Video 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.