Leetcode 724 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.

The problem described is asking to find the “pivot index” of an array of integers. A pivot index is an index in the array where the sum of all the numbers to the left of that index is equal to the sum of all the numbers to the right of that index.

For example, consider the following array of integers:

nums = [1, 7, 3, 6, 5, 6]

The pivot index of this array is 3, because the sum of the numbers to the left of index 3 (1 + 7 + 3 = 11) is equal to the sum of the numbers to the right of index 3 (5 + 6 = 11).

If there is no such index in the array where the sum of the numbers to the left is equal to the sum of the numbers to the right, then we return -1.

It’s important to note that if the pivot index is at the beginning or end of the array, we assume that there are no elements to the left or right, respectively. So the sum of the elements to the left or right of the pivot index would be 0 in that case.
Let us see another example

nums = [2, 1, -1, 5, 6]

In this case, there is no pivot index since no index satisfies the condition. The sum of the elements to the left of index 0 is 0, while the sum of the elements to the right of index 0 is 11.

The sum of the elements to the left of index 1 is 2, while the sum of the elements to the right of index 1 is 4. The sum of the elements to the left of index 2 is 3, while the sum of the elements to the right of index 2 is 3.

The sum of the elements to the left of index 3 is 2, while the sum of the elements to the right of index 3 is 1. Finally, the sum of the elements to the left of index 4 is 1, while the sum of the elements to the right of index 4 is 0.

Therefore, the function should return -1.

We can have multiple solutions for Find Pivot Index problem, let’s discuss few of them in this article.

Solution 1: Prefix Sums

One approach to solve this problem is by using prefix sums. A prefix sum is the sum of all elements up to a certain index in an array. Using prefix sums, we can calculate the sum of all elements to the left and right of each index, and check whether they are equal.

Pseudocode:

1. Initialize a variable ‘total_sum’ to hold the sum of all elements in the input array ‘nums’.
2. Initialize a variable ‘left_sum’ to 0.
3. Iterate through the input array ‘nums’, and for each element ‘num’: a. Calculate the sum of all elements to the right of ‘num’ as ‘right_sum’ = ‘total_sum’ – ‘left_sum’ – ‘num’. b. Check whether ‘left_sum’ is equal to ‘right_sum’. If so, return the current index. c. Otherwise, update ‘left_sum’ by adding ‘num’ to it.
4. If no pivot index is found, return -1.

In this solution, we first calculate the sum of all elements in the array, which we can use to calculate the sum of all elements to the right of each index.

We start with the left sum set to 0, and for each element in the input array, we calculate the sum of all elements to the right by subtracting the current element and the left sum from the total sum of the array.

We then check whether the left and right sums are equal at the current index. If they are, we have found the pivot index, and we return it. If not, we update the left sum by adding the current element to it and continue iterating through the array. If we reach the end of the array without finding a pivot index, we return -1.

Time Complexity: O(n), where n is the length of the input array ‘nums’. We iterate through the array once.

Space Complexity: O(1). We only need to store a few variables, and the space used does not depend on the size of the input.

Solution 2: Two-Pointer Approach

Another approach to solve this problem is by using a two-pointer approach. We initialize two pointers, one at the beginning of the array and one at the end of the array. We then compare the sums of elements at the two pointers, and move the pointer with the smaller sum towards the middle of the array until we find the pivot index.

Pseudocode:

1. Initialize two pointers ‘left’ and ‘right’ to the beginning and end of the input array ‘nums’, respectively.
2. Initialize variables ‘left_sum’ and ‘right_sum’ to hold the sums of elements to the left and right of the pointers, respectively.
3. While ‘left’ is less than ‘right’: a. If ‘left_sum’ is less than ‘right_sum’, increment ‘left’ and update ‘left_sum’ by adding the element at the new ‘left’ index to it. b. If ‘right_sum’ is less than ‘left_sum’, decrement ‘right’ and update ‘right_sum’ by adding the element at the new ‘right’ index to it. c. If ‘left_sum’ is equal to ‘right_sum’, check whether ‘left+1’ is equal to ‘right-1’. If so, return ‘left+1’ (or ‘right-1’, since they are equal). Otherwise, increment ‘left’ and decrement ‘right’, and update ‘left_sum’ and ‘right_sum’ accordingly.
4. If no pivot index is found, return -1.

In this solution, we start with two pointers, one at the beginning of the array and one at the end of the array. We calculate the sum of all elements to the left and right of these pointers, and compare them.

If the left sum is less than the right sum, it means that we need to move the left pointer towards the middle of the array to increase the left sum.

Similarly, if the right sum is less than the left sum, we move the right pointer towards the middle of the array to increase the right sum. We keep doing this until the left and right pointers meet or cross each other. If we find a pivot index, we return it. Otherwise, we return -1.

It’s important to note that when the left and right pointers are adjacent to each other and the sums are equal, we can return either pointer since the sum of elements to the left and right of both pointers is 0.

Time Complexity: O(n), where n is the length of the input array ‘nums’. In the worst case, we need to traverse the array twice from left and right to find the pivot index.

Space Complexity: O(1). We only need to store a few variables, and the space used does not depend on the size of the input.

Solution 3: Binary Search

In this approach, we calculate the prefix sum of the input array and store it in a new array. Then, we perform binary search on the prefix sum array to find the pivot index.

Pseudocode:

1. Initialize an array ‘prefix_sum’ to store the prefix sum of the input array ‘nums’.
2. Initialize a variable ‘total_sum’ to hold the sum of all elements in ‘nums’.
3. For each element in ‘nums’, set the corresponding element in ‘prefix_sum’ to the sum of all elements up to and including that element.
4. Initialize a variable ‘left’ to 0, and ‘right’ to the length of ‘prefix_sum’ minus 1.
5. While ‘left’ is less than or equal to ‘right’: a. Calculate the midpoint as ‘mid’ = (left + right) // 2. b. If the sum of elements up to ‘mid’ is less than the sum of elements from ‘mid’ to the end of the array, set ‘left’ to ‘mid’ plus 1. c. If the sum of elements up to ‘mid’ is greater than the sum of elements from ‘mid’ to the end of the array, set ‘right’ to ‘mid’ minus 1. d. If the sum of elements up to ‘mid’ is equal to the sum of elements from ‘mid’ to the end of the array, return ‘mid’.
6. If no pivot index is found, return -1.

In this solution, we first calculate the prefix sum of the input array ‘nums’, which gives us an array where each element represents the sum of all elements up to and including the corresponding element in ‘nums’. We then perform binary search on the prefix sum array to find the pivot index.

In each iteration of the binary search, we calculate the midpoint and compare the sum of elements up to the midpoint with the sum of elements from the midpoint to the end of the array.

If the sum of elements up to the midpoint is less than the sum of elements from the midpoint to the end of the array, it means that the pivot index must be to the right of the midpoint.

Therefore, we update the left pointer to ‘mid’ plus 1. Similarly, if the sum of elements up to the midpoint is greater than the sum of elements from the midpoint to the end of the array, it means that the pivot index must be to the left of the midpoint.

Therefore, we update the right pointer to ‘mid’ minus 1. We keep doing this until we find the pivot index or the left pointer exceeds the right pointer.

Time Complexity: O(nlogn), where n is the length of the input array ‘nums’. We need to perform binary search on the prefix sum array, which takes O(logn) time, and we also need to calculate the prefix sum array, which takes O(n) time.

Space Complexity: O(n), where n is the length of the input array ‘nums’. We need to store the prefix sum array, which has the same length as the input array.

Which one is better Solution

All three solutions have their own advantages and disadvantages, but Solution 1, which uses prefix sums, is the most efficient in terms of both time and space complexity.

It has a time complexity of O(n) and a space complexity of O(1), which are the best among the three solutions.

Solution 2, which uses the two-pointer approach, has similar time and space complexity as Solution 1, but may be slightly slower in practice due to the extra comparisons and updates that are needed in the while loop.

Solution 3, which uses binary search, has a slower time complexity of O(nlogn) and a higher space complexity of O(n) than Solutions 1 and 2.

However, it may be useful in situations where the input array is very large and the prefix sum array can be preprocessed and reused multiple times. Overall, if time and space efficiency are the top priorities, Solution 1 may be the best choice.

Find Pivot Index Java Solution:

public int pivotIndex(int[] nums) {
    int totalSum = 0;
    int leftSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    for (int i = 0; i < nums.length; i++) {
        int rightSum = totalSum - leftSum - nums[i];
        if (leftSum == rightSum) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
}

Find Pivot Index Python Solution:

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        right_sum = total_sum - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num
    return -1

Find Pivot Index Ruby Solution:

def pivot_index(nums)
  total_sum = nums.inject(0, :+)
  left_sum = 0
  nums.each_with_index do |num, i|
    right_sum = total_sum - left_sum - num
    return i if left_sum == right_sum
    left_sum += num
  end
  -1
end

Find Pivot Index JavaScript Solution:

function pivotIndex(nums) {
    let totalSum = nums.reduce((acc, curr) => acc + curr, 0);
    let leftSum = 0;
    for (let i = 0; i < nums.length; i++) {
        let rightSum = totalSum - leftSum - nums[i];
        if (leftSum === rightSum) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
}