Find Pivot Index

---

Intuition

• You could use Prefix and Postfix to solve this problem. Note that it is a bit awkward since when you calculate the prefix, technically prefix[i] is the prefix of the i - 1th element, and postfix[i + 1] is the postfix of the i + 1th element.
  • This is because in practice, you prepend 0’s to avoid boundary collisions.
• Alternatively, the problem could be solved simply with a current sum, subtracting from the right elements and adding to the left, thereby representing prefix and postfix.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

Two Pointers

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left_sum = 0
        right_sum = sum(nums)
 
        for i in range(len(nums)):
            right_sum -= nums[i]
            if left_sum == right_sum:
                return i
            left_sum += nums[i]
            
        return -1

Prefix and Postfix

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        prefix = [0]
        for i, num in enumerate(nums):
            prefix.append(prefix[i] + nums[i])
 
        postfix = [0] * (len(nums) + 1)
        for i in range(len(nums) - 1, -1, -1):
            postfix[i] = nums[i] + postfix[i + 1]
 
        for i in range(len(nums)):
            if prefix[i] == postfix[i + 1]:
                return i
 
        return -1

Cards

START Basic Front: Find Pivot Index Back: Keep a running left_sum and right_sum.

END

---

References

• Find Pivot Index