LeetCode 724: Find Pivot Index

Problem Restatement

We are given an integer array:

nums

We need to find the pivot index.

An index is a pivot index if the sum of all numbers strictly to its left equals the sum of all numbers strictly to its right.

If the pivot is at the left edge, the left sum is 0.

If the pivot is at the right edge, the right sum is 0.

Return the leftmost pivot index.

If no pivot index exists, return:

-1

Input and Output

Item	Meaning
Input	Integer array `nums`
Output	Leftmost pivot index, or `-1`
Left sum	Sum of elements before the index
Right sum	Sum of elements after the index
Edge behavior	Missing side has sum `0`

The function shape is:

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        ...

Examples

Example 1:

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

At index 3, the value is 6.

The left side is:

[1, 7, 3]

Its sum is:

The right side is:

[5, 6]

Its sum is:

So index 3 is a pivot index.

Output:

Example 2:

nums = [1, 2, 3]

No index has equal left and right sums.

Output:

-1

Example 3:

nums = [2, 1, -1]

At index 0, the left sum is 0.

The right side is:

[1, -1]

Its sum is also 0.

Output:

First Thought: Check Each Index Directly

A direct solution is to compute the left sum and right sum for every index.

For each index i:

left_sum = sum(nums[:i])
right_sum = sum(nums[i + 1:])

If they are equal, return i.

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        for i in range(len(nums)):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i + 1:])

            if left_sum == right_sum:
                return i

        return -1

This is easy to understand, but it repeats the same summations many times.

Problem With Brute Force

For each index, summing the left and right parts can take O(n) time.

There are n indices.

So the total runtime is:

O(n^2)

We can do better by keeping running sums.

Key Insight

Let:

total = sum(nums)

At index i, suppose:

left_sum

is the sum of all elements before i.

Then the right sum is:

total - left_sum - nums[i]

So index i is a pivot if:

left_sum == total - left_sum - nums[i]

We can scan from left to right while maintaining left_sum.

Because we scan in order, the first valid index we find is automatically the leftmost pivot index.

Algorithm

Compute total = sum(nums).
Set left_sum = 0.
For each index i and value num:
- Compute the right sum as total - left_sum - num.
- If left_sum == right_sum, return i.
- Add num to left_sum.
Return -1.

Correctness

At the start of each loop iteration for index i, left_sum is exactly the sum of all elements strictly before i.

The total sum of the array is total. If we subtract the left side and the current element from total, the remaining value is exactly the sum of all elements strictly after i.

Therefore the condition:

left_sum == total - left_sum - nums[i]

is true exactly when index i is a pivot index.

The algorithm checks indices from left to right. Thus the first pivot index it returns is the leftmost pivot index.

If the loop finishes without returning, no index satisfies the pivot condition, so returning -1 is correct.

Complexity

Let n be the length of nums.

Metric	Value	Why
Time	`O(n)`	One pass to compute the total and one pass to scan indices
Space	`O(1)`	Only two sums are stored

Implementation

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

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

            if left_sum == right_sum:
                return i

            left_sum += num

        return -1

Code Explanation

First compute the full array sum:

total = sum(nums)

The left sum starts at 0 because index 0 has no elements to its left:

left_sum = 0

For each index, compute the right side:

right_sum = total - left_sum - num

The current number is excluded from both sides.

If the two sides match, return this index:

if left_sum == right_sum:
    return i

Then update left_sum for the next index:

left_sum += num

If no pivot is found:

return -1

Alternative Form

Instead of computing right_sum directly, we can keep a running right sum.

Start with:

right_sum = sum(nums)
left_sum = 0

For each number:

Subtract the current number from right_sum.
Compare left_sum and right_sum.
Add the current number to left_sum.

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

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

            if left_sum == right_sum:
                return i

            left_sum += num

        return -1

This version makes the “strictly left” and “strictly right” idea explicit.

Example Walkthrough

Use:

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

Total:

Scan:

Index	Value	Left Sum	Right Sum	Pivot
`0`	`1`	`0`	`27`	No
`1`	`7`	`1`	`20`	No
`2`	`3`	`8`	`17`	No
`3`	`6`	`11`	`11`	Yes

Return:

Testing

def test_pivot_index():
    s = Solution()

    assert s.pivotIndex([1, 7, 3, 6, 5, 6]) == 3
    assert s.pivotIndex([1, 2, 3]) == -1
    assert s.pivotIndex([2, 1, -1]) == 0
    assert s.pivotIndex([1]) == 0
    assert s.pivotIndex([-1, -1, 0, 1, 1, 0]) == 5
    assert s.pivotIndex([0, 0, 0]) == 0

    print("all tests passed")

test_pivot_index()

Test coverage:

Test	Why
Standard example	Confirms normal pivot detection
No pivot	Confirms `-1` result
Pivot at first index	Confirms left edge sum is `0`
Single element	Confirms both sides are empty
Negative numbers	Confirms sums work with signs
Multiple pivots	Confirms leftmost pivot is returned