Here are your structured notes for “Find Pivot Index” from LeetCode:

Problem Link

724. Find Pivot Index – LeetCode

Problem Statement

Given an array of integers nums, find the pivot index of this array.

The pivot index is the index where:

Sum of elements strictly to the left of the index

Sum of elements strictly to the right of the index

If such an index exists, return the leftmost pivot index. Otherwise, return -1.

Examples

Example 1:

Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
Left sum  = 1 + 7 + 3 = 11
Right sum = 5 + 6     = 11

Example 2:

Input: nums = [1, 2, 3]
Output: -1
Explanation:
No index satisfies the condition.

Example 3:

Input: nums = [2, 1, -1]
Output: 0
Explanation:
Left sum = 0
Right sum = 1 + (-1) = 0

Constraints

• 1 <= nums.length <= 10⁴

• -1000 <= nums[i] <= 1000

Intuition

We are looking for an index i such that:

sum(nums[0] to nums[i-1]) == sum(nums[i+1] to nums[n-1])

Instead of recalculating left and right sums every time (O(n²)), we can use prefix sum tricks:

1. Precompute the total sum of the array.

2. Iterate from left to right.

   • Maintain a running right sum (Rsum) which is the sum of all elements before index i.

   • The left sum after removing current element is Lsum -= nums[i].

If at any point, Rsum == Lsum - nums[i], then index i is the pivot.

Approach

1. Calculate the total sum of the array and store it in Lsum.

2. Initialize Rsum = 0.

3. Iterate from i = 0 to n - 1:

   • Subtract nums[i] from Lsum → becomes the left-side sum after i.

   • Check if Rsum == Lsum

     • If yes, return i.

   • Otherwise, add nums[i] to Rsum.

4. If no pivot found, return -1.

Java Code

class Solution {
    public int pivotIndex(int[] nums) {
        int Lsum = 0;
        for (int i : nums) {
            Lsum += i;
        }

        int Rsum = 0;
        for (int i = 0; i < nums.length; i++) {
            Lsum -= nums[i]; // now Lsum is actually the RIGHT side sum
            if (Rsum == Lsum) {
                return i;
            }
            Rsum += nums[i]; // build up Rsum (left side sum for next iteration)
        }

        return -1;
    }
}

Time and Space Complexity

Dry Run

Input:

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

Total Sum (Lsum) = 28

Initialize Rsum = 0

Conclusion

This problem is a classic example of how prefix sum optimization can reduce the time complexity from O(n²) to O(n). Instead of checking sums from scratch every time, we maintain rolling sums for left and right using a single pass.

Use this pattern when you need to compare the sum of two parts of an array repeatedly.