927. Three Equal Parts
Problem Description
In this combinatorial problem, we are given an array arr
consisting only of 0s and 1s. The goal is to divide this array into three contiguous, non-empty parts, such that each part represents an identical binary value when converted to a decimal number. If such a tripartition is possible, we return the indices [i, j]
which separate the three parts:
- The first part spans from
arr[0]
toarr[i]
, - The second part spans from
arr[i+1]
toarr[j-1]
, and - The third part spans from
arr[j]
toarr[arr.length - 1]
.
It's important to note that all three parts must represent the same binary value. The representation includes leading zeros, which means that sequences like [0, 1, 1]
and [1, 1]
are considered equivalent. If division into such three parts is not feasible, we must return [-1, -1]
.
Intuition
The approach to solving this problem involves understanding that if we can divide the array into three partitions with equal binary value, the number of 1's in each part must be equal, because binary numbers are represented by the sequence of 1's they contain, and leading zeros do not change their value.
Following this logic:
-
We first count the total number of 1's in the array. If this number is not divisible by 3, we cannot possibly divide the array into three parts with an equal number of 1's, and we return
[-1, -1]
. -
If the total number of 1's is zero, that means the array contains only 0's, and we can return any valid partition such as
[0, n - 1]
wheren
is the length of the array. -
In other cases, we settle for an iterative approach to find the actual partition:
- We find the index of the 1st
1
in each of the three parts. These will be the start points for comparing the parts. - Since
cnt
is the total count of 1's in each partition, we find:- The 1st
1
atfind(1)
- The 1st
1
in the second part atfind(cnt + 1)
- The 1st
1
in the third part atfind(cnt * 2 + 1)
- The 1st
- We find the index of the 1st
-
Once we have these starting points, we compare each subsequent digit of the three parts to ensure they match. If they do, we move all indices to the next position.
-
We continue this until we've compared all digits or find a mismatch. If we reach the end of the array and all digits have matched, we return
[i - 1, j]
, which represents the required partition. If there's a mismatch, the arrangement is not possible, and we return[-1, -1]
.
This approach utilizes two key ideas: equal number of 1's in each partition and the rule that leading zeroes do not alter the binary number's value for the solution.
Learn more about Math patterns.
Solution Approach
The provided Python solution begins with a helper function find(x)
used to locate the index of the x
-th 1
within the array. This function iterates over the arr
and keeps a count s
of the number of 1's seen so far. When s
equals x
, the function returns the current index, effectively marking the boundary of a part.
Here is the step-by-step breakdown of the algorithm:
-
Counting 1's and Pre-validation: The total number of 1's in the array is counted using
sum(arr)
. The algorithm then checks if this sum is divisible by 3. If not, the parts cannot have equal binary values, and the function returns[-1, -1]
. If there are no 1's, the array can be split anywhere to create equal parts of zeros, and thus[0, n - 1]
is returned. -
Finding the Initial Indices for Comparison: The algorithm finds the indices
i
,j
, andk
which point to the first 1 in each of the three parts we want to compare. This is accomplished by callingfind(1)
for the first1
,find(cnt + 1)
for the first1
in the second part, andfind(cnt * 2 + 1)
for the first1
in the third part, wherecnt
is the count of1
s in any part. -
Comparing the Three Parts: By initializing
i
,j
, andk
to the start of each part, the algorithm enters awhile
loop which continues until the indexk
reaches the end of the array. Inside the loop, it checks whether the current bits atarr[i]
,arr[j]
, andarr[k]
are equal. If they are equal, it means the parts are still matching, and it incrementsi
,j
, andk
one position forward to compare the next set of bits. -
Determining the Correct Split Point: The loop terminates when the end of the array is reached (
k == n
) or a mismatch is found. If the end of the array is reached without encountering a mismatch, it means the three parts match and the function returns the split points[i - 1, j]
. If the while loop exits due to a mismatch, it means equal partitioning is not possible, and thus[-1, -1]
is returned.
This solution employs a single pass to count 1
s and a single traversal for comparison. It uses no additional data structures and solely relies on array indexing. The solution pattern hinges on the continual comparison of triplet indices, moving forward collectively to maintain the synchrony and alignment of the three parts. This is an example of a two-pointer technique, where multiple pointers are used to iterate over the data structure, updating their positions based on certain conditions.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example arr = [1, 0, 1, 0, 1, 0]
to illustrate the solution approach.
-
Counting 1's and Pre-validation: We start by counting the number of
1
s in the array. There are a total of 31
s, which is divisible by 3. That means we can potentially dividearr
into three parts with an equal number of1
s in each part. -
Finding the Initial Indices for Comparison: We want to find the indices for the first
1
in all three parts.- The first
1
appears at index0
. We seti
to this value. - The second
1
is part of the second segment. Since there's one1
in the first segment, we search for the(1+1)
-th1
, which is at index2
. We setj
to point to the following position, which is3
. - The third
1
is part of the third segment. We search for the(2*1+1)
-th1
, which is at index4
. We setk
to point to this index.
- The first
By the end of this step, we have i = 0
, j = 3
, and k = 4
.
-
Comparing the Three Parts: Now we begin comparing the elements pointed by
i
,j
, andk
.- At our starting indices the values at
arr[i]
,arr[j]
, andarr[k]
are1
,0
, and1
, respectively. They are not all equal, so we move thei
index forward to try to match the values in the next iteration. - After incrementing, we have
i = 1
,j = 3
, andk = 4
. The values are0
,0
, and1
. The values atj
andk
are different, so we incrementj
to try to match in the next iteration. - With
i = 1
,j = 4
, andk = 4
, now we havearr[i]
,arr[j]
, andarr[k]
all0
. We increment all indices to find the next value. - With
i = 2
,j = 5
, andk = 5
, the values are1
,0
, and0
. Now, sincearr[j]
andarr[k]
are equal but different fromarr[i]
, we incrementi
untilarr[i]
matches. - This process continues until
i
,j
, andk
move past the end ofarr
or until we find a mismatch that we can't resolve by incrementing the pointers.
- At our starting indices the values at
-
Determining the Correct Split Point: In this example, we see that
i
can move to2
, makingarr[i]
a1
, which gives usarr[i]
,arr[j]
, andarr[k]
values of1
,0
, and0
. There seems to be a mismatch, however, we note that the parts don't need to be equal only the binary value they represent need to be equal. Since leading zeros can be ignored in the binary value representation, in our current positions (i = 2
,j = 5
,k = 5
), the partition yieldsarr[0]
toarr[i]
as[1,0]
,arr[i+1]
toarr[j-1]
as[1]
and the last partarr[j]
toarr[arr.length - 1]
as an empty array which after considering leading zeros could also be[1]
. The binary value all three parts correspond to is 1 in decimal, so the array can indeed be partitioned. The correct split points are[i, j]
, and after decrementingi
by one to exclude it from the second part, we havearr[0..1]
,arr[2..4]
, andarr[5..5]
. Thus, we return[1, 5]
.
In this case, the binary value for all three parts is 1
, which is equal for each partition. Hence, we can return [1, 5]
which are the required indices to divide the array into three parts of equal binary value.
Solution Implementation
1class Solution:
2 def threeEqualParts(self, arr):
3 # Helper function to find the index of the partition
4 def find_partition(target_sum):
5 running_sum = 0
6 for index, value in enumerate(arr):
7 running_sum += value
8 if running_sum == target_sum:
9 return index
10 return -1
11
12 n = len(arr) # Length of the array
13 total_ones, remainder = divmod(sum(arr), 3) # Total ones and remainder when divided by 3
14
15 # If the number of 1's is not divisible by 3, return [-1, -1]
16 if remainder != 0:
17 return [-1, -1]
18
19 # If there are no ones, any index can be the partition, choose 0 and n-1
20 if total_ones == 0:
21 return [0, n - 1]
22
23 # Find the start index of each part
24 part1_index = find_partition(1)
25 part2_index = find_partition(total_ones + 1)
26 part3_index = find_partition(2 * total_ones + 1)
27
28 # Match bits of the three parts
29 while part3_index < n and arr[part1_index] == arr[part2_index] == arr[part3_index]:
30 part1_index += 1
31 part2_index += 1
32 part3_index += 1
33
34 # If part3_index reached the end, we found a valid partition
35 if part3_index == n:
36 return [part1_index - 1, part2_index]
37
38 # Otherwise, no valid partition was found
39 return [-1, -1]
40
1class Solution {
2 private int[] binaryArray; // Renamed array for clarity
3
4 public int[] threeEqualParts(int[] arr) {
5 binaryArray = arr;
6 int countOfOnes = 0; // More descriptive naming
7 int arrayLength = arr.length;
8
9 // Count the number of 1s in the array
10 for (int value : arr) {
11 countOfOnes += value;
12 }
13
14 // If count of 1s is not divisible by three, solution is impossible
15 if (countOfOnes % 3 != 0) {
16 return new int[] {-1, -1};
17 }
18
19 // If array has no 1s, any split is valid (all zeros)
20 if (countOfOnes == 0) {
21 return new int[] {0, arrayLength - 1};
22 }
23
24 // Each part must contain an equal number of 1s
25 countOfOnes /= 3;
26
27 // Find the start index of three subarrays with an equal number of 1s
28 int first = findNthOne(1),
29 second = findNthOne(countOfOnes + 1),
30 third = findNthOne(2 * countOfOnes + 1);
31
32 // Check if all three parts are equal
33 while (third < arrayLength &&
34 binaryArray[first] == binaryArray[second] &&
35 binaryArray[second] == binaryArray[third]) {
36 ++first;
37 ++second;
38 ++third;
39 }
40
41 // If end of the array is reached, return valid split positions, else return [-1, -1]
42 return third == arrayLength ?
43 new int[] {first - 1, second} :
44 new int[] {-1, -1};
45 }
46
47 // Helper method to find the start index of the n-th one in the binary array
48 private int findNthOne(int nthOne) {
49 int sum = 0;
50 for (int i = 0; i < binaryArray.length; ++i) {
51 sum += binaryArray[i];
52 if (sum == nthOne) {
53 return i;
54 }
55 }
56 return -1; // Return -1 if the nth one is not found
57 }
58}
59
1#include <vector>
2#include <numeric> // For std::accumulate
3
4class Solution {
5public:
6 vector<int> threeEqualParts(vector<int>& arr) {
7 int totalOnes = accumulate(arr.begin(), arr.end(), 0); // Count total number of 1's in the array
8
9 // If total number of 1's is not divisible by 3, we can't partition the array into three parts with equal no of 1's.
10 if (totalOnes % 3 != 0) return {-1, -1};
11
12 // If there are no 1's, any partition is valid (since all are zeros)
13 if (totalOnes == 0) return {0, static_cast<int>(arr.size()) - 1};
14
15 int onesPerPart = totalOnes / 3; // Number of 1's each part must have
16
17 // Lambda function to find the first index where the cumulative number of 1's equals 'targetOnes'
18 auto findIndexWithCumulativeOnes = [&](int targetOnes) {
19 int cumulativeOnes = 0;
20 for (int i = 0; i < arr.size(); ++i) {
21 cumulativeOnes += arr[i];
22 if (cumulativeOnes == targetOnes) return i;
23 }
24 return -1; // Return -1 if target is not found (should not happen if input is valid)
25 };
26
27 // Find the ending indexes of parts with 1/3, 2/3, and all of the 1's
28 int firstPartEnd = findIndexWithCumulativeOnes(1);
29 int secondPartEnd = findIndexWithCumulativeOnes(onesPerPart + 1);
30 int thirdPartEnd = findIndexWithCumulativeOnes(2 * onesPerPart + 1);
31
32 // Ensure each corresponding position in the three parts contains the same value
33 while (thirdPartEnd < arr.size() && arr[firstPartEnd] == arr[secondPartEnd] && arr[secondPartEnd] == arr[thirdPartEnd]) {
34 ++firstPartEnd;
35 ++secondPartEnd;
36 ++thirdPartEnd;
37 }
38
39 // If end of array is reached, return valid partition points,
40 // Otherwise, return {-1, -1} since parts are not equal.
41 return thirdPartEnd == arr.size() ? vector<int>{firstPartEnd - 1, secondPartEnd} : vector<int>{-1, -1};
42 }
43};
44
1/**
2 * Function to find the split points for the array such that all parts are equal.
3 * @param arr An array of 0s and 1s.
4 * @returns An array with two indices that represent the split points, if valid, else returns [-1, -1].
5 */
6function threeEqualParts(arr: number[]): [number, number] {
7 // A helper function to find the end index of the subarray that makes the sum x.
8 const find = (targetSum: number, startIndex: number): number => {
9 let sum = 0;
10 for (let i = startIndex; i < n; ++i) {
11 sum += arr[i];
12 if (sum === targetSum) {
13 return i;
14 }
15 }
16 return -1;
17 };
18
19 const n: number = arr.length;
20 let totalOnes: number = 0; // Count the total number of 1s in the array.
21
22 // Counting the number of 1's in the array.
23 for (const value of arr) {
24 totalOnes += value;
25 }
26
27 // If total number of 1's is not divisible by 3, then it's not possible to split the array into three equal parts.
28 if (totalOnes % 3) {
29 return [-1, -1];
30 }
31
32 // If there are no 1's, we can split anywhere.
33 if (totalOnes === 0) {
34 return [0, n - 1];
35 }
36
37 // The number of 1s in each part.
38 const onesPerPart: number = Math.floor(totalOnes / 3);
39
40 // Find the first index in each part of the array.
41 let firstIndexEnd = find(1, 0);
42 let secondIndexStart = find(onesPerPart + 1, firstIndexEnd + 1) + 1;
43 let thirdIndexStart = find(2 * onesPerPart + 1, secondIndexStart) + 1;
44
45 // Now we just have to check that the remaining parts of the array are the same.
46 while(thirdIndexStart < n && arr[firstIndexEnd] === arr[secondIndexStart] && arr[secondIndexStart] === arr[thirdIndexStart]) {
47 firstIndexEnd += 1;
48 secondIndexStart += 1;
49 thirdIndexStart += 1;
50 }
51
52 // If we reached the end of the array, it means we found a valid split.
53 if (thirdIndexStart === n) {
54 return [firstIndexEnd, secondIndexStart];
55 }
56
57 // If no valid split is found, return [-1, -1].
58 return [-1, -1];
59}
60
Time and Space Complexity
The given Python function threeEqualParts
is intended to solve a problem where, given an array of binary digits, the goal is to split the array into three non-empty parts that all represent the same binary value.
Time Complexity
The time complexity of the code is composed of several parts:
sum(arr)
: This operation traverses the entire array to compute the sum, and has a time complexity ofO(n)
wheren
is the length of the array.- Three separate calls to
find(x)
: Each call tofind(x)
will, in the worst case, traverse the entire array once, therefore the time complexity for all three calls combined isO(n)
. - The while loop: This loop continues incrementing
i
,j
, andk
untilk
reaches the end of the array or a mismatch is found. In the worst case, this leads to traversing the array again, adding anotherO(n)
to the complexity.
The total time complexity is the sum of these parts, leading to O(n) + O(n) + O(n)
which simplifies to O(n)
.
Space Complexity
The space complexity is determined by the amount of additional memory used by the algorithm, which is mainly:
- Constant extra space for variables
n
,cnt
,mod
,i
,j
,k
, ands
, which does not grow with the input size. - No additional data structures that grow with input size are used.
Therefore, the space complexity is O(1)
, which signifies constant space.
In summary, the time complexity of the function is O(n)
and the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first