LeetCode 927: Three Equal Parts Solution

Master LeetCode problem 927 (Three Equal Parts), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

927. Three Equal Parts

Hard

Array Math

Problem Explanation

Explanation

To solve this problem, we need to find three equal parts in the given binary array such that all three parts represent the same binary value. We can approach this problem by counting the total number of ones in the array and then calculating if it is possible to divide the array into three equal parts with the same number of ones.

Calculate the total number of ones in the array. If the total number of ones is not divisible by 3, it is not possible to divide the array into three equal parts with the same binary value.
Find the starting and ending positions of the three parts by counting zeros in between the parts. If the zeros in between the parts are not enough to accommodate the remaining ones equally, then it is not possible.
Check if the three parts are equal by comparing them element by element.

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the array.

Space Complexity

The space complexity of this solution is O(1) as we are not using any extra space apart from a few variables.

Solution Code

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int onesCount = 0;
        for (int num : arr) {
            if (num == 1) onesCount++;
        }
        
        if (onesCount == 0) {
            return new int[]{0, arr.length-1};
        }
        if (onesCount % 3 != 0) {
            return new int[]{-1, -1};
        }
        
        int onesInEachPart = onesCount / 3;
        int firstEnd = findEndIndex(arr, onesInEachPart);
        if (firstEnd == -1) return new int[]{-1, -1};
        
        int secondEnd = findEndIndex(arr, onesInEachPart + 1);
        if (secondEnd == -1) return new int[]{-1, -1};
        
        int thirdEnd = findEndIndex(arr, onesInEachPart * 2);
        if (thirdEnd == -1) return new int[]{-1, -1};
        
        while (thirdEnd < arr.length && arr[firstEnd] == arr[secondEnd] && arr[secondEnd] == arr[thirdEnd]) {
            firstEnd++;
            secondEnd++;
            thirdEnd++;
        }
        
        if (thirdEnd == arr.length) {
            return new int[]{firstEnd-1, secondEnd};
        }
        
        return new int[]{-1, -1};
    }
    
    private int findEndIndex(int[] arr, int onesCount) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                count++;
                if (count == onesCount) {
                    return i;
                }
            }
        }
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 927 (Three Equal Parts)?

This page provides optimized solutions for LeetCode problem 927 (Three Equal Parts) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 927 (Three Equal Parts)?

The time complexity for LeetCode 927 (Three Equal Parts) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 927 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 927 in Java, C++, or Python.

Back to LeetCode Solutions