Problem

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.

Examples

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

Solution

Method 1 - Using Prefix Sum

public int pivotIndex(int[] nums) {
	if (nums.length == 0) {
		return -1;
	}

	// cumulative sum of nums array
	for(int i = 1; i < nums.length ; i++){
		nums[i] += nums[i-1] ;
	}

	int l = 0;
	int r = nums.length - 1;


	// if the numbers at the first and last index are equal, return 0
	// This also handles arrays that have only 1 character
	if (nums[l] - nums[r] == 0) {
		return 0;
	}
	for (int i = 1; i < nums.length; i++) {
		/* If the number at the last index minus the number at the current index
		 * is equal to the previous index, return  the current index
		 * */
		if (nums[r] - nums[i] == nums[i - 1]) {
			return i;
		}
	}

	return -1;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1), but modifies array.

Method 2 - Using Prefix Sum but without Modifying Array 🏆

We can keep track of the left sum and right sum and return the index when they are equal. Left sum can be easily calculated when we loop on array from 0th index to n-1. For calculating the right sum, we can calculate total sum and subtract left sum and current index.

Code

Java
public int pivotIndex(int[] nums) {
	int sum = 0;
	for(int i = 0; i<nums.length; i++){
		sum += nums[i];
	}

	int leftSum = 0;
	int rightSum = sum;
	for(int i = 0; i < nums.length; i++){
		rightSum = sum - leftSum - nums[i];
		if(leftSum == rightSum) {
			return i;
		}
		leftSum += nums[i];
	}
	return -1;
}