How to Solve Binary Array Partition

Written By
Adam Bhula

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]
        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.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.