927. Three Equal Parts LeetCode Solution

In this guide, you will get 927. Three Equal Parts LeetCode Solution with the best time and space complexity. The solution to Three Equal Parts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Three Equal Parts solution in C++
Three Equal Parts solution in Java
Three Equal Parts solution in Python
Additional Resources

927. Three Equal Parts LeetCode Solution image

Problem Statement of Three Equal Parts

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, and
arr[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 * 104
arr[i] is 0 or 1

Complexity Analysis

Time Complexity:
Space Complexity:

927. Three Equal Parts LeetCode Solution in C++

class Solution {
 public:
  vector<int> threeEqualParts(vector<int>& arr) {
    const int ones = ranges::count_if(arr, [](int a) { return a == 1; });

    if (ones == 0)
      return {0, static_cast<int>(arr.size()) - 1};
    if (ones % 3 != 0)
      return {-1, -1};

    int k = ones / 3;
    int i;
    int j;
    int first;
    int second;
    int third;

    for (i = 0; i < arr.size(); ++i)
      if (arr[i] == 1) {
        first = i;
        break;
      }

    int gapOnes = k;

    for (j = i + 1; j < arr.size(); ++j)
      if (arr[j] == 1 && --gapOnes == 0) {
        second = j;
        break;
      }

    gapOnes = k;

    for (i = j + 1; i < arr.size(); ++i)
      if (arr[i] == 1 && --gapOnes == 0) {
        third = i;
        break;
      }

    while (third < arr.size() && arr[first] == arr[second] &&
           arr[second] == arr[third]) {
      ++first;
      ++second;
      ++third;
    }

    if (third == arr.size())
      return {first - 1, second};
    return {-1, -1};
  }
};
/* code provided by PROGIEZ */

927. Three Equal Parts LeetCode Solution in Java

class Solution {
  public int[] threeEqualParts(int[] arr) {
    int ones = 0;

    for (final int a : arr)
      if (a == 1)
        ++ones;

    if (ones == 0)
      return new int[] {0, arr.length - 1};
    if (ones % 3 != 0)
      return new int[] {-1, -1};

    int k = ones / 3;
    int i = 0;
    int j = 0;
    int first = 0;
    int second = 0;
    int third = 0;

    for (i = 0; i < arr.length; ++i)
      if (arr[i] == 1) {
        first = i;
        break;
      }

    int gapOnes = k;

    for (j = i + 1; j < arr.length; ++j)
      if (arr[j] == 1 && --gapOnes == 0) {
        second = j;
        break;
      }

    gapOnes = k;

    for (i = j + 1; i < arr.length; ++i)
      if (arr[i] == 1 && --gapOnes == 0) {
        third = i;
        break;
      }

    while (third < arr.length && arr[first] == arr[second] && arr[second] == arr[third]) {
      ++first;
      ++second;
      ++third;
    }

    if (third == arr.length)
      return new int[] {first - 1, second};
    return new int[] {-1, -1};
  }
}
// code provided by PROGIEZ

927. Three Equal Parts LeetCode Solution in Python

class Solution:
  def threeEqualParts(self, arr: list[int]) -> list[int]:
    ones = sum(a == 1 for a in arr)

    if ones == 0:
      return [0, len(arr) - 1]
    if ones % 3 != 0:
      return [-1, -1]

    k = ones // 3
    i = 0

    for i in range(len(arr)):
      if arr[i] == 1:
        first = i
        break

    gapOnes = k

    for j in range(i + 1, len(arr)):
      if arr[j] == 1:
        gapOnes -= 1
        if gapOnes == 0:
          second = j
          break

    gapOnes = k

    for i in range(j + 1, len(arr)):
      if arr[i] == 1:
        gapOnes -= 1
        if gapOnes == 0:
          third = i
          break

    while third < len(arr) and arr[first] == arr[second] == arr[third]:
      first += 1
      second += 1
      third += 1

    if third == len(arr):
      return [first - 1, second]
    return [-1, -1]
 # code by PROGIEZ