Skip to main content

Find Pivot Index

LeetCode 724 | Difficulty: Easy​

Problem Description​

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 right.

  • If the index is on the left edge, the left sum is 0 (no elements to the left)
  • If the index is on the right edge, the right sum is 0 (no elements to the right)

Return *the leftmost pivot index*. If no such index exists, return -1.

Constraints​

  • 1 <= nums.length <= 10^4
  • -1000 <= nums[i] <= 1000

Examples​

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation: 
  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: No index satisfies the pivot condition.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation: 
  Left sum  = 0 (no elements to the left of index 0)
  Right sum = 1 + (-1) = 0

Approach​

Key Insight: At any index i:

  • leftSum = sum of elements [0..i-1]
  • rightSum = totalSum - leftSum - nums[i]

If leftSum == rightSum, then i is the pivot index.

Visualization for [1,7,3,6,5,6]:

IndexElementLeft SumRight SumIs Pivot?
01027No
17120No
23817No
361111Yes ✓
45176No
56220No

Total sum = 28. At index 3: leftSum = 11, rightSum = 28 - 11 - 6 = 11 ✓

Complexity Analysis​

  • Time Complexity: $O(N)$ — One pass to calculate total, one pass to find pivot
  • Space Complexity: $O(1)$ — Only using a few variables
public int PivotIndex(int[] nums)
{
    int totalSum = 0;
    foreach (int num in nums)
    {
        totalSum += num;
    }
    
    int leftSum = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        int rightSum = totalSum - leftSum - nums[i];
        
        if (leftSum == rightSum)
        {
            return i; // Found the pivot
        }
        
        leftSum += nums[i];
    }
    
    return -1; // No pivot found
}

Solution: Using Prefix/Suffix Arrays​

This approach uses extra space but is more intuitive:

public int PivotIndexWithArrays(int[] nums)
{
    int len = nums.Length;
    long[] leftSum = new long[len];
    long[] rightSum = new long[len];
    
    // Build left prefix sums
    leftSum[0] = 0; // Nothing to the left of index 0
    for (int i = 1; i < len; i++)
    {
        leftSum[i] = leftSum[i - 1] + nums[i - 1];
    }
    
    // Build right suffix sums
    rightSum[len - 1] = 0; // Nothing to the right of last index
    for (int i = len - 2; i >= 0; i--)
    {
        rightSum[i] = rightSum[i + 1] + nums[i + 1];
    }
    
    // Find pivot
    for (int i = 0; i < len; i++)
    {
        if (leftSum[i] == rightSum[i]) return i;
    }
    
    return -1;
}

[!NOTE] The space-optimized solution is preferred in interviews as it demonstrates understanding of the mathematical relationship between left sum, right sum, and total sum.

Interview Tips​

  • Edge case - First element: If totalSum - nums[0] == 0, then index 0 is the pivot
  • Edge case - Last element: If totalSum - nums[n-1] == 0, then index n-1 is the pivot
  • Negative numbers: The problem allows negatives, so don't assume sums are always positive
  • Follow-up: What if you need to find all pivot indices? (Remove the early return)