Problem Description

You are given an array of integers nums. Your task is to find the pivot index of this array.

The pivot index is defined as the index where the sum of all numbers strictly to the left of that index equals the sum of all numbers strictly to the right of that index.

Key points to understand:

• If the index is at position 0 (leftmost), the left sum is 0 since there are no elements to its left
• If the index is at the last position (rightmost), the right sum is 0 since there are no elements to its right
• You need to return the leftmost pivot index if multiple pivot indices exist
• If no pivot index exists, return -1

For example, if nums = [1, 7, 3, 6, 5, 6]:

• At index 3 (value 6):
  • Left sum: 1 + 7 + 3 = 11
  • Right sum: 5 + 6 = 11
  • Since left sum equals right sum, index 3 is a pivot index

The solution uses a two-pointer approach with running sums:

1. Initialize left = 0 (sum of elements to the left) and right = sum(nums) (total sum)
2. For each index i:
   • Subtract current element from right (removing it from the right sum)
   • Check if left == right (found pivot index)
   • Add current element to left (adding it to the left sum for next iteration)
3. Return the first index where left == right, or -1 if none exists

The algorithm efficiently finds the pivot in a single pass with O(n) time complexity and O(1) space complexity.

Intuition

The key insight is recognizing that we don't need to recalculate the left and right sums from scratch for each index. Instead, we can maintain running sums and update them as we traverse the array.

Think about what happens as we move from one index to the next:

• The element at the current index moves from being "on the right" to being "on the left"
• This means we can start with all elements in the "right sum" and gradually move them to the "left sum" one by one

Let's trace through the thought process:

1. Initially, if we're considering index 0 as a potential pivot:

   • Left sum = 0 (nothing to the left)
   • Right sum = sum(nums[1:]) (everything except nums[0])

2. When we move to index 1:

   • Left sum = previous left sum + nums[0]
   • Right sum = previous right sum - nums[1]

This pattern reveals that we can maintain two variables:

• left: accumulates the sum of elements we've passed
• right: starts with the total sum and decreases as we traverse

The clever part is the order of operations in each iteration:

1. First, subtract the current element from right (because the current element shouldn't be included in either the left or right sum when checking if it's a pivot)
2. Check if left == right (this is our pivot condition)
3. Then add the current element to left (preparing for the next iteration)

This approach transforms what could be an O(n²) solution (calculating sums for each index) into an elegant O(n) solution with just one pass through the array.

Learn more about Prefix Sum patterns.

Solution Approach

Following the prefix sum pattern, we implement the solution using two running sum variables:

Initialization:

• left = 0: Represents the sum of elements to the left of the current index
• right = sum(nums): Initially holds the total sum of all elements

Main Algorithm:

We iterate through the array using enumerate to get both index and value:

for i, x in enumerate(nums):
    right -= x        # Step 1: Remove current element from right sum
    if left == right: # Step 2: Check pivot condition
        return i
    left += x         # Step 3: Add current element to left sum

Step-by-step Logic:

1. Update right sum: right -= x

   • We subtract the current element because at index i, the pivot check requires sums of elements strictly to the left and right
   • After this subtraction, right contains the sum of all elements after index i

2. Check pivot condition: if left == right

   • At this point, left has the sum of all elements before index i
   • If they're equal, we've found our pivot index and return immediately

3. Update left sum: left += x

   • We add the current element to left to prepare for the next iteration
   • This element will now be part of the "left side" for the next index

Edge Cases Handled:

• Index 0: left = 0 and right = sum(nums[1:]) after the first subtraction
• Last index: right becomes 0 after subtracting all elements
• No pivot: If the loop completes without finding a match, return -1

Time and Space Complexity:

• Time: O(n) - One pass to calculate initial sum, one pass to find pivot
• Space: O(1) - Only using two variables regardless of input size

This approach elegantly avoids recalculating sums at each position by maintaining the invariant that left + nums[i] + right = total_sum throughout the iteration.

Example Walkthrough

Let's walk through the solution with nums = [2, 1, -1]:

Initial Setup:

• left = 0 (sum to the left of current index)
• right = sum([2, 1, -1]) = 2 (total sum)

Iteration 1 (i=0, x=2):

1. right = right - x = 2 - 2 = 0 (remove current element from right)
2. Check: left == right? → 0 == 0? → Yes!
3. Return 0 as the pivot index

Let's verify: At index 0:

• Left sum = (nothing) = 0
• Right sum = 1 + (-1) = 0
• They're equal, so index 0 is indeed the pivot! ✓

Let's try another example where the pivot isn't at the beginning: nums = [1, 2, 3]:

Initial Setup:

• left = 0
• right = sum([1, 2, 3]) = 6

Iteration 1 (i=0, x=1):

1. right = 6 - 1 = 5
2. Check: 0 == 5? → No
3. left = 0 + 1 = 1

Iteration 2 (i=1, x=2):

1. right = 5 - 2 = 3
2. Check: 1 == 3? → No
3. left = 1 + 2 = 3

Iteration 3 (i=2, x=3):

1. right = 3 - 3 = 0
2. Check: 3 == 0? → No
3. left = 3 + 3 = 6

Result: Loop completes without finding a pivot, return -1

This makes sense because:

• At index 0: left=0, right=5
• At index 1: left=1, right=3
• At index 2: left=3, right=0

No position has equal left and right sums.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• The initial sum(nums) operation takes O(n) time to compute the total sum of all elements
• The for loop iterates through each element exactly once, performing constant time operations (right -= x, comparison, and left += x) in each iteration, which takes O(n) time
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(1) - constant extra space.

• The algorithm only uses a fixed number of variables (left, right, i, and x) regardless of the input size
• No additional data structures are created that scale with the input
• The space used remains constant throughout the execution

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Pivot Definition

The Problem: Many developers mistakenly include the pivot element itself in either the left or right sum. The definition explicitly states sums of elements strictly to the left and strictly to the right, meaning the pivot element should not be included in either sum.

Incorrect Implementation:

# WRONG: Including pivot element in the sums
for i in range(len(nums)):
    left_sum = sum(nums[:i+1])  # Includes nums[i]
    right_sum = sum(nums[i:])    # Also includes nums[i]
    if left_sum == right_sum:
        return i

Correct Approach:

# RIGHT: Excluding pivot element from both sums
for i, x in enumerate(nums):
    right -= x  # Remove current element first
    if left == right:  # Compare sums without current element
        return i
    left += x  # Add to left for next iteration

Pitfall 2: Order of Operations

The Problem: Adding the current element to left before checking the pivot condition, or forgetting to subtract from right first.

Incorrect Implementation:

# WRONG: Adding to left before checking
for i, x in enumerate(nums):
    left += x  # Added too early!
    right -= x
    if left == right:  # This checks wrong sums
        return i

Why This Fails: When checking index i, we need:

• left = sum of elements at indices [0, 1, ..., i-1]
• right = sum of elements at indices [i+1, i+2, ..., n-1]

If we add nums[i] to left before checking, we're actually comparing:

• left = sum of elements at indices [0, 1, ..., i] (includes current)
• right = sum of elements at indices [i+1, i+2, ..., n-1]

Correct Order:

1. Subtract from right (exclude current from right sum)
2. Check if left == right (pivot condition)
3. Add to left (prepare for next iteration)

Pitfall 3: Initial Right Sum Calculation

The Problem: Some implementations try to calculate the right sum as sum(nums) - nums[0] initially, which creates off-by-one errors.

Incorrect Implementation:

# WRONG: Incorrect initial right sum
left = 0
right = sum(nums) - nums[0]  # This is wrong!
for i, x in enumerate(nums):
    if left == right:
        return i
    left += x
    if i + 1 < len(nums):
        right -= nums[i + 1]

Correct Approach: Initialize right as the total sum, then subtract each element as you process it:

left = 0
right = sum(nums)  # Start with total sum
for i, x in enumerate(nums):
    right -= x  # Subtract current element
    # ... rest of logic

Pitfall 4: Returning Wrong Index for Multiple Pivots

The Problem: While the problem asks for the leftmost pivot index, the natural implementation already handles this correctly by returning immediately upon finding the first pivot. However, some might overthink and try to find all pivots first.

Overcomplicated (and inefficient):

# Unnecessary: Finding all pivots then returning the minimum
pivots = []
for i in range(len(nums)):
    # ... calculate sums
    if left_sum == right_sum:
        pivots.append(i)
return min(pivots) if pivots else -1

Simple and Correct:

# Return immediately upon finding first pivot
for i, x in enumerate(nums):
    right -= x
    if left == right:
        return i  # First pivot found, return immediately
    left += x