Find Pivot Index - Leetcode Solution

Problem Statement:

Given an array of integers nums, calculate the pivot index of the array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This applies to the right edge of the array as well.

If there is no such index, the function should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example:

Input: nums = [1,7,3,6,5,6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the leftmost pivot index.

Solution:

The easiest approach to solve this problem is to compute the total sum of the array first. Then traverse through the array, checking at each index if the sum of all the elements to its left is equal to the sum of all the elements to its right.

If yes, then return that index as the pivot index. If no such index is found, then return -1.

Let's implement this approach in code:

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

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input array. We traverse through the array only once.

Space Complexity:

The space complexity of this solution is O(1), as we are not using any extra space except for a few variables to store the sum values and the loop index.

1