#927 Three Equal Parts - Solution

You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i + 1 < j, such that:

arr[0], arr[1], ..., arr[i] is the first part,
arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and
arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part.
All three parts have equal binary values.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: arr = [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: arr = [1,1,0,1,1]
Output: [-1,-1]

Example 3:

Input: arr = [1,1,0,0,1]
Output: [0,2]

Constraints:

3 <= arr.length <= 3 * 10⁴
arr[i] is 0 or 1

In #927 Three Equal Parts, the goal is to split a binary array into three non-empty parts such that each part represents the same binary value. A key observation is that if the total number of 1s in the array is not divisible by three, forming three equal binary values is impossible.

The efficient strategy counts the total number of 1s and determines the starting index of the first 1 in each of the three segments. Once these anchors are identified, the algorithm compares the segments simultaneously to ensure they form identical binary patterns. Special attention must be given to trailing zeros, as they affect valid partition boundaries. If all three segments match until the end of the array, valid split indices can be derived.

This approach processes the array in a single pass with constant extra memory, making it highly efficient. The solution runs in O(n) time with O(1) additional space.

Approach	Time Complexity	Space Complexity
Counting 1s and matching three segments	O(n)	O(1)

Solutions (4)

Iterative Matching with Counting

In this approach, we iterate through the array while counting the number of 1s. We need to ensure that the number of 1s is divisible by 3, otherwise it's impossible to split the array with equal parts. If it's divisible, each part must contain the same number of 1s.

After determining the number of 1s each part should have, we traverse the array again to find possible split points, and validate if the parts have equal binary values by comparing.

Time Complexity: O(n), where n is the length of the array, as we are traversing the array a few times.

Space Complexity: O(1), as no additional space is used except for variables.

Python JavaScript Java

1public int[] threeEqualParts(int[] arr) {
2    int numOfOnes = 0;
3    for (int num : arr) numOfOnes += num;
4    if (numOfOnes % 3 != 0) return new int[]{-1, -1};
5    if (numOfOnes == 0) return new int[]{0, arr.length - 1};
6
7    int target = numOfOnes / 3;
8    int first = -1, second = -1, third = -1, oneCount = 0;
9    for (int i = 0; i < arr.length; i++) {
10        if (arr[i] == 1) {
11            if (oneCount == 0) first = i;
12            if (oneCount == target) second = i;
13            if (oneCount == 2 * target) third = i;
14            oneCount++;
15        }
16    }
17
18    int length = arr.length - third;
19    if (isValid(arr, first, second, third, length)) {
20        return new int[]{first + length - 1, second + length};
21    }
22    return new int[]{-1, -1};
23}
24
25private boolean isValid(int[] arr, int first, int second, int third, int length) {
26    for (int i = 0; i < length; i++) {
27        if (arr[first + i] != arr[second + i] || arr[second + i] != arr[third + i]) return false;
28    }
29    return true;
30}

Explanation

This Java solution calculates the number of 1s and ensures they can be divided into three equal parts. Then it finds the starting indices for the segments to contain equal 1s. A helper method checks if the segments starting at these indices yield the same binary value.

Hashing to Check Parts

This approach uses hashing to store the indices of 1s as keys and their count as values for faster retrieval and comparison.

Once we determine the number of 1s each part should have (after verifying it's divisible by 3), we use these indices to segment the array into candidate parts. Hashing ensures we efficiently compare these binary segments.

Time Complexity: O(n)

Space Complexity: O(1)

1public int[] ThreeEqualParts(int[] arr)
2{
3    int numOfOnes = arr.Count(x => x == 1);
4    if (numOfOnes % 3 != 0) return new int[] { -1, -1 };
5    if (numOfOnes == 0) return new int[] { 0, arr.Length - 1 };
6
7    int target = numOfOnes / 3;
    int first = -1, second = -1, third = -1, count = 0;

    for (int i = 0; i < arr.Length; ++i)
    {
        if (arr[i] == 1)
        {
            if (count == 0) first = i;
            if (count == target) second = i;
            if (count == 2 * target) third = i;
            count++;
        }
    }

    int partLen = arr.Length - third;
    if (ArePartsEqual(arr, first, second, third, partLen))
    {
        return new int[] { first + partLen - 1, second + partLen };
    }
    return new int[] { -1, -1 };
}

private bool ArePartsEqual(int[] arr, int first, int second, int third, int partLen)
{
    for (int i = 0; i < partLen; ++i)
    {
        if (arr[first + i] != arr[second + i] || arr[second + i] != arr[third + i])
        {
            return false;
        }
    }
    return true;
}