How to Solve Binary Array Partition

Binary Array Partition Introduction

The Binary Array Partition problem (also known as the Three Equal Parts problem) asks us to divide the given array containing 1's and 0's into 3 non-empty parts, such that all of these parts represent the same binary value. If it's not possible we return [-1, -1]. This problem requires careful consideration and checks for the number of ones existing in the given array and ensuring each part has an equal number of ones present keeping into account trailing zeros.

Binary Array Partition Problem

Given an array Z of 0s and 1s, divide the array into 3 non-empty parts, such that all of these parts represent the same binary value.

If it is possible, return any [i, j], such that

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

If it's not possible return [-1, -1].

Example Inputs and Outputs

Example 1

Input: Z = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

Output: Partition indices: [2, 7]

Example 2

Input: Z = [1,0,1,0,1]

Output: Partition indices: [0, 3]

Example 3

Input: Z = [1,1,0,1,1]

Output: Partition indices: [-1, -1]

Binary Array Partition Solutions

To solve this problem, we iterate through the array and count the number of ones. If there are no ones, we return [0, length-1] since the array already represents the same binary value. If the count of ones isn't divisible by 3, we return [-1, -1] since it's not possible to divide the array into three equal parts. Otherwise, we find the indices where the array can be partitioned into three parts that have the same binary value. By tracking the counts of ones, we find the first and second indices. If both indices are found, we check if the corresponding parts have the same binary value. If they do, we return the indices [first index, second index + 1]. If no suitable indices are found, we return [-1, -1].

def threeEqualParts(Z):
    ones = Z.count(1)

if ones == 0:
        return [0, len(Z) - 1]

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

ones_in_number = ones // 3
    ones = 0
    start0 = Z.index(1)
    i = start0

while ones < ones_in_number:
        if Z[i] == 1:
            ones += 1
        i += 1

l = i - start0
    start1 = Z.index(1, start0 + l)
    start2 = Z.index(1, start1 + l)

l = len(Z) - start2

if Z[start0:start0 + l] == Z[start1:start1 + l] == Z[start2:start2 + l]:
        return [start0 + l - 1, start1 + l]
    else:
        return [-1, -1]

# Driver code
Z = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
result = threeEqualParts(Z)
print("Partition indices:", result)

Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the length of the input array. We iterate through the array once to calculate the total number of ones and find the dividing indices.
• Space Complexity: O(1), as we use a constant amount of extra space.