# LeetCode 927: Three Equal Parts

## Problem Restatement

We are given an array `arr` containing only `0`s and `1`s.

We need to split it into three non-empty parts so that all three parts represent the same binary value.

Return two indices `[i, j]` such that:

```text
arr[0] ... arr[i]          first part
arr[i + 1] ... arr[j - 1]  second part
arr[j] ... arr[n - 1]      third part
```

The split must satisfy:

```text
i + 1 < j
```

Leading zeros are allowed.

For example:

```text
[0, 1, 1]
[1, 1]
```

Both represent the same binary value.

If no valid split exists, return:

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

The official examples include `[1,0,1,0,1] -> [0,3]`, `[1,1,0,1,1] -> [-1,-1]`, and `[1,1,0,0,1] -> [0,2]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary array `arr` |
| Output | Two split indices `[i, j]` |
| Valid split | `i + 1 < j` |
| Failure case | Return `[-1, -1]` |
| Constraint | `3 <= arr.length <= 3 * 10^4` |
| Values | Each `arr[i]` is `0` or `1` |

Function shape:

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

## Examples

Example 1:

```python
arr = [1, 0, 1, 0, 1]
```

A valid split is:

```text
[1] | [0, 1] | [0, 1]
```

The three values are:

```text
1
1
1
```

The second and third parts have leading zeros, which are allowed.

So one valid answer is:

```python
[0, 3]
```

Example 2:

```python
arr = [1, 1, 0, 1, 1]
```

There are four `1`s.

If three binary values are equal and non-zero, each part must contain the same number of `1`s.

Four cannot be divided evenly into three parts.

So the answer is:

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

Example 3:

```python
arr = [1, 1, 0, 0, 1]
```

A valid split is:

```text
[1] | [1, 0, 0] | [1]
```

These represent:

```text
1
4
1
```

That split is invalid.

But the official valid answer is:

```python
[0, 2]
```

This creates:

```text
[1] | [1, 0] | [0, 1]
```

The values are:

```text
1
2
1
```

That also looks wrong if read directly without accounting for the exact LeetCode split definition.

With `[0, 2]`, the parts are:

```text
arr[0..0] = [1]
arr[1..1] = [1]
arr[2..4] = [0, 0, 1]
```

All three represent `1`.

So `[0, 2]` is valid.

## First Thought: Try Every Split

The direct approach is to try every pair of split indices.

For each pair `[i, j]`:

1. Build the first binary value from `arr[0..i]`.
2. Build the second binary value from `arr[i + 1..j - 1]`.
3. Build the third binary value from `arr[j..n - 1]`.
4. Check whether all three values are equal.

This is simple, but it has two problems.

First, there are `O(n^2)` possible split pairs.

Second, the binary values may become very large, so converting each part to an integer is unsafe or inefficient.

We need to compare the binary patterns directly.

## Key Insight

If the array contains some `1`s, then each of the three equal parts must contain the same number of `1`s.

So we first count all `1`s.

Let:

```python
ones = sum(arr)
```

There are three cases.

| Case | Result |
|---|---|
| `ones == 0` | Every part represents zero, so any valid split works |
| `ones % 3 != 0` | Impossible |
| Otherwise | Each part must contain `ones / 3` ones |

The important part is this:

Once we know each part must contain exactly `k = ones / 3` ones, we can locate the first `1` of each part.

Then the meaningful binary pattern of each part must match from those starting points to the end.

Leading zeros before those starting points do not matter.

Trailing zeros do matter.

For example:

```text
00101
101
```

These represent the same value because leading zeros are ignored.

But:

```text
1010
101
```

These do not represent the same value because the trailing zero changes the value.

## Algorithm

First count the total number of ones:

```python
ones = sum(arr)
```

If there are no ones:

```python
return [0, len(arr) - 1]
```

This works because all parts represent `0`.

If the number of ones is not divisible by `3`:

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

Otherwise:

```python
k = ones // 3
```

Each part must contain exactly `k` ones.

Now find the index of:

| Index | Meaning |
|---|---|
| `first` | First `1` of the first part |
| `second` | First `1` of the second part |
| `third` | First `1` of the third part |

These are the positions of the:

```text
1st one
(k + 1)th one
(2k + 1)th one
```

Then compare the three sequences starting from:

```python
first, second, third
```

Move all three pointers while:

```python
arr[first] == arr[second] == arr[third]
```

If the third pointer reaches the end, then all three meaningful suffixes match.

The answer is:

```python
[first - 1, second]
```

Here:

| Returned value | Meaning |
|---|---|
| `first - 1` | End of the first part |
| `second` | Start of the third part, after pointer movement |

If the third pointer does not reach the end, the patterns do not match.

Return:

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

## Walkthrough

Use:

```python
arr = [1, 0, 1, 0, 1]
```

The total number of ones is:

```python
3
```

So each part must contain:

```python
1
```

The first `1` of each part is at:

| Part | Start index |
|---|---:|
| First | `0` |
| Second | `2` |
| Third | `4` |

Compare from these positions:

```text
arr[0:] = 1 0 1 0 1
arr[2:] = 1 0 1
arr[4:] = 1
```

We compare only while the third pointer is inside the array.

Step by step:

| `first` | `second` | `third` | Values |
|---:|---:|---:|---|
| 0 | 2 | 4 | `1`, `1`, `1` |

The third pointer reaches the end after one step.

So the answer is:

```python
[first - 1, second] = [0, 3]
```

That gives:

```text
[1] | [0, 1] | [0, 1]
```

All three parts represent `1`.

## Correctness

If a valid split exists and the represented value is non-zero, each part must contain the same number of `1`s. Equal binary values have the same non-leading binary representation, so the count of `1`s in each meaningful representation must match.

Therefore, if the total number of `1`s is not divisible by `3`, no valid split exists.

If the total number of `1`s is zero, every part represents zero. Since the array length is at least `3`, returning `[0, n - 1]` creates three non-empty parts and is valid.

Now consider the non-zero case. Each part must contain exactly `k = ones / 3` ones. The first meaningful bit of each part must be the first `1` in that part, because leading zeros do not affect the binary value.

The algorithm finds exactly those three first meaningful bits:

```text
1st one
(k + 1)th one
(2k + 1)th one
```

For the three parts to represent the same value, the binary sequences starting at these three positions must be identical through the end of the third part. The third part ends at the end of the array, so it determines the required suffix length, including trailing zeros.

The synchronized comparison checks exactly this condition.

If the comparison reaches the end of the array with all matched bits equal, the three meaningful binary representations are identical. The returned indices place the cuts immediately after the matched first representation and immediately before the matched third representation, so the three parts are valid and non-empty.

If the comparison fails before the third pointer reaches the end, then at least one required bit differs. No placement of extra leading zeros can fix a difference inside the meaningful representation, so no valid split exists.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We count ones, locate starts, and compare once |
| Space | `O(1)` | We only store counters and indices |

## Implementation

```python
class Solution:
    def threeEqualParts(self, arr: list[int]) -> list[int]:
        n = len(arr)
        ones = sum(arr)

        if ones == 0:
            return [0, n - 1]

        if ones % 3 != 0:
            return [-1, -1]

        k = ones // 3

        first = second = third = -1
        count = 0

        for i, bit in enumerate(arr):
            if bit == 1:
                count += 1

                if count == 1:
                    first = i
                elif count == k + 1:
                    second = i
                elif count == 2 * k + 1:
                    third = i
                    break

        while third < n and arr[first] == arr[second] == arr[third]:
            first += 1
            second += 1
            third += 1

        if third == n:
            return [first - 1, second]

        return [-1, -1]
```

## Code Explanation

We first count how many `1`s exist:

```python
ones = sum(arr)
```

If all values are zero, any valid split works:

```python
if ones == 0:
    return [0, n - 1]
```

This creates:

```text
arr[0..0]
arr[1..n-2]
arr[n-1..n-1]
```

All three parts are non-empty because `n >= 3`.

If the number of ones cannot be split evenly:

```python
if ones % 3 != 0:
    return [-1, -1]
```

Each part must contain:

```python
k = ones // 3
```

Then we scan the array and record the first `1` of each part:

```python
if count == 1:
    first = i
elif count == k + 1:
    second = i
elif count == 2 * k + 1:
    third = i
```

After that, we compare the three suffixes together:

```python
while third < n and arr[first] == arr[second] == arr[third]:
    first += 1
    second += 1
    third += 1
```

If `third` reaches `n`, the third suffix has been fully matched.

So we return the two cuts:

```python
return [first - 1, second]
```

Otherwise, a mismatch exists:

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

## Testing

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

    assert s.threeEqualParts([1, 0, 1, 0, 1]) == [0, 3]
    assert s.threeEqualParts([1, 1, 0, 1, 1]) == [-1, -1]
    assert s.threeEqualParts([1, 1, 0, 0, 1]) == [0, 2]

    assert s.threeEqualParts([0, 0, 0, 0, 0]) == [0, 4]
    assert s.threeEqualParts([1, 0, 1, 0, 1, 0]) == [1, 4]
    assert s.threeEqualParts([1, 0, 0, 1, 0, 0, 1, 0, 0]) == [2, 6]
    assert s.threeEqualParts([1, 1, 1]) == [0, 2]
    assert s.threeEqualParts([0, 1, 0, 1, 0, 1, 0]) == [2, 5]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,0,1,0,1]` | Basic valid split |
| `[1,1,0,1,1]` | Ones not divisible by three |
| `[1,1,0,0,1]` | Leading zeros in the third part |
| All zeros | Every part represents zero |
| `[1,0,1,0,1,0]` | Requires matching trailing zero |
| Repeated `100` pattern | Clean repeated binary pattern |
| `[1,1,1]` | Smallest non-zero valid case |
| Leading zero before each part | Confirms leading zeros are allowed |