FInd Pivot index

Problem Statement:

Given an array of integers nums, your task is to find the pivot index. The pivot index is the index where the sum of all the numbers to the left of the index is equal to the sum of all the numbers to the right of the index. If no such index exists, return -1. If there are multiple pivot indexes, return the left-most pivot index.

Approach:

1. Calculate Total Sum: First, calculate the sum of all elements in the array.

2. Iterate and Compare: As you iterate through the array, keep track of the sum of elements to the left of the current index. For each element, calculate the sum of elements to the right by subtracting the left sum and the current element from the total sum.

3. Check Condition: If the left sum equals the right sum at any index, that index is the pivot index.

4. Return: If you find such an index, return it; otherwise, return -1.

Code Implementation:

class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        int leftSum = 0;

        // Step 1: Calculate the total sum of the array
        for (int num : nums) {
            totalSum += num;
        }

        // Step 2: Iterate through the array and check the pivot condition
        for (int i = 0; i < nums.length; i++) {
            // rightSum = totalSum - leftSum - nums[i]
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;  // pivot index found
            }
            leftSum += nums[i];
        }

        // Step 3: If no pivot index is found, return -1
        return -1;
    }
}

Dry Run:

Let's take an example array and perform a dry run:

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

1. Step 1: Calculate the total sum:

    totalSum = 1 + 7 + 3 + 6 + 5 + 6 = 28
   

2. Step 2: Initialize leftSum = 0. Iterate through the array and check the pivot condition:

   • Iteration 1 (i = 0):

     • Current element: nums[0] = 1

     • leftSum = 0

     • rightSum = totalSum - leftSum - nums[i] = 28 - 0 - 1 = 27

     • leftSum != rightSum, so continue.

     • Update leftSum = leftSum + nums[0] = 0 + 1 = 1

   • Iteration 2 (i = 1):

     • Current element: nums[1] = 7

     • leftSum = 1

     • rightSum = totalSum - leftSum - nums[i] = 28 - 1 - 7 = 20

     • leftSum != rightSum, so continue.

     • Update leftSum = leftSum + nums[1] = 1 + 7 = 8

   • Iteration 3 (i = 2):

     • Current element: nums[2] = 3

     • leftSum = 8

     • rightSum = totalSum - leftSum - nums[i] = 28 - 8 - 3 = 17

     • leftSum != rightSum, so continue.

     • Update leftSum = leftSum + nums[2] = 8 + 3 = 11

   • Iteration 4 (i = 3):

     • Current element: nums[3] = 6

     • leftSum = 11

     • rightSum = totalSum - leftSum - nums[i] = 28 - 11 - 6 = 11

     • leftSum == rightSum, so we found the pivot index at i = 3.

     • Return 3.

3. Step 3: Since a pivot index was found in Step 2, return the index 3.

Conclusion:

The pivot index for the array [1, 7, 3, 6, 5, 6] is 3, where the sum of elements to the left (1 + 7 + 3 = 11) equals the sum of elements to the right (5 + 6 = 11).

If no such index is found, the function returns -1.