# LeetCode 724: Find Pivot Index

## Problem Restatement

We are given an integer array:

```python
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:

```python
-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:

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

## Examples

Example 1:

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

At index `3`, the value is `6`.

The left side is:

```python
[1, 7, 3]
```

Its sum is:

```python
11
```

The right side is:

```python
[5, 6]
```

Its sum is:

```python
11
```

So index `3` is a pivot index.

Output:

```python
3
```

Example 2:

```python
nums = [1, 2, 3]
```

No index has equal left and right sums.

Output:

```python
-1
```

Example 3:

```python
nums = [2, 1, -1]
```

At index `0`, the left sum is `0`.

The right side is:

```python
[1, -1]
```

Its sum is also `0`.

Output:

```python
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`:

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

If they are equal, return `i`.

```python
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:

```python
O(n^2)
```

We can do better by keeping running sums.

## Key Insight

Let:

```python
total = sum(nums)
```

At index `i`, suppose:

```python
left_sum
```

is the sum of all elements before `i`.

Then the right sum is:

```python
total - left_sum - nums[i]
```

So index `i` is a pivot if:

```python
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:

```python
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

```python
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:

```python
total = sum(nums)
```

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

```python
left_sum = 0
```

For each index, compute the right side:

```python
right_sum = total - left_sum - num
```

The current number is excluded from both sides.

If the two sides match, return this index:

```python
if left_sum == right_sum:
    return i
```

Then update `left_sum` for the next index:

```python
left_sum += num
```

If no pivot is found:

```python
return -1
```

## Alternative Form

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

Start with:

```python
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`.

```python
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:

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

Total:

```python
28
```

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:

```python
3
```

## Testing

```python
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 |