927. Three Equal Parts

Description

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

Solutions

Solution 1: Counting + Three Pointers

We denote the length of the array as \(n\), and the number of '1's in the array as \(cnt\).

Obviously, \(cnt\) must be a multiple of \(3\), otherwise the array cannot be divided into three equal parts, and we can return \([-1, -1]\) in advance. If \(cnt\) is \(0\), it means that all elements in the array are '0', and we can directly return \([0, n - 1]\).

We divide \(cnt\) by \(3\) to get the number of '1's in each part, and then find the position of the first '1' in each part in the array arr (refer to the \(find(x)\) function in the following code), denoted as \(i\), \(j\), \(k\) respectively.

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
  ^         ^             ^
  i         j             k

Then we start from \(i\), \(j\), \(k\) and traverse each part at the same time, check whether the corresponding values of the three parts are equal. If they are, continue to traverse until \(k\) reaches the end of arr.

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
          ^         ^             ^
          i         j             k

At the end of the traversal, if \(k=n\), it means that it satisfies the three equal parts, and we return \([i - 1, j]\) as the answer, otherwise return \([-1, -1]\).

The time complexity is \(O(n)\), where \(n\) is the length of arr. The space complexity is \(O(1)\).

Similar problems:

1573. Number of Ways to Split a String

Python3JavaC++GoJavaScript

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]

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

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

func threeEqualParts(arr []int) []int {
    find := func(x int) int {
        s := 0
        for i, v := range arr {
            s += v
            if s == x {
                return i
            }
        }
        return 0
    }
    n := len(arr)
    cnt := 0
    for _, v := range arr {
        cnt += v
    }
    if cnt%3 != 0 {
        return []int{-1, -1}
    }
    if cnt == 0 {
        return []int{0, n - 1}
    }
    cnt /= 3
    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 = i+1, j+1, k+1 {
    }
    if k == n {
        return []int{i - 1, j}
    }
    return []int{-1, -1}
}

/**
 * @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];
};

927. Three Equal Parts

Description

Solutions

Solution 1: Counting + Three Pointers

Comments