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] to arr[i],
• The second part spans from arr[i+1] to arr[j-1], and
• The third part spans from arr[j] to arr[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:

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

2. 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] where n is the length of the array.

3. 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 at find(1)
     • The 1st 1 in the second part at find(cnt + 1)
     • The 1st 1 in the third part at find(cnt * 2 + 1)

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

5. 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:

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

2. Finding the Initial Indices for Comparison: The algorithm finds the indices i, j, and k which point to the first 1 in each of the three parts we want to compare. This is accomplished by calling find(1) for the first 1, find(cnt + 1) for the first 1 in the second part, and find(cnt * 2 + 1) for the first 1 in the third part, where cnt is the count of 1s in any part.

3. Comparing the Three Parts: By initializing i, j, and k to the start of each part, the algorithm enters a while loop which continues until the index k reaches the end of the array. Inside the loop, it checks whether the current bits at arr[i], arr[j], and arr[k] are equal. If they are equal, it means the parts are still matching, and it increments i, j, and k one position forward to compare the next set of bits.

4. 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 1s 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.

Example Walkthrough

Let's consider an example arr = [1, 0, 1, 0, 1, 0] to illustrate the solution approach.

1. Counting 1's and Pre-validation: We start by counting the number of 1s in the array. There are a total of 3 1s, which is divisible by 3. That means we can potentially divide arr into three parts with an equal number of 1s in each part.

2. 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 index 0. We set i to this value.
   • The second 1 is part of the second segment. Since there's one 1 in the first segment, we search for the (1+1)-th 1, which is at index 2. We set j to point to the following position, which is 3.
   • The third 1 is part of the third segment. We search for the (2*1+1)-th 1, which is at index 4. We set k to point to this index.

By the end of this step, we have i = 0, j = 3, and k = 4.

3. Comparing the Three Parts: Now we begin comparing the elements pointed by i, j, and k.

   • At our starting indices the values at arr[i], arr[j], and arr[k] are 1, 0, and 1, respectively. They are not all equal, so we move the i index forward to try to match the values in the next iteration.
   • After incrementing, we have i = 1, j = 3, and k = 4. The values are 0, 0, and 1. The values at j and k are different, so we increment j to try to match in the next iteration.
   • With i = 1, j = 4, and k = 4, now we have arr[i], arr[j], and arr[k] all 0. We increment all indices to find the next value.
   • With i = 2, j = 5, and k = 5, the values are 1, 0, and 0. Now, since arr[j] and arr[k] are equal but different from arr[i], we increment i until arr[i] matches.
   • This process continues until i, j, and k move past the end of arr or until we find a mismatch that we can't resolve by incrementing the pointers.

4. Determining the Correct Split Point: In this example, we see that i can move to 2, making arr[i] a 1, which gives us arr[i], arr[j], and arr[k] values of 1, 0, and 0. 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 yields arr[0] to arr[i] as [1,0], arr[i+1] to arr[j-1] as [1] and the last part arr[j] to arr[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 decrementing i by one to exclude it from the second part, we have arr[0..1], arr[2..4], and arr[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

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:

1. sum(arr): This operation traverses the entire array to compute the sum, and has a time complexity of O(n) where n is the length of the array.
2. Three separate calls to find(x): Each call to find(x) will, in the worst case, traverse the entire array once, therefore the time complexity for all three calls combined is O(n).
3. The while loop: This loop continues incrementing i, j, and k until k reaches the end of the array or a mismatch is found. In the worst case, this leads to traversing the array again, adding another O(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:

1. Constant extra space for variables n, cnt, mod, i, j, k, and s, which does not grow with the input size.
2. 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.