Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/927.html

927. Three Equal Parts

Level

Hard

Description

Given an array A of 0s and 1s, divide the array into 3 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:

  • A[0], A[1], ..., A[i] is the first part;
  • A[i+1], A[i+2], ..., A[j-1] is the second part, and
  • A[j], A[j+1], ..., A[A.length - 1] is the third part.
  • All three parts have equal binary value.

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: [1,0,1,0,1]

Output: [0,3]

Example 2:

Input: [1,1,0,1,1]

Output: [-1,-1]

Note:

  1. 3 <= A.length <= 30000
  2. A[i] == 0 or A[i] == 1

Solution

If the three parts represent the same binary value, then the three parts must contain exactly the same values, except the leading zeros.

First consider a special case, where all elements are 0. If A[0] is 0, then loop over A and check whether all elements are 0. If so, then simply return an array [0, A.length - 1].

If not all elements are 0, which means at least one element is 1, then loop over array A and use a map to store the counts of 1’s and the corresponding indices. Specifically, if a key-value pair (k, v) is in the map, then A[v] is the k-th occurrence of 1 in the array A starting from the left.

Obviously, if the three parts represent the same binary value, then each part must contain the same number of 1’s. Therefore, if the total number of 1’s is not divisible by 3, return [-1, -1].

Since no more elements are after the last part, the lengths of each part after removing the leading zeros can be determined by the last part. Suppose there are k elements 1 in each part, then the three indices in the three parts are initially index1 = 1, index2 = k + 1 and index 3 = k * 2 + 1, respectively. Each time check the three elements at the three indices. If the elements are not the same, then return [-1. -1]. If the elements are all the same, then move all three indices to the right by 1 step. Repeat the process until index3 becomes A.length. Finally, if the three parts represent the same binary value, return [index1 - 1, index2].

  • class Solution {
    public int[] threeEqualParts(int[] A) {
        int length = A.length;
        if (A[0] == 0) {
            boolean flag = true;
            for (int i = 1; i < length; i++) {
                if (A[i] == 1) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return new int[]{0, length - 1};
        }
        int onesCount = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            if (A[i] == 1) {
                onesCount++;
                map.put(onesCount, i);
            }
        }
        if (onesCount % 3 != 0)
            return new int[]{-1, -1};
        int onesEachPart = onesCount / 3;
        int index1 = map.get(1);
        int index2 = map.get(onesEachPart + 1);
        int index3 = map.get(onesEachPart * 2 + 1);
        while (index3 < length) {
            int num1 = A[index1], num2 = A[index2], num3 = A[index3];
            if (num1 != num2 || num1 != num3)
                return new int[]{-1, -1};
            index1++;
            index2++;
            index3++;
        }
        return new int[]{index1 - 1, index2};
    }
}

  • // OJ: https://leetcode.com/problems/three-equal-parts/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& A) {
        int sum = accumulate(begin(A), end(A), 0);
        if (sum % 3) return {-1,-1};
        if (sum == 0) return {0, (int)A.size() - 1};
        sum /= 3; 
        int last = A.size() - 1;
        while (A[last] == 0) --last;
        int trailingZeros = A.size() - last - 1, firstBegin = 0;
        while (A[firstBegin] == 0) ++firstBegin;
        int firstEnd = firstBegin, cnt = 0;
        while (cnt < sum) cnt += A[firstEnd++];
        for (int i = 0; i < trailingZeros; ++i, ++firstEnd);
        int j = firstEnd, i = firstBegin;
        while (A[j] == 0) ++j;
        while (i < firstEnd && A[i] == A[j]) ++i, ++j;
        if (i < firstEnd) return {-1, -1};
        int secondEnd = j;
        while (A[j] == 0) ++j;
        i = firstBegin;
        while (i < firstEnd && A[i] == A[j]) ++i, ++j;
        if (i < firstEnd) return {-1, -1};
        return {firstEnd - 1, secondEnd};
    }
};

  • 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]



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

All Problems

All Solutions