Find Pivot Index

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

Key Insights

• The pivot index is determined by comparing the sum of elements on the left with the sum of elements on the right.
• We can calculate the total sum of the array first, then use a running sum to find the pivot index efficiently.
• The left sum can be updated iteratively as we progress through the array, avoiding the need for nested loops.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a single pass approach:

1. Calculate the total sum of the array.
2. Initialize a variable to keep track of the left sum, which starts at 0.
3. Iterate through the array, updating the left sum and calculating the right sum as total_sum - left_sum - nums[i].
4. If at any index the left sum equals the right sum, return that index.
5. If no index is found by the end of the iteration, return -1.

The algorithm uses a simple loop and only requires a few variables, making it space efficient.

Code Solutions