Leetcode – Find Pivot Index Solution in Python

In this comprehensive guide, we will unravel the ‘Find Pivot Index’ problem from Leetcode. This problem is an excellent demonstration of array manipulation, a commonly tested topic in coding interviews.

Before we delve into the problem-solving approaches, let’s first understand the problem statement.

Problem Statement

The problem statement from Leetcode is as follows:

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 rule applies to the right edge as well.

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

Examples:

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 first index where this occurs.

Input: nums = [1,2,3]

Output: -1

Explanation: There is no index that satisfies the conditions in the problem statement.

Approach 1: Naive Solution

The simplest approach to solve this problem would be to use two nested loops.

The outer loop iterates over the array. For each index, the inner loop calculates the sum of elements to the left and right of that index. If the two sums are equal, we return the current index. If we don’t find a pivot index by the end of the loop, we return -1.

Here is the Python code that implements this logic:

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

This solution works, but it’s not very efficient. The time complexity is O(n^2), which can be too slow for large inputs.

Approach 2: Prefix Sum

A more efficient solution is to first calculate a prefix sum of the array. The prefix sum is an array where the element at each index is the sum of all elements up to that index in the original array.

Once we have the prefix sum, we can calculate the sum of elements to the left and right of each index in O(1) time. The left sum for an index i is prefix_sum[i-1], and the right sum is prefix_sum[-1] - prefix_sum[i].

Here is the Python code that implements this logic:

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

This solution is much more efficient than the naive one. The time complexity is O(n), and the space complexity is also O(n) due to the extra space required for the prefix sum.

Approach 3: Optimal Solution

While the prefix sum approach improves the time complexity, it uses extra space. We can further optimize the solution to use constant space.

The key observation is that the total sum of the array is equal to the left sum plus the right sum plus the element at the pivot index. Therefore, for each index, we can calculate the right sum as the total sum minus the left sum minus the element at the current index.

Here is the Python code that implements this logic:

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

This solution has a time complexity of O(n) and a space complexity of O(1), which is the most efficient solution for this problem.

Conclusion

In this extensive guide, we walked through the ‘Find Pivot Index’ problem from Leetcode. We started with a simple but inefficient solution, then improved the efficiency using the prefix sum approach, and finally arrived at the most optimal solution.