Find Pivot Index

In this problem, we will receive an array of numbers, and we must return the index where the elements sum of left side of this index, is the same as well as right side.

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

Notice that the pivot value does not count for either side. But we will have to use it in the next steps.

We can approach this problem splitting it in several components:

  • Sum of every array element
  • Left elements sum
  • Temporal pivot
var sum = nums.reduce(0, +)   // we could use for loop to sum every element also
var left = 0

Now, the approach would be loop the array, to check if the left sum if equals to sum of whole array less left sum and pivot value.

We could make it like that:

left == sum - (left + pivot)

If this is operations is true, would means we are in the middle of the same sum value.

If not, we will have to sum the current pivot value to left variable. (And then, move ahead one position into the array).

left += pivot

Finally, if we would not find the equals positions, the loop will finish without any return. And then we will return -1 value.

class Solution {
    func pivotIndex(_ nums: [Int]) -> Int {
        var sum = nums.reduce(0, +)                 // 1. Sum whole array into unique value
        var left = 0                                // 2. Initialization of left growing side
        
        for (index, pivot) in nums.enumerated() {
            if left == sum - (left + pivot) {       // 3. Check if both sides are equals without pivot
                return index
            }
            
            left += pivot                           // 4. Sum pivot value to left side
        }
        
        return -1                                   // 5. Returning nil value if does not exist any chance
    }
}
Time complexity: O(n)
Due we only loop every element of the given array

Space complexity: O(1)
Due we are creating a variable to update the sum value