Binary Array Partition Introduction
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
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
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)1def threeEqualParts(Z):
2 ones = Z.count(1)
3
4 if ones == 0:
5 return [0, len(Z) - 1]
6
7 if ones % 3 != 0:
8 return [-1, -1]
9
10 ones_in_number = ones // 3
11 ones = 0
12 start0 = Z.index(1)
13 i = start0
14
15 while ones < ones_in_number:
16 if Z[i] == 1:
17 ones += 1
18 i += 1
19
20 l = i - start0
21 start1 = Z.index(1, start0 + l)
22 start2 = Z.index(1, start1 + l)
23
24 l = len(Z) - start2
25
26 if Z[start0:start0 + l] == Z[start1:start1 + l] == Z[start2:start2 + l]:
27 return [start0 + l - 1, start1 + l]
28 else:
29 return [-1, -1]
30
31# Driver code
32Z = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
33result = threeEqualParts(Z)
34print("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.
Watch These Related Mock Interviews
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.
