Algorithm & Data Structure - Three Equal Parts
This is an interesting problem that could be solved more efficient than thought.
- Leetcode - 927
Brutal Force
A brutal force thought using two loops would be: for every \(i\), find a \(j > i+1\), and measure whether the three parts would be equal. The question now is how to measure their equality. We could convert the numbers to string by omitting the leading zeros, and compare the equality of strings. Because of the comparison, the total time complexity would be O(n^3).
public int[] threeEqualParts(int[] arr) {
StringBuilder all = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
all.append(arr[i]);
}
int[] ans = new int[]{-1, -1};
for (int i = 0; i < arr.length; i++){
for (int j = i+2; j < arr.length; j++) {
int is = 0;
while (is < i && arr[is] == 0) is++;
int js = i+1;
while (js < j-1 && arr[js] == 0) js++;
int ks = j;
while (ks < arr.length-1 && arr[ks] == 0) ks++;
if (all.substring(is,i+1).equals(all.substring(js,j)) && all.substring(is,i+1).equals(all.substring(ks))) {
ans[0] = i;
ans[1] = j;
return ans;
}
}
}
return ans;
}
Faster Solution
Since it is a binary value, to have three parts equal, a few conditions have to be fullfilled:
- Each part contains the same number of 1s;
- After leading 0s, all 1s and 0s should match.
Condition 1 means the total 1s in the array has to be divisible by 3. Condition 2 means the effective start position of each part is a 1, and before this this position, all previous parts contains the same number of 1s. With these two observations, we could do the following:
- Find the total ones, if it is not divisible by 3, return;
- Find the number of ones for each part;
- Find the start position of each part by counting ones.
- The effective length of all parts could be obtained from the start position of the last part to the end of the array.
- Comparing each bit of all parts.
This method takes O(n);
public int[] threeEqualParts(int[] arr) {
int[] ans = new int[]{-1, -1};
int totalOnes = 0;
for (int num : arr) {
if (num == 1) totalOnes++;
}
if (totalOnes%3 != 0) return ans;
if (totalOnes == 0) return new int[]{0, arr.length-1};
int unitOnes = totalOnes/3;
int countOne = 0;
int p1 = 0, p2 = 0, p3 = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
countOne++;
if (countOne == 1) {
p1 = i;
} else if (countOne == unitOnes + 1) {
p2 = i;
} else if (countOne == 2*unitOnes + 1) {
p3 = i;
}
}
}
int maxLen = arr.length - p3;
for (int i = 0; i < maxLen; i++) {
if (arr[p1+i] != arr[p3+i] || arr[p2+i] != arr[p3+i]) {
return ans;
}
}
return new int[]{p1+maxLen-1, p2+maxLen};
}