LeetCode 724: Find Pivot Index

Question

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:

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

Solution (Python)

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum_l = 0                # Initialize the left sum to 0
        sum_r = sum(nums)        # Initialize the right sum to the total sum of the array
        
        for i in range(len(nums)):
            sum_r -= nums[i]     # Remove the current element from right sum
            
            if sum_r == sum_l:   # Check if left sum equals right sum
                return i         # Found pivot index, return it
                
            sum_l += nums[i]     # Add current element to left sum
            
        return -1                # No pivot index found

This code is solving the “Pivot Index” problem: finding the index in an array where the sum of elements to the left equals the sum of elements to the right.

Solution Walkthrough:

Let’s trace through an example with nums = [1, 7, 3, 6, 5, 6]:

1. Initialize sum_l = 0, sum_r = sum(nums) = 28
2. For i = 0:
   • sum_r = 28 - 1 = 27
   • Check if 0 == 27 → False
   • Update sum_l = 0 + 1 = 1
3. For i = 1:
   • sum_r = 27 - 7 = 20
   • Check if 1 == 20 → False
   • Update sum_l = 1 + 7 = 8
4. For i = 2:
   • sum_r = 20 - 3 = 17
   • Check if 8 == 17 → False
   • Update sum_l = 8 + 3 = 11
5. For i = 3:
   • sum_r = 17 - 6 = 11
   • Check if 11 == 11 → True
   • Return 3 as the pivot index

The algorithm is clever because at each index, it:

• Removes the current element from the right sum
• Checks if left sum equals right sum
• Adds the current element to left sum

This way, we’re effectively shifting elements from right to left one by one until we find a balance point, or determine none exists.

Time and Space Complexity Analysis

Time Complexity: O(n)

• Initial sum(nums) operation: O(n) - It requires iterating through the entire array once to calculate the sum
• Main loop: O(n) - The algorithm loops through each element in the array exactly once
• Operations inside the loop: O(1) - All operations (subtraction, addition, comparison) are constant time

Overall, this gives us a time complexity of O(n), where n is the length of the input array.

Space Complexity: O(1)

• Input storage: O(n) - The input array itself, but we don’t count this in the space complexity as it’s part of the input
• Additional variables:
  • sum_l: O(1) - A single integer to store the left sum
  • sum_r: O(1) - A single integer to store the right sum
  • Loop variable i: O(1)

Since we’re using only a constant amount of extra space regardless of the input size, the space complexity is O(1).

Why This Is Efficient

This solution is optimal because:

1. It avoids recalculating sums repeatedly by maintaining running sums
2. It processes each element exactly once
3. It uses constant extra space

An alternative approach might recalculate left and right sums at each index, which would result in O(n²) time complexity. This solution cleverly avoids that by using the relationship between consecutive positions’s sums.