Three Equal Parts

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.

Examples

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 * 10^4
• arr[i] is 0 or 1

Solution

Method 1 - Count 1s and Match Suffixes

We count the number of 1s in the array. If not divisible by 3, return [-1, -1]. Otherwise, we find the starting index of each part so that the binary values match, including trailing zeros. We compare the three parts for equality.

Code

C++

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int n = arr.size();
        int ones = 0;
        for (int x : arr) ones += x;
        if (ones == 0) return {0, n-1};
        if (ones % 3 != 0) return {-1, -1};
        int k = ones / 3;
        int i1 = -1, i2 = -1, i3 = -1, cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 1) {
                ++cnt;
                if (cnt == 1) i1 = i;
                if (cnt == k+1) i2 = i;
                if (cnt == 2*k+1) i3 = i;
            }
        }
        int len = n - i3;
        if (i1+len <= i2 && i2+len <= i3) {
            for (int j = 0; j < len; ++j) {
                if (arr[i1+j] != arr[i2+j] || arr[i1+j] != arr[i3+j])
                    return {-1, -1};
            }
            return {i1+len-1, i2+len};
        }
        return {-1, -1};
    }
};

Java

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int n = arr.length, ones = 0;
        for (int x : arr) ones += x;
        if (ones == 0) return new int[]{0, n-1};
        if (ones % 3 != 0) return new int[]{-1, -1};
        int k = ones / 3, i1 = -1, i2 = -1, i3 = -1, cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 1) {
                ++cnt;
                if (cnt == 1) i1 = i;
                if (cnt == k+1) i2 = i;
                if (cnt == 2*k+1) i3 = i;
            }
        }
        int len = n - i3;
        if (i1+len <= i2 && i2+len <= i3) {
            for (int j = 0; j < len; ++j) {
                if (arr[i1+j] != arr[i2+j] || arr[i1+j] != arr[i3+j])
                    return new int[]{-1, -1};
            }
            return new int[]{i1+len-1, i2+len};
        }
        return new int[]{-1, -1};
    }
}

Python

from typing import List
class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ones = sum(arr)
        if ones == 0:
            return [0, n-1]
        if ones % 3 != 0:
            return [-1, -1]
        k = ones // 3
        i1 = i2 = i3 = cnt = 0
        for i, x in enumerate(arr):
            if x == 1:
                cnt += 1
                if cnt == 1: i1 = i
                if cnt == k+1: i2 = i
                if cnt == 2*k+1: i3 = i
        l = n - i3
        if i1+l <= i2 and i2+l <= i3:
            if arr[i1:i1+l] == arr[i2:i2+l] == arr[i3:i3+l]:
                return [i1+l-1, i2+l]
        return [-1, -1]

Rust

impl Solution {
    pub fn three_equal_parts(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        let ones = arr.iter().filter(|&&x| x == 1).count();
        if ones == 0 { return vec![0, n as i32 - 1]; }
        if ones % 3 != 0 { return vec![-1, -1]; }
        let k = ones / 3;
        let (mut i1, mut i2, mut i3, mut cnt) = (0, 0, 0, 0);
        for (i, &x) in arr.iter().enumerate() {
            if x == 1 {
                cnt += 1;
                if cnt == 1 { i1 = i; }
                if cnt == k+1 { i2 = i; }
                if cnt == 2*k+1 { i3 = i; }
            }
        }
        let l = n - i3;
        if i1+l <= i2 && i2+l <= i3 {
            if arr[i1..i1+l] == arr[i2..i2+l] && arr[i1..i1+l] == arr[i3..i3+l] {
                return vec![(i1+l-1) as i32, (i2+l) as i32];
            }
        }
        vec![-1, -1]
    }
}

TypeScript

function threeEqualParts(arr: number[]): number[] {
    const n = arr.length;
    const ones = arr.reduce((a, b) => a + b, 0);
    if (ones === 0) return [0, n-1];
    if (ones % 3 !== 0) return [-1, -1];
    const k = ones / 3;
    let i1 = -1, i2 = -1, i3 = -1, cnt = 0;
    for (let i = 0; i < n; ++i) {
        if (arr[i] === 1) {
            ++cnt;
            if (cnt === 1) i1 = i;
            if (cnt === k+1) i2 = i;
            if (cnt === 2*k+1) i3 = i;
        }
    }
    const len = n - i3;
    if (i1+len <= i2 && i2+len <= i3) {
        for (let j = 0; j < len; ++j) {
            if (arr[i1+j] !== arr[i2+j] || arr[i1+j] !== arr[i3+j])
                return [-1, -1];
        }
        return [i1+len-1, i2+len];
    }
    return [-1, -1];
}

Complexity

• ⏰ Time complexity: O(N)
• 🧺 Space complexity: O(1)