Code Implementation

class Solution:
    def threeEqualParts(self, arr):
        S = sum(arr)
        if S % 3 != 0:
            return [-1, -1]
        if S == 0:
            return [0, len(arr) - 1]
        ones_per_part = S // 3
        first = second = third = -1
        ones_count = 0
        n = len(arr)
        for i, bit in enumerate(arr):
            if bit == 1:
                ones_count += 1
                if ones_count == 1:
                    first = i
                elif ones_count == ones_per_part + 1:
                    second = i
                elif ones_count == 2 * ones_per_part + 1:
                    third = i
        length = n - third
        if arr[first:first + length] == arr[second:second + length] == arr[third:third + length]:
            return [first + length - 1, second + length]
        return [-1, -1]
      

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int S = 0;
        for (int bit : arr) S += bit;
        if (S % 3 != 0) return {-1, -1};
        if (S == 0) return {0, (int)arr.size() - 1};
        int ones_per_part = S / 3;
        int first = -1, second = -1, third = -1, ones_count = 0, n = arr.size();
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 1) {
                ones_count++;
                if (ones_count == 1) first = i;
                else if (ones_count == ones_per_part + 1) second = i;
                else if (ones_count == 2 * ones_per_part + 1) third = i;
            }
        }
        int len = n - third;
        for (int i = 0; i < len; ++i) {
            if (arr[first + i] != arr[second + i] || arr[first + i] != arr[third + i])
                return {-1, -1};
        }
        return {first + len - 1, second + len};
    }
};
      

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int S = 0;
        for (int bit : arr) S += bit;
        if (S % 3 != 0) return new int[]{-1, -1};
        if (S == 0) return new int[]{0, arr.length - 1};
        int onesPerPart = S / 3;
        int first = -1, second = -1, third = -1, onesCount = 0, n = arr.length;
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 1) {
                onesCount++;
                if (onesCount == 1) first = i;
                else if (onesCount == onesPerPart + 1) second = i;
                else if (onesCount == 2 * onesPerPart + 1) third = i;
            }
        }
        int len = n - third;
        for (int i = 0; i < len; ++i) {
            if (arr[first + i] != arr[second + i] || arr[first + i] != arr[third + i])
                return new int[]{-1, -1};
        }
        return new int[]{first + len - 1, second + len};
    }
}
      

var threeEqualParts = function(arr) {
    let S = arr.reduce((a, b) => a + b, 0);
    if (S % 3 !== 0) return [-1, -1];
    if (S === 0) return [0, arr.length - 1];
    let onesPerPart = S / 3;
    let first = -1, second = -1, third = -1, onesCount = 0, n = arr.length;
    for (let i = 0; i < n; ++i) {
        if (arr[i] === 1) {
            onesCount++;
            if (onesCount === 1) first = i;
            else if (onesCount === onesPerPart + 1) second = i;
            else if (onesCount === 2 * onesPerPart + 1) third = i;
        }
    }
    let len = n - third;
    for (let i = 0; i < len; ++i) {
        if (arr[first + i] !== arr[second + i] || arr[first + i] !== arr[third + i])
            return [-1, -1];
    }
    return [first + len - 1, second + len];
};
      

Problem Description

You are given a binary array arr (containing only 0s and 1s). Your task is to split this array into three non-empty parts such that each part represents the same binary value (ignoring leading zeros). You must return the indices [i, j] such that:

• The first part is arr[0..i]
• The second part is arr[i+1..j]
• The third part is arr[j+1..]
• All three parts are non-empty
• Each part, interpreted as a binary number (ignoring leading zeros), is equal
• If there are multiple answers, return any one. If no answer exists, return [-1, -1].

The key constraints are:

• You cannot reuse elements between parts.
• Each part must be non-empty.
• There is at most one valid solution, but if there are multiple, any is acceptable.

Thought Process

At first glance, one might think to try all possible ways to split the array into three parts and check if all three represent the same binary number. However, this would be extremely inefficient, especially for large arrays.

Instead, let's focus on what must be true for a solution to exist. Since we want three parts with the same value, the number of 1s in each part must be equal. If the total number of 1s is not divisible by 3, it's impossible. If the array contains only zeros, any split works, because all parts are equal to zero.

We also need to pay attention to leading zeros and the actual positions of the 1s. The key insight is to find the starting index of each part and check if the sections that start at those indices are identical.

Solution Approach

• Count the total number of 1s: Let S be the total number of 1s in arr. If S % 3 != 0, return [-1, -1] because it's impossible to split equally.
• Handle all-zero case: If S == 0, any split works. Return [0, arr.length - 1] as a valid answer.
• Find the starting positions: Let each part have ones_per_part = S // 3 ones. Walk through arr and record the indices where the 1st, (ones_per_part+1)th, and (2*ones_per_part+1)th 1s occur. These will be the starting indices of the three parts.
• Compare the segments: The three parts must be identical from their respective starting points to the end of the array (since leading zeros are ignored). The length of the segment to compare is n - third, where third is the starting index of the third part.
• Check for equality: If the three segments are equal, return the end indices of the first and second parts; otherwise, return [-1, -1].

This approach works because the only way for the three parts to be equal is for their meaningful (trailing) bits to be exactly the same, and any leading zeros do not affect the value.

Example Walkthrough

Consider the input arr = [1,0,1,0,1].

• Total number of 1s: 3. Each part must have 1 one.
• Find the positions of the 1st, 2nd, and 3rd ones: indices 0, 2, and 4.
• Length to compare: n - third = 5 - 4 = 1. So, compare arr[0..0], arr[2..2], arr[4..4].
• Each segment is [1]. They are all equal.
• The indices to split: first part ends at 0, second part ends at 2 (so, [0, 3] is the answer).

In this way, you can trace the process for any input, always focusing on the positions of the 1s and the length of the segment to compare.

Time and Space Complexity

• Brute-force approach: Trying all possible splits would be O(n²) or worse, since you'd check every possible pair of split points and compare the resulting parts.
• Optimized approach: The presented solution scans the array a constant number of times (to count 1s, find indices, and compare segments), so its time complexity is O(n).
• Space complexity: Only a few variables are used, so the space complexity is O(1).

The efficiency comes from leveraging the structure of the problem and avoiding unnecessary work.

Summary

The "Three Equal Parts" problem is elegantly solved by focusing on the distribution of 1s in the array. By ensuring each part contains the same number of 1s and comparing the meaningful segments, we avoid brute-force and achieve an efficient solution. The key insight is that only the positions and groupings of 1s matter, and leading zeros can be ignored. This strategy leads to a clean and optimal linear-time algorithm.