Find Pivot Index (Prefix Sum Made Simple)

The Pivot Index of an array is the index where:

1. Sum of elements on the left = Sum of elements on the right
2. If no such index exists, return -1.

Key Idea

1) Instead of calculating left and right sums again and again (which is slow), we can
2) Compute the total sum of the array.
3) Keep a running left sum. At each index:
-> Right sum = totalSum - leftSum - nums[i]
-> If leftSum == rightSum, that index is the pivot.

This avoids nested loops and makes the solution efficient.

Efficient Approach (Prefix Logic)

Steps:

1. Find total sum.
2. Traverse the array.
3. At each index:

• Check if left sum equals right sum.
• Update left sum.

C++ Implementation

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums)
            totalSum += num;

        int leftSum = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (leftSum == totalSum - leftSum - nums[i])
                return i;

            leftSum += nums[i];
        }

        return -1;
    }
};

Example

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

At index 3: -> Left sum = 1 + 7 + 3 = 11 . -> Right sum = 5 + 6 = 11

So output: 3

Complexity

Time    O(n)
Space   O(1)

Final Takeaway

This problem teaches: How to use prefix sum thinking, How to avoid unnecessary recomputation, How to optimize from O(n²) to O(n)

Simple logic. Clean thinking. Efficient solution. 💪