How to Solve Pivot Index Algorithm in Java

This is my solution to problem 724 on Leet Code.

Given an array of integers nums, write a method that returns the "pivot" index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, return the left-most pivot index.

Example 1:

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.

Example 2:

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

Note:

• The length of nums will be in the range [0, 10000].
• Each element nums[i] will be an integer in the range [-1000, 1000].

First, we check to see if the array is empty. If so, return -1. This is the first edge case.

Return -1 if the array is empty

Next, we need to find the sum of all the numbers in the array. The leet code solution adds all the numbers into one sum. I chose to go a slightly different route.

Let’s use a for loop to traverse through the whole array starting at the second index, which is index 1 (remember, the first number in an array is index 0). The number at the current index (i) is equal to the sum of the current and previous values. This way, we will always have access to the sum of the numbers before the current index.

i equals the sum of the current and previous numbers in the array

When the for loop has finished, the number at the last index of the array will be the sum of all the numbers in the array.

the last index is nums.length -1 because array indices start at 0

Now for the next edge case: if the first and last integer in the array are equal, return 0. This bit of code comes in handy in case the array has only one integer. In that case, the pivot index will be 0.

Return 0 if the array has only one number

It’s time to go through the revised array, starting at index 1. Remember, each index contains the sum of all the values in the array up to that point. If the last index value minus the current index value is equal to the previous index value, return the current index (i). This will be the pivot index.

Finally, return -1. This is just in case the input does not pass our previous if statements and test cases.

Let’s see it in action on the first array example above:

First we ask if the array is empty. It’s not. Now we move to the for loop. Remember, the index starts at 1, so i is equal to 1.

The value at the current index is equal to the sum of the current and previous value. The current index is 1, the current value is 7 and the previous value is 1. So the new number at index 1 will be 8.

We go through the for loop again at the next index, which is two. That means i is equal to 2. At index 2, we add the current value to the previous value. The current value is 3 and the previous value is 8. The new number at index two is 11.

Back to the beginning of the for loop. Go to the next index. i equals three. The current value is 6 and the previous value is 11. The new value at index 3 is 17.

Go through the for loop again. The next index is 4. i equals 4. The current value is 5 and the previous value is 17. The new value of index 4 is 22.

Here we are at the end of the array, going through the for loop for that last time. The index is 5. i equals 5. The current value is 6 and the previous value is 22. The new value at index 5 is 28.

Keep in mind, the last index contains the sum of all the numbers in the original array. Now the code will ask if the last number is equal to the first number. It’s not. So let’s move on.

We use another for loop to go through the revised array starting at index 1. We are only looking for the pivot index. If the last value (28) minus the current value is equal to the previous value, return the current index (i). This will be the pivot index.

The first iteration of the for loop: i equals 1. The current value is 8 and the previous value is 1. 28- 8 equals 20, not 1. The for loop iterates again.

We do the same thing for index 2. The current value is 11 and the previous value is 8. 28- 11 equals 17, not 8. Back to the for loop.

Now, i equals 3. The current value is 17 and the previous value is 11. 28- 17 equals 11, which is the previous value. The program is instructed to return the current index (i), which is 3. 3 is the pivot index.

Time Complexity: This will take O(N) time. N is the number of integers.
Space Complexity: This will take O(1) space.

You can find the source code with notes on my github profile.

I’m raising $7k for my college tuition. Please help me out by donating and/or sharing my gofundme.