Problem Statement

Given an integer array nums, determine the pivot index of this array.

The pivot index divides the array in such a way that the sum of the numbers on its left side is exactly equal to the sum of the numbers on its right side.

If the index is at the beginning, the sum to its left is considered zero, similarly for an index at the end.

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

Examples

• Example 1:

  • Input: [1, 2, 3, 4, 3, 2, 1]
  • Expected Output: 3
  • Justification: The sum of the numbers to the left of index 3 (1 + 2 + 3) is 6, and the sum to its right (3 + 2 + 1) is also 6.

• Example 2:

  • Input: [2, 1, 3]
  • Expected Output: -1
  • Justification: There is no pivot index that exists in the given array.

• Example 3:

  • Input: [1, 100, 50, -51, 1, 1]
  • Expected Output: 1
  • Justification: The sum to the left of index 1 is 1, and the sum to its right (50 + (-51) + 1 + 1) is 1.

Solution

To solve this problem, we'll employ a two-step approach to ensure efficiency and simplicity. Initially, we calculate the total sum of all array elements. Knowing the total, we can iterate through the array, maintaining a running sum of elements to the left of the current index. At any point, if the left sum is equal to the total minus the left sum minus the current element, we've found our pivot index. This method is effective because it only requires a single pass through the array after calculating the total sum, making it efficient in terms of both time and space.

The reason this approach is particularly appealing is its simplicity and the fact that it leverages the arithmetic property of sums. This allows for quick determination of the pivot index without needing complex data structures or multiple passes through the array, making it an ideal choice for this problem.

Step-by-step algorithm:

• Calculate the total sum of the array elements.
• Initialize a variable to keep track of the sum of elements to the left of the current index (leftSum) and set it to 0.
• Iterate through the array:
  • At each index, check if leftSum is equal to the total sum minus leftSum minus the current element. If true, return the current index as the pivot index.
  • Otherwise, add the current element to leftSum and continue.
• If no pivot index is found during the iteration, return -1.

Algorithm Walkthrough

Using the input [1, 2, 3, 4, 3, 2, 1]:

Step 1: Calculate the Total Sum of the Array

1. Initialize the totalSum variable to 0.
2. Add each element in the array to totalSum:
   • After adding 1, totalSum is 1.
   • After adding 2, totalSum is 3.
   • After adding 3, totalSum is 6.
   • After adding 4, totalSum is 10.
   • After adding the second 3, totalSum is 13.
   • After adding the second 2, totalSum is 15.
   • After adding the second 1, totalSum is 16.

Step 2: Iterate Through the Array to Find the Pivot Index

1. Initialize the leftSum variable to 0.
2. Iterate through the array, calculating the leftSum and comparing it with the sum of elements to the right of the current index to find the pivot index.

Iteration 1: Index 0 ([1])

• leftSum is 0.
• The sum to the right is totalSum - leftSum - nums[i] = 16 - 0 - 1 = 15.
• The sums are not equal, so continue.

Iteration 2: Index 1 ([1, 2])

• Update leftSum to 1 (0 + 1).
• The sum to the right is totalSum - leftSum - nums[i] = 16 - 1 - 2 = 13.
• The sums are not equal, so continue.

Iteration 3: Index 2 ([1, 2, 3])

• Update leftSum to 3 (1 + 2).
• The sum to the right is totalSum - leftSum - nums[i] = 16 - 3 - 3 = 10.
• The sums are not equal, so continue.

Iteration 4: Index 3 ([1, 2, 3, 4])

• Update leftSum to 6 (3 + 3).
• The sum to the right is totalSum - leftSum - nums[i] = 16 - 6 - 4 = 6.
• The sums are equal, which means we've found the pivot index at 3.

Final Result:

The pivot index for the array [1, 2, 3, 4, 3, 2, 1] is 3, as the sum of the numbers to the left of index 3 is equal to the sum of the numbers to its right, both summing to 6.

Code

Complexity Analysis

Time Complexity

The time complexity for the algorithm is O(n), where (n) is the number of elements in the input array. This efficiency is due to the algorithm requiring a single pass to calculate the total sum and another pass to find the pivot index, making the operations linear in time relative to the size of the input.

Space Complexity

The space complexity of the algorithm is O(1). This is because the amount of extra space required does not scale with the size of the input array.