720. Find Pivot Index

Problem Statement in English

You’re given an array of integers nums.

You need to find an index $i$ such that the sum of elements to the left of $i$ is equal to the sum of elements to the right of $i$.

If no such index exists, return -1.

Approach

We make 2 passes on this array. A left pass, and a right pass.

In each pass we calculate the prefix sum as we go.

Finally we check if the value of the prefix sum in the left pass is equal to the prefix sum in the right pass, if it is, we return the index, else we return $-1$.

Solution in Python

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        leftPass = [0 for _ in range(len(nums))]
        rightPass = [0 for _ in range(len(nums))]

        for i in range(1, len(nums)):
            leftPass[i] = leftPass[i - 1] + nums[i - 1]

        for i in range(len(nums) - 2, -1, -1):
            rightPass[i] = rightPass[i + 1] + nums[i + 1]

            if rightPass[i] == leftPass[i]:
                return i

        return -1

Complexity

• Time: $O(n)$
  Since we process $n$ elements at most. Twice doesn’t matter, since this is Big-O notation.

• Space: $O(n)$
  Since we store $n$ elements at most in the left and right passes.

And we are done.