LeetCode 724 - Find Pivot Index

LeetCode Problem 724

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to find an index in the array such that the sum of all elements strictly to the left of that index is equal to the sum of all elements strictly to the right of that index.

More formally, for an index i:

• Left sum = nums[0] + nums[1] + ... + nums[i - 1]
• Right sum = nums[i + 1] + nums[i + 2] + ... + nums[n - 1]

We must return the leftmost index where these two sums are equal. If no such index exists, we return -1.

The input is an integer array nums. The array may contain positive numbers, negative numbers, and zero. The output is a single integer representing the pivot index.

The constraints are relatively small:

• The array length is at most 10^4
• Each number is between -1000 and 1000

Even though the constraints are not huge, they are large enough that repeatedly recalculating sums for every index can become inefficient. This suggests that we should avoid nested loops if possible.

Several edge cases are important:

• A pivot index may exist at index 0, where the left sum is automatically 0
• A pivot index may exist at the last index, where the right sum is automatically 0
• Arrays with negative values can still have valid pivots
• Arrays with only one element should return 0, because both left and right sums are 0
• Multiple pivot indices may exist, but we must return the leftmost one

Understanding these details is important because naive implementations often mishandle edge boundaries or recalculate sums unnecessarily.

Approaches

Brute Force Approach

The most direct solution is to examine every index individually.

For each index i:

1. Compute the sum of all elements to the left
2. Compute the sum of all elements to the right
3. Compare the two sums
4. Return the first index where they are equal

This approach is correct because it explicitly checks the condition required by the problem definition for every possible pivot index.

However, the issue is efficiency. Calculating left and right sums separately for every index requires scanning parts of the array repeatedly. If the array has n elements, then each index may require up to O(n) work, resulting in a total complexity of O(n^2).

With n = 10^4, this still works in practice, but it is unnecessarily slow compared to what we can achieve.

Optimal Prefix Sum Approach

The key observation is that we do not need to recompute sums repeatedly.

If we already know:

• The total sum of the array
• The running sum of elements to the left

then we can compute the right sum instantly.

Suppose:

• left_sum is the sum of elements before index i
• total_sum is the sum of the entire array
• nums[i] is the current element

Then:

$$\text{right_sum} = \text{total_sum} - \text{left_sum} - \text{nums[i]}$$

So the pivot condition becomes:

$$\text{left_sum} = \text{total_sum} - \text{left_sum} - \text{nums[i]}$$

This lets us determine whether an index is a pivot in constant time.

We iterate through the array once while maintaining the running left sum. This reduces the total complexity to O(n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes left and right sums for every index
Optimal	O(n)	O(1)	Uses total sum and running prefix sum

Algorithm Walkthrough

Optimal Prefix Sum Algorithm

1. Compute the total sum of the array.

This allows us to determine the right-side sum without recalculating it repeatedly. 2. Initialize a variable left_sum = 0.

Before processing any index, there are no elements to the left, so the left sum starts at zero. 3. Iterate through the array using index i.

At each step, we treat nums[i] as the potential pivot index. 4. Compute the right sum.

Instead of scanning the array again, calculate:

$$\text{right_sum} = \text{total_sum} - \text{left_sum} - \text{nums[i]}$$

This subtracts the current element and all left-side elements from the total. 5. Compare the left and right sums.

If they are equal, then index i satisfies the pivot condition, so return i. 6. Update the left sum.

Add the current element to left_sum before moving to the next index. 7. If the loop finishes without finding a pivot, return -1.

This means no index satisfied the required condition.

Why it works

The algorithm maintains the invariant that left_sum always equals the sum of elements strictly before the current index.

At every index:

• left_sum correctly represents the left side
• total_sum - left_sum - nums[i] correctly represents the right side

Since every index is checked exactly once using accurate left and right sums, the first matching index returned is guaranteed to be the leftmost valid pivot index.

Python Solution

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0

        for i, num in enumerate(nums):
            right_sum = total_sum - left_sum - num

            if left_sum == right_sum:
                return i

            left_sum += num

        return -1

The implementation begins by calculating the total sum of the array. This is essential because it allows us to derive the right-side sum in constant time during iteration.

The variable left_sum tracks the cumulative sum of elements before the current index. Initially, it is zero because there are no elements to the left of index 0.

During each iteration:

• num is the current element
• right_sum is computed using the total sum formula
• The algorithm checks whether the left and right sums match

If they match, the current index is immediately returned because the problem requires the leftmost pivot index.

If not, the current element is added to left_sum so that the next iteration has the correct prefix sum.

If no pivot index is found after processing the entire array, the function returns -1.

Go Solution

func pivotIndex(nums []int) int {
    totalSum := 0

    for _, num := range nums {
        totalSum += num
    }

    leftSum := 0

    for i, num := range nums {
        rightSum := totalSum - leftSum - num

        if leftSum == rightSum {
            return i
        }

        leftSum += num
    }

    return -1
}

The Go implementation follows the same logic as the Python solution.

One difference is that Go does not provide a built-in sum() function for slices, so we manually compute the total sum using a loop.

The algorithm uses Go slices directly, which are lightweight references to arrays. No extra arrays or prefix sum structures are allocated, so the space complexity remains constant.

Integer overflow is not a concern here because the constraints are small. Even in the worst case:

$$10^4 \times 1000 = 10^7$$

which easily fits inside Go's int type.

Worked Examples

Example 1

Input:

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

Total sum:

28

Index	Value	Left Sum	Right Sum Calculation	Right Sum	Pivot?
0	1	0	28 - 0 - 1	27	No
1	7	1	28 - 1 - 7	20	No
2	3	8	28 - 8 - 3	17	No
3	6	11	28 - 11 - 6	11	Yes

The algorithm returns 3.

Example 2

Input:

nums = [1,2,3]

Total sum:

6

Index	Value	Left Sum	Right Sum	Pivot?
0	1	0	5	No
1	2	1	3	No
2	3	3	0	No

No pivot index exists, so the algorithm returns -1.

Example 3

Input:

nums = [2,1,-1]

Total sum:

2

Index	Value	Left Sum	Right Sum	Pivot?
0	2	0	0	Yes

The algorithm immediately returns 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed once after computing the total sum
Space	O(1)	Only a few variables are used

The algorithm performs two linear passes over the array:

1. One pass to compute the total sum
2. One pass to locate the pivot index

Since both passes are linear, the total time complexity is O(n).

No additional arrays, hash maps, or auxiliary data structures are created. The algorithm only stores a few integer variables, so the space complexity is constant.

Test Cases

sol = Solution()

assert sol.pivotIndex([1, 7, 3, 6, 5, 6]) == 3  # standard example with middle pivot
assert sol.pivotIndex([1, 2, 3]) == -1  # no pivot exists
assert sol.pivotIndex([2, 1, -1]) == 0  # pivot at left edge

assert sol.pivotIndex([1]) == 0  # single element array
assert sol.pivotIndex([0, 0, 0]) == 0  # multiple pivots, return leftmost
assert sol.pivotIndex([-1, -1, -1, -1, -1, 0]) == 2  # negative numbers
assert sol.pivotIndex([0]) == 0  # single zero element
assert sol.pivotIndex([1, -1, 0]) == 2  # pivot at right edge
assert sol.pivotIndex([2, 3, -1, 8, 4]) == 3  # mixed positive and negative
assert sol.pivotIndex([10, -10, 10, -10, 10, -10]) == -1  # alternating values, no pivot

Test Summary

Test	Why
[1,7,3,6,5,6]	Standard example with pivot in the middle
[1,2,3]	Confirms correct handling when no pivot exists
[2,1,-1]	Validates pivot at index 0
[1]	Smallest possible input
[0,0,0]	Multiple valid pivots, must return leftmost
[-1,-1,-1,-1,-1,0]	Handles negative numbers correctly
[0]	Single zero element
[1,-1,0]	Pivot at the last index
[2,3,-1,8,4]	Mixed positive and negative values
[10,-10,10,-10,10,-10]	Alternating values with no valid pivot

Edge Cases

Pivot at the Beginning of the Array

An index at the far left has no elements before it, so the left sum should be treated as zero.

This can easily cause bugs if an implementation incorrectly tries to access elements before index 0 or forgets that an empty sum equals zero.

The implementation handles this naturally because left_sum is initialized to 0 before iteration begins.

Pivot at the End of the Array

Similarly, the last index has no elements after it, so the right sum should be zero.

Some incorrect implementations accidentally include the current element in the right-side calculation or mishandle array boundaries.

This solution correctly computes:

$$\text{right_sum} = \text{total_sum} - \text{left_sum} - \text{nums[i]}$$

At the last index, this expression becomes zero automatically.

Arrays with Negative Numbers

Negative numbers are important because the sums are not guaranteed to increase monotonically.

A naive approach based on assumptions about increasing sums could fail. For example:

[-1, -1, -1, -1, -1, 0]

still contains a valid pivot index.

The prefix sum approach works correctly regardless of whether values are positive, negative, or zero because it relies only on exact arithmetic equality.

Multiple Valid Pivot Indices

An array may contain more than one valid pivot index. The problem specifically requires the leftmost one.

For example:

[0, 0, 0]

Every index is technically a pivot.

The implementation guarantees the correct result because it scans from left to right and returns immediately when it finds the first valid pivot.