LeetCode //C - 724. Find Pivot Index

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.
 

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

Constraints:

• $1<=nums.length<=10^4$
• -1000 <= nums[i] <= 1000

From: LeetCode
Link: 724. Find Pivot Index

Solution:

Ideas：

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

2. Iterate and Compare Sums: Iterate through each element of the array. For each index, calculate the left sum (which starts from 0 and accumulates as we iterate). The right sum at any index can be obtained by subtracting the current left sum and the current element from the total sum. If at any point, the left sum equals the right sum, return the current index.

3. No Pivot Found Case: If no such index is found, return -1.

Code:

int pivotIndex(int* nums, int numsSize) {
   
    int totalSum = 0, leftSum = 0;

    // Calculate the total sum of the array
    for (int i = 0; i < numsSize; i++) {
   
        totalSum += nums[i];
    }

    // Iterate through the array to find the pivot index
    for (int i = 0; i < numsSize; i++) {
   
        // Right sum is total sum minus left sum minus current element
        if (leftSum == (totalSum - leftSum - nums[i])) {
   
            return i;
        }
        leftSum += nums[i];
    }

    // Return -1 if no pivot index is found
    return -1;
}