# Three Equal Parts
**Difficulty:** HARD
[External](https://leetcode.com/problems/three-equal-parts)
Canonical: https://scaleengineer.com/dsa/problems/three-equal-parts
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Hotstar](https://scaleengineer.com/companies/hotstar)
---
## Problem
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`

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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]`.

```java
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
    }
}
```
### Algorithm
*   Use two nested loops to generate all possible split points `i` and `j`.
    *   The outer loop iterates `i` from `0` to `n-3`.
    *   The inner loop iterates `j` from `i+2` to `n-1`.
*   For each pair `(i, j)`, define three parts: `Part 1: arr[0...i]`, `Part 2: arr[i+1...j-1]`, and `Part 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]`.

## Counting Ones and Pattern Matching
This efficient approach is built on a crucial observation: for three parts to represent the same binary value, they must contain the same number of ones. This allows us to quickly discard impossible scenarios and significantly narrow down the search space for the split points `i` and `j`. The core idea is to determine the required pattern from the third part (as its form is fixed) and then verify if the first two parts can be formed to match this pattern.
**Time:** O(N). The algorithm involves a few passes over the array (counting ones, finding indices, final comparison), each taking linear time. Thus, the total time complexity is O(N). · **Space:** O(C), where C is the total number of ones. In the worst case, the array consists of all ones, leading to O(N) space complexity to store their indices.
**Pros:** Optimal O(N) time complexity, making it very efficient for large inputs.; Systematically handles all constraints and edge cases.
**Cons:** The logic is more involved than the brute-force approach, requiring careful index management.; Requires O(N) extra space in the worst case to store the indices of ones.
### Explanation
1.  **Count Ones:** The algorithm begins by counting the total number of `1`s in the array. If this count is zero, the entire array is zeros, and any valid partition like `[0, n-1]` works. If the count is not divisible by 3, a valid partition is impossible.

2.  **Identify Part Structure:** If the number of ones is a multiple of 3, say `3k`, then each of the three parts must contain exactly `k` ones. We find the indices of all `1`s in the array to locate the boundaries of these groups of `k` ones.

3.  **Determine Canonical Form:** The binary value of a part is determined by its bits starting from the first '1'. Since all three parts must be equal, their canonical forms must be identical. The third part's form is rigid because it has no subsequent part to absorb trailing zeros. Therefore, the number of zeros after the last '1' in the entire array (`trailingZeros`) dictates the number of trailing zeros required for the first two parts.

4.  **Calculate Split Points:** The end of the first part, `i`, is determined by the index of its last '1' (the `k`-th '1' overall) plus `trailingZeros`. Similarly, the end of the second part, `j-1`, is found using the `2k`-th '1' and `trailingZeros`. This gives us a candidate solution `[i, j]`.

5.  **Verification:** We must perform two final checks:
    *   **Spacing:** The calculated `i` and `j` must create valid, non-overlapping partitions. The end of part 1 (`i`) must come before the first '1' of part 2. The end of part 2 (`j-1`) must come before the first '1' of part 3.
    *   **Pattern Matching:** The bit patterns of the three parts (from their respective first '1's to their ends) must be identical. This is checked by a single pass comparing the three segments.

If both checks pass, `[i, j]` is a valid solution. Otherwise, no solution exists.

```java
class Solution {
    public int[] threeEqualParts(int[] arr) {
        int n = arr.length;
        int totalOnes = 0;
        for (int bit : arr) {
            if (bit == 1) {
                totalOnes++;
            }
        }

        if (totalOnes == 0) {
            return new int[]{0, n - 1};
        }

        if (totalOnes % 3 != 0) {
            return new int[]{-1, -1};
        }

        int k = totalOnes / 3;
        int[] onesIndices = new int[totalOnes];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                onesIndices[count++] = i;
            }
        }

        // Start indices of the significant bits of each part
        int p1_start = onesIndices[0];
        int p2_start = onesIndices[k];
        int p3_start = onesIndices[2 * k];

        // End indices of the significant bits of each part
        int p1_end = onesIndices[k - 1];
        int p2_end = onesIndices[2 * k - 1];
        int p3_end = onesIndices[3 * k - 1];

        // Number of trailing zeros in the third part determines the form for all parts
        int trailingZeros = n - 1 - p3_end;

        // Calculate the end of the first and second parts
        int i = p1_end + trailingZeros;
        int j = p2_end + trailingZeros + 1;

        // Check if parts have enough space for leading zeros and don't overlap
        if (i >= p2_start || (j - 1) >= p3_start) {
            return new int[]{-1, -1};
        }
        
        // Compare the three canonical parts to ensure they are identical
        int len = n - p3_start; // Length of the canonical part
        for (int l = 0; l < len; l++) {
            if (arr[p1_start + l] != arr[p2_start + l] || arr[p2_start + l] != arr[p3_start + l]) {
                return new int[]{-1, -1};
            }
        }

        return new int[]{i, j};
    }
}
```
### Algorithm
*   Count the total number of `1`s in the array, `totalOnes`.
*   Handle two base cases:
    *   If `totalOnes` is 0, all elements are 0. Any partition is valid. Return `[0, n-1]`.
    *   If `totalOnes` is not divisible by 3, it's impossible to have three parts with an equal number of ones. Return `[-1, -1]`.
*   If `totalOnes` is divisible by 3, calculate `k = totalOnes / 3`. Each part must contain `k` ones.
*   Find and store the indices of all `1`s in the array.
*   The pattern of bits for all three parts must be identical to the pattern of the third part, as it has no adjustable trailing zeros. The number of trailing zeros in the third part is `trailingZeros = n - 1 - (index of last '1')`.
*   Calculate the potential split points `i` and `j`. The first part must end at `i = (index of k-th '1') + trailingZeros`. The second part must end at `j-1 = (index of 2k-th '1') + trailingZeros`.
*   Verify that these split points are valid. The first part must not overlap with the significant bits of the second part, and similarly for the second and third parts. This means `i` must be less than the start of the second part's significant bits, and `j-1` must be less than the start of the third's.
*   Finally, compare the three canonical parts (from their first '1' to their end) to ensure they are identical. If all checks pass, return `[i, j]`; otherwise, return `[-1, -1]`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} arr * @return {number[]} */ var threeEqualParts =
  function (arr) {
    function find(x) {
      let s = 0;
      for (let i = 0; i < n; ++i) {
        s += arr[i];
        if (s == x) {
          return i;
        }
      }
      return 0;
    }
    const n = arr.length;
    let cnt = 0;
    for (const v of arr) {
      cnt += v;
    }
    if (cnt % 3) {
      return [-1, -1];
    }
    if (cnt == 0) {
      return [0, n - 1];
    }
    cnt = Math.floor(cnt / 3);
    let [i, j, k] = [find(1), find(cnt + 1), find(cnt * 2 + 1)];
    for (; k < n && arr[i] == arr[j] && arr[j] == arr[k]; ++i, ++j, ++k) {}
    return k == n ? [i - 1, j] : [-1, -1];
  };

```

### Python

```python
class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]: def find(x): s = 0 for i, v in enumerate(arr): s += v if s == x: return i n = len(arr) cnt, mod = divmod(sum(arr), 3) if mod: return [- 1, - 1] if cnt == 0: return [0, n - 1] i, j, k = find(1), find(cnt + 1), find(cnt * 2 + 1) while k < n and arr[i] == arr[j] == arr[k]: i, j, k = i + 1, j + 1, k + 1 return [i - 1, j] if k == n else [- 1, - 1]

```

### CPP

```cpp
class Solution {
public:
  vector<int> threeEqualParts(vector<int> &arr) {
    int n = arr.size();
    int cnt = accumulate(arr.begin(), arr.end(), 0);
    if (cnt % 3)
      return {-1, -1};
    if (!cnt)
      return {0, n - 1};
    cnt /= 3;
    auto find = [&](int x) {
      int s = 0;
      for (int i = 0; i < n; ++i) {
        s += arr[i];
        if (s == x)
          return i;
      }
      return 0;
    };
    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 ? vector<int>{i - 1, j} : vector<int>{-1, -1};
  }
};

```