Three Equal Parts
HardPrompt
You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value.
If it is possible, return any [i, j] with i + 1 < j, such that:
arr[0], arr[1], ..., arr[i]is the first part,arr[i + 1], arr[i + 2], ..., arr[j - 1]is the second part, andarr[j], arr[j + 1], ..., arr[arr.length - 1]is the third part.- All three parts have equal binary values.
If it is not possible, return [-1, -1].
Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.
Example 1:
Input: arr = [1,0,1,0,1]
Output: [0,3]Example 2:
Input: arr = [1,1,0,1,1]
Output: [-1,-1]Example 3:
Input: arr = [1,1,0,0,1]
Output: [0,2]
Constraints:
3 <= arr.length <= 3 * 104arr[i]is0or1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible way to split the array into three non-empty parts. It iterates through all valid pairs of indices (i, j) that can define the three partitions. For each split, it then compares the binary values of the three resulting subarrays. Since the binary numbers can be very large, a direct conversion to standard integer types is not feasible. Instead, the comparison is done by trimming leading zeros from each part and then comparing the resulting significant bits as sequences.
Algorithm
- Use two nested loops to generate all possible split points
iandj.- The outer loop iterates
ifrom0ton-3. - The inner loop iterates
jfromi+2ton-1.
- The outer loop iterates
- For each pair
(i, j), define three parts:Part 1: arr[0...i],Part 2: arr[i+1...j-1], andPart 3: arr[j...n-1]. - Create a helper function to compare the binary values of these three parts.
- This function finds the first '1' in each part to get its canonical representation (ignoring leading zeros).
- It then checks if the lengths of these canonical parts are equal.
- Finally, it compares the canonical parts element by element.
- If the three parts are found to be equal, return
[i, j]. - If the loops complete without finding a solution, return
[-1, -1].
Walkthrough
The algorithm uses two nested loops to generate all possible split points i and j. The outer loop iterates i from 0 to n-3, and the inner loop iterates j from i+2 to n-1, ensuring that the three parts are non-empty and the condition i + 1 < j is met.
For each pair (i, j), we define three parts by their indices: Part 1: arr[0...i], Part 2: arr[i+1...j-1], and Part 3: arr[j...n-1].
A helper function is used to determine if these three parts represent the same binary value. This function first locates the index of the first '1' in each part. If a part contains only zeros, its value is 0. If all three parts are zeros, they are equal. If the significant parts (starting from the first '1') have different lengths, they cannot be equal. Otherwise, the function proceeds to compare the significant bits of each part element by element. If they all match, a valid partition has been found.
If the loops complete without finding any valid partition, it means no solution exists, and the function returns [-1, -1].
class Solution { public int[] threeEqualParts(int[] arr) { int n = arr.length; for (int i = 0; i < n - 2; i++) { for (int j = i + 2; j < n; j++) { if (arePartsEqual(arr, 0, i, i + 1, j - 1, j, n - 1)) { return new int[]{i, j}; } } } return new int[]{-1, -1}; } private boolean arePartsEqual(int[] arr, int s1, int e1, int s2, int e2, int s3, int e3) { int p1 = findFirstOne(arr, s1, e1); int p2 = findFirstOne(arr, s2, e2); int p3 = findFirstOne(arr, s3, e3); if (p1 == -1 && p2 == -1 && p3 == -1) return true; if (p1 == -1 || p2 == -1 || p3 == -1) return false; int len1 = e1 - p1 + 1; int len2 = e2 - p2 + 1; int len3 = e3 - p3 + 1; if (len1 != len2 || len2 != len3) return false; for (int k = 0; k < len1; k++) { if (arr[p1 + k] != arr[p2 + k] || arr[p2 + k] != arr[p3 + k]) { return false; } } return true; } private int findFirstOne(int[] arr, int start, int end) { for (int i = start; i <= end; i++) { if (arr[i] == 1) { return i; } } return -1; // All zeros }}Complexity
Time
O(N^3). The two nested loops for `i` and `j` run in O(N^2) time. Inside the loops, the `arePartsEqual` function takes O(N) time in the worst case to scan and compare the parts.
Space
O(1). No extra space proportional to the input size is used.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient due to its O(N^3) time complexity.
Will result in a 'Time Limit Exceeded' error on platforms with typical constraints.
Solutions
Solution
class Solution {private int[] arr;public int[] threeEqualParts(int[] arr) { this.arr = arr; int cnt = 0; int n = arr.length; for (int v : arr) { cnt += v; } if (cnt % 3 != 0) { return new int[]{-1, -1}; } if (cnt == 0) { return new int[]{0, n - 1}; } cnt /= 3; int i = find(1), j = find(cnt + 1), k = find(cnt * 2 + 1); for (; k < n && arr[i] == arr[j] && arr[j] == arr[k]; ++i, ++j, ++k) { } return k == n ? new int[]{i - 1, j} : new int[]{-1, -1}; }private int find(int x) { int s = 0; for (int i = 0; i < arr.length; ++i) { s += arr[i]; if (s == x) { return i; } } return 0; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.