Leetcode #03: ‘Find Pivot Index’

Do you know what a pivot index is in an array?
It’s an index where the sum of all the elements to the left of the index is equal to the sum of all the elements to the right of it. Finding the pivot index in an array is a common programming problem that can be encountered in real-world applications.

In this article, I’ll introduce you to an efficient Python solution that uses a two-pointer approach to find the pivot index in an array. I will discuss the step-by-step process of the algorithm and discuss its time and space complexity. So, if you’re curious to learn a new technique to solve the pivot index problem, read on!

Problem:

Given an array of integers nums, find the pivot 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 there is no such index, return -1. If there are multiple pivot indexes, return the left-most pivot index.

Solution:

The idea behind this solution is to use two pointers, leftSum and rightSum, to keep track of the sum of all the numbers strictly to the left and right of the current index, respectively.

We start by initializing leftSum to 0 and rightSum to the sum of all the numbers in the array. Then, we iterate through each element of the array using a for loop and update leftSum and rightSum for each element.

For each element, we subtract it from rightSum and check if leftSum is equal to rightSum. If they are equal, we have found the pivot index and returned it. If there is no such index, we return -1.

Here’s the Python code for the solution:

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Initialize the leftSum to zero and the rightSum to the sum of all elements in the array
        leftSum, rightSum = 0, sum(nums)
        
        # Iterate through each element of the array using the enumerate() function
        for idx, ele in enumerate(nums):
            # Subtract the current element from the rightSum to calculate the sum of all elements to the right of the current index
            rightSum -= ele
            
            # If the leftSum is equal to the rightSum, return the current index as the pivot index
            if leftSum == rightSum:
                return idx
            
            # Add the current element to the leftSum to calculate the sum of all elements to the left of the current index
            leftSum += ele
        
        # If there is no pivot index, return -1
        return -1

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of elements in the input array. This is because we need to iterate through each element of the array once to calculate the sum of all elements strictly to the left and right of each index.

Space Complexity:

The space complexity of this algorithm is O(1), which means that the amount of memory used by the algorithm does not increase as the input size grows. This is because we only use two constant-sized variables (leftSum and rightSum) to keep track of the sum of elements.

Pivot Index

Conclusion:

In conclusion, we have discussed the problem of finding the pivot index in an array and presented a Python solution that uses two pointers to keep track of the sum of elements to the left and right of each index. We also analyzed the time and space complexity of the algorithm and concluded that the algorithm has a time complexity of O(n) and a space complexity of O(1).

This algorithm is a very efficient and optimal solution to this problem, making it a good choice for real-world applications.

Happy Coding :)

— Shruti Mandaokar

#coding #programming #algorithms #python #computerscience #arrays #problem-solving #softwareengineering #tech #opensource #datascience #development #codinglife #learnprogramming #pivot