Time Complexity: $\mathcal O(N)$.

Solution 1

The pivot index must have the same sum on its left and its right. To calculate this, we can create a prefix sum of the $\texttt{nums}$ array (in my solution it is cushioned with one $0$ at index $0$). Loop through every index in the $\texttt{psums}$ array and check whether

If this is true, we can return our current index because the problem wants the left-most index. If it finishes the for-loop without returning, it means there is no valid pivot index so return $-1$.

Copy
from typing import List


class Solution:
	def pivotIndex(self, nums: list[int]) -> int:
		psums = [0]
		for i in range(len(nums)):
			# Notice i in psums is always one less than the current index
			psums.append(psums[i] + nums[i])

Solution 2

The alternate solution does not require an array to store the sums. Instead, we only need the total sum of the array and the current sum at each index (exclusive of index). With this we check whether

Note: This is technically the same solution as solution 1, but it is another way to think about approaching this question.

Copy
from typing import List


class Solution:
	def pivotIndex(self, nums: List[int]) -> int:
		total = sum(nums)

		curSum = 0
		for i in range(len(nums)):
			# curSum is up to i not inclusive of i.
			if curSum == total - curSum - nums[i]:
				return i
			# updating curSum
			curSum += nums[i]
		return -1