Problem: Find the Pivot Index

The Pivot Index is defined as the index in an array where the sum of all elements to the left of the index is equal to the sum of all elements to the right of the index.

Problem Breakdown:

Given an integer array nums, the task is to find the pivot index, where:

• The sum of elements before the pivot index is equal to the sum of elements after it.

If no such index exists, return -1.

Example:

Input:

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

Output:

Pivot Index: 3

Explanation:

• At index 3, the sum of elements on the left (1 + 7 + 3 = 11) is equal to the sum on the right (5 + 6 = 11).

Approach:

1. Calculate the Total Sum: We start by calculating the total sum of the array. This will help in quickly calculating the sum of elements to the right of the current index.

2. Iterate through the Array: As we iterate through the array, we maintain a leftSum, which tracks the sum of elements before the current index. For each element at index i, the sum of elements to the right can be calculated as:

   rightSum=totalSum−leftSum−nums[i]text{rightSum} = text{totalSum} – text{leftSum} – text{nums}[i]

   If the leftSum equals the rightSum, we’ve found our pivot index.

3. Return the Pivot Index or -1: If a pivot index is found, return the index; otherwise, return -1 if no such index exists.

C Code Solution:

#include <stdio.h>

int totalSum(int* nums, int numsSize) {
    int total = 0;
    for (int i = 0; i < numsSize; i++) total += nums[i];
    return total;
}

int pivotIndex(int* nums, int numsSize) {
    int total = totalSum(nums, numsSize);
    int leftSum = 0;
    for (int i = 0; i < numsSize; i++) {
        int rightSum = total - leftSum - nums[i];
        if (leftSum == rightSum) return i;
        leftSum += nums[i];
    }
    return -1;
}

int main() {
    int nums[] = {1, 7, 3, 6, 5, 6};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("Pivot Index: %dn", pivotIndex(nums, n));
    return 0;
}

Explanation of the Code:

1. totalSum Function:

   • This function calculates the total sum of the elements in the nums array. It iterates over the array and adds each element to the total.

2. pivotIndex Function:

   • We calculate the totalSum of the array and then initialize leftSum to 0.
   • For each element in the array, we compute the rightSum as the difference between the totalSum, leftSum, and the current element (nums[i]).
   • If leftSum equals rightSum, we return the current index (i) as the pivot index.
   • After checking, we add the current element (nums[i]) to leftSum and move to the next index.

3. Main Function:

   • We initialize the array nums and calculate its size.
   • We call the pivotIndex function to get the pivot index and print the result.

Time Complexity:

• Time Complexity: O(n)O(n), where nn is the number of elements in the array. We traverse the array once to compute the total sum, and then iterate again to find the pivot index.

• Space Complexity: O(1)O(1), since we only use a few extra variables (total, leftSum, and rightSum), and no additional data structures are used.

Example Walkthrough:

Example 1:

Input:

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

• Step 1: Total Sum = 1 + 7 + 3 + 6 + 5 + 6 = 28
• Step 2: Iterate through the array:
  • At index 0: Left Sum = 0, Right Sum = 28 – 0 – 1 = 27 (not a match)
  • At index 1: Left Sum = 1, Right Sum = 28 – 1 – 7 = 20 (not a match)
  • At index 2: Left Sum = 8, Right Sum = 28 – 8 – 3 = 17 (not a match)
  • At index 3: Left Sum = 11, Right Sum = 28 – 11 – 6 = 11 (match, pivot index is 3)

Output:

Pivot Index: 3

Example 2:

Input:

nums = [1, 2, 3]

• Step 1: Total Sum = 1 + 2 + 3 = 6
• Step 2: Iterate through the array:
  • At index 0: Left Sum = 0, Right Sum = 6 – 0 – 1 = 5 (not a match)
  • At index 1: Left Sum = 1, Right Sum = 6 – 1 – 2 = 3 (not a match)
  • At index 2: Left Sum = 3, Right Sum = 6 – 3 – 3 = 0 (not a match)

Output:

Pivot Index: -1