LeetCode 927: Three Equal Parts

Problem Restatement

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

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:

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:

i + 1 < j

Leading zeros are allowed.

For example:

[0, 1, 1]
[1, 1]

Both represent the same binary value.

If no valid split exists, return:

[-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

Function shape:

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

Examples

Example 1:

arr = [1, 0, 1, 0, 1]

A valid split is:

[1] | [0, 1] | [0, 1]

The three values are:

1
1
1

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

So one valid answer is:

[0, 3]

Example 2:

arr = [1, 1, 0, 1, 1]

There are four 1s.

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

Four cannot be divided evenly into three parts.

So the answer is:

[-1, -1]

Example 3:

arr = [1, 1, 0, 0, 1]

A valid split is:

[1] | [1, 0, 0] | [1]

These represent:

1
4
1

That split is invalid.

But the official valid answer is:

[0, 2]

This creates:

[1] | [1, 0] | [0, 1]

The values are:

1
2
1

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

With [0, 2], the parts are:

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 1s, then each of the three equal parts must contain the same number of 1s.

So we first count all 1s.

Let:

ones = sum(arr)

There are three cases.

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:

00101
101

These represent the same value because leading zeros are ignored.

But:

1010
101

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

Algorithm

First count the total number of ones:

ones = sum(arr)

If there are no ones:

return [0, len(arr) - 1]

This works because all parts represent 0.

If the number of ones is not divisible by 3:

return [-1, -1]

Otherwise:

k = ones // 3

Each part must contain exactly k ones.

Now find the index of:

These are the positions of the:

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

Then compare the three sequences starting from:

first, second, third

Move all three pointers while:

arr[first] == arr[second] == arr[third]

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

The answer is:

[first - 1, second]

Here:

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

Return:

[-1, -1]

Walkthrough

Use:

arr = [1, 0, 1, 0, 1]

The total number of ones is:

3

So each part must contain:

1

The first 1 of each part is at:

Compare from these positions:

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:

The third pointer reaches the end after one step.

So the answer is:

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

That gives:

[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 1s. Equal binary values have the same non-leading binary representation, so the count of 1s in each meaningful representation must match.

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

If the total number of 1s 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:

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

Implementation

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 1s exist:

ones = sum(arr)

If all values are zero, any valid split works:

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

This creates:

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:

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

Each part must contain:

k = ones // 3

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

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:

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:

return [first - 1, second]

Otherwise, a mismatch exists:

return [-1, -1]

Testing

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()