Find Pivot Index (Leet Code-724)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 724. This is a Leet code problem named Find Pivot Index. We will solve it using python and it is the best space and time-optimized solution.

Question of Find Pivot Index

Given an array of integers nums, calculate the pivot index of this 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 also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example

Example 1

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000

Approach to solve Find Pivot Index

To solve this problem we will create two variables called left and right. We initialize the left with zero and right with sum of all arrays. We traverse in list and simply adding elements in left variable. If left variable equals to right variable than we return the position of that variable otherwise we subtract that number by right and repeat till we find pivot index or reach end of loop.

Algorithm

This method performs the following steps to Find Pivot Index

Initialize left variable with zero.
Initialize right variable with sum of all elements of list
Repeat steps 4 to 7 for each elements say variable x of list.
Add x in left variable left.
Check if left and right variable are equal.
If step 5 is true then return position of variable x and break for loop.
Assign right = right – x.
If we don’t find any pivot element then return -1.

Python Code for Find Pivot Index

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