Three Equal Parts - Leetcode Solution

The Three Equal Parts problem on LeetCode is a problem that requires a bit of thinking, but with the right approach, it can be solved efficiently. Here is a detailed solution to the problem.

Problem Statement:

Given an array of binary integers, return three non-empty parts such that all of them have the same binary value.

Solution:

To solve the problem, we need to first identify if there exists a solution. In other words, we need to check if the array can be divided into three equal parts, each having the same binary value. To do this, we can perform the following steps:

Step 1: Calculate the total number of 1's in the array.

Step 2: If the total number of 1's is not divisible by three, return [-1,-1]. This is because there is no way we can divide the array into three parts having equal binary value.

Step 3: Calculate the value of onesInEachPart as the total number of 1's divided by three.

Step 4: Traverse the array from right to left and count the number of 1's in the last part of the array. Once you reach onesInEachPart, you have found the last part of the array. Store its index in a variable lastPartIndex.

Step 5: Traverse the array from right to left again and repeat Step 4 for the second part.

Step 6: Traverse the array from left to right starting from index 0 and count the number of 1's in the first part of the array. Once you reach onesInEachPart, you have found the first part of the array. Store its index in a variable firstPartIndex.

Step 7: Traverse the array from left to right again and repeat Step 6 for the second part.

Step 8: Check if the three parts have equal binary value. If they do, return [firstPartIndex, lastPartIndex+1]. Otherwise, return [-1,-1].

Code:

Here is the code for the solution to the Three Equal Parts problem on LeetCode:

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        vector<int> result{-1,-1};
        int n=arr.size();
        int ones=0;
        for(int i=0; i<n; i++){
            if(arr[i]==1) ones++;
        }
        if(ones % 3 != 0) return result;
        if(ones == 0) return {0, n-1};
        int onesInEachPart = ones / 3;
        int lastPartIndex=-1, secondPartIndex=-1;
        int cnt=0;
        for(int i=n-1; i>=0; i--){
            if(arr[i]==1) cnt++;
            if(cnt==onesInEachPart){
                lastPartIndex=i;
                break;
            }
        }
        cnt=0;
        for(int i=lastPartIndex-1; i>=0; i--){
            if(arr[i]==1) cnt++;
            if(cnt==onesInEachPart){
                secondPartIndex=i;
                break;
            }
        }
        cnt=0;
        int firstPartIndex=0;
        for(int i=0; i<n; i++){
            if(arr[i]==1) cnt++;
            if(cnt==onesInEachPart){
                firstPartIndex=i;
                break;
            }
        }
        cnt=0;
        int secondPartStart=secondPartIndex+1;
        for(int i=secondPartStart; i<n; i++){
            if(arr[i]==1) cnt++;
            if(cnt==onesInEachPart){
                int thirdPartStart=i+1;
                for(int j=0; j<=onesInEachPart-1; j++){
                    if(arr[firstPartIndex+j]!=arr[secondPartIndex+j] || arr[secondPartIndex+j]!=arr[thirdPartStart+j]){
                        return result;
                    }
                }
                return {firstPartIndex+onesInEachPart-1, secondPartIndex+onesInEachPart};
            }
        }
        return result;
    }
};

The time complexity of this solution is O(n) as we are traversing the array only four times. The space complexity is O(1) as we are not using any extra memory other than the result vector.

1