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

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:

11

The right side is:

[5, 6]

Its sum is:

11

So index 3 is a pivot index.

Output:

3

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:

0

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

1. Compute total = sum(nums).
2. Set left_sum = 0.
3. 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.
4. 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.

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:

1. Subtract the current number from right_sum.
2. Compare left_sum and right_sum.
3. 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:

28

Scan:

Return:

3

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: