[link](https://leetcode.com/problems/find-pivot-index)

---

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:

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

#### Constraints:

- 1 <= nums.length <= 104
- -1000 <= nums[i] <= 1000

---

The method pivotIndex initializes variables totalL and totalR to store the cumulative sums of the elements from the left and right sides of the nums list, respectively.

Two lists prefixSumL and prefixSumR are created to store the cumulative prefix sums from the left and right sides of the nums list, respectively.

In the first loop, the method calculates the prefix sums from the left side by iterating through nums, updating totalL at each step, and appending the cumulative sum to the prefixSumL list.

In the second loop, the method calculates the prefix sums from the right side by iterating through nums in reverse order, updating totalR at each step, and appending the cumulative sum to the prefixSumR list.

Since the second loop traverses nums in reverse order, the prefixSumR list is created in reverse. To correct this, the line prefixSumR = prefixSumR[::-1] is used to reverse the prefixSumR list back to its original order.

Finally, the method compares the elements at each index k in prefixSumL and prefixSumR. If the prefix sums are equal at an index k, it means that the pivot index is found, and the method returns the index. Otherwise, it returns -1 if no pivot index is found.

#### Solution 1

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        totalL, totalR = 0, 0
        prefixSumL, prefixSumR = [], []
        for i in range(len(nums)):
            totalL += nums[i]
            prefixSumL.append(totalL)
            
        for j in range(len(nums) - 1, -1, -1):
            totalR += nums[j]
            prefixSumR.append(totalR)

        prefixSumR = prefixSumR[::-1]

        for k in range(len(nums)):
            if prefixSumL[k] == prefixSumR[k]:
                return k
        return -1
        

O(T): O(n)
O(S): O(n)

---

The method pivotIndex first calculates the total sum of all elements in the nums list using the sum function and stores it in the variable total. It initializes a variable leftSum to keep track of the cumulative sum from the left side of the current index.

The method then iterates through the nums list using a loop. At each iteration i, it calculates the rightSum as total - leftSum - nums[i], which is the sum of elements to the right of the current index.

It compares leftSum and rightSum. If they are equal, it means the pivot index is found, and the method returns the index i. If the pivot index is not found, it updates leftSum by adding the current element nums[i] to it, and the loop proceeds to the next iteration. If no pivot index is found during the loop, the method returns -1.

#### Solution 2

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums) # O(n)
        leftSum = 0
        for i in range(len(nums)):
            rightSum = total - leftSum - nums[i]
            if leftSum == rightSum:
                return i
            leftSum += nums[i]
        return -1
        

O(T): O(n)
O(S): O(1)