# LeetCode 1013: Partition Array Into Three Parts With Equal Sum

## Problem Restatement

We are given an integer array `arr`.

We need to return `true` if we can partition the array into three non-empty contiguous parts that each have the same sum.

Formally, find indices `i` and `j` such that:

```python
0 < i < j < len(arr)
sum(arr[:i]) == sum(arr[i:j]) == sum(arr[j:])
```

If such indices exist, return `true`. Otherwise return `false`.

The official constraints state that `3 <= arr.length <= 5 * 10^4` and `-10^4 <= arr[i] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr` |
| Output | `true` if a valid three-way partition exists |
| Partition | Three non-empty contiguous subarrays with equal sums |

Function shape:

```python
def canThreePartsEqualSum(arr: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
```

Total sum is `9`. Each part should sum to `3`.

Partition: `[0,2,1]`, `[-6,6,-7,9,1]`, `[2,0,1]` → sums `3, 3, 3`. ✓

Answer:

```python
True
```

Example 2:

```python
arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]
```

Total sum is `21`. Each part should sum to `7`.

But no such partition exists.

Answer:

```python
False
```

## Key Insight

The total sum must be divisible by `3`. Each part must equal `total / 3`.

Scan the array while accumulating a running sum. Each time the running sum hits `target`, we have found one part boundary. After finding two boundaries, check if a third non-empty part remains.

## Algorithm

1. Compute `total = sum(arr)`. If `total % 3 != 0`, return `False`.
2. Set `target = total // 3`.
3. Scan the array, tracking the running sum and the count of parts found.
4. When the running sum equals `target * parts_found`, increment the parts count.
5. If we found 3 parts and there are elements remaining, return `True` (but ensure the third part is non-empty by requiring the boundary to be before the last element).

Simpler: scan for the first boundary, then the second boundary, then check elements remain.

## Correctness

If total is not divisible by 3, no equal-sum partition exists.

If it is, we greedily find the earliest position where the prefix sum equals `target`. Then from there, find the next position where the cumulative sum equals `2 * target`. If this second boundary is before the last element, the third part exists and is non-empty.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Single pass |
| Space | `O(1)` | Constant extra space |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False

        target = total // 3
        parts = 0
        running = 0

        for i in range(len(arr)):
            running += arr[i]
            if running == target * (parts + 1):
                parts += 1
            if parts == 2 and i < len(arr) - 1:
                return True

        return False
```

## Code Explanation

Check divisibility:

```python
if total % 3 != 0:
    return False
```

Scan while counting part boundaries:

```python
running += arr[i]
if running == target * (parts + 1):
    parts += 1
```

After finding the second boundary, check that we are not at the last element (ensuring the third part is non-empty):

```python
if parts == 2 and i < len(arr) - 1:
    return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canThreePartsEqualSum([0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]) == True
    assert s.canThreePartsEqualSum([0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]) == False
    assert s.canThreePartsEqualSum([3, 3, 6, 5, -2, 2, 5, 1, -9, 4]) == True
    assert s.canThreePartsEqualSum([1, 1, 1]) == True
    assert s.canThreePartsEqualSum([0, 0, 0, 0]) == True

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[0,2,1,-6,6,-7,9,1,2,0,1]` | `True` | Valid three-way partition |
| `[0,2,1,-6,6,7,9,-1,2,0,1]` | `False` | No valid partition |
| `[3,3,6,5,-2,2,5,1,-9,4]` | `True` | Another valid partition |
| `[1,1,1]` | `True` | Each part is one element |
| `[0,0,0,0]` | `True` | Multiple zero partitions |