Find Pivot Index
- 1 min read
- Array
- LC-Easy
3 years ago
Solution
- Read the question description properly- the fact that they mentioned "leftmost pivot index" should be an indication that you should use a brute force approach
- First, calculate the entire sum of the array.
- Then, from left to right, check each index by using it as the pivot, and then using the values seen so far to calculate the left sum and the right sum without doing repeated work.
- Whenever a valid case is found, return the current index.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def pivotIndex(self, nums: List[int]) -> int:
lsum = 0
total_sum = sum(nums)
for pivot in range(len(nums)):
rsum = total_sum - lsum - nums[pivot]
if lsum == rsum:
return pivot
lsum += nums[pivot]
return -1