Three Equal Parts

LeetCode Q 927 - Three Equal Parts

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:

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

Solution

• count how many ones (if num%3!=0 return [-1,-1])
• search from right side to left, until we found num/3 1s. This index is not final answer, but it defines patten of 1s
• from left, ignore leading 0s, and then match the pattern found in step 2, to get the first EndIndex
• do another matching to found second EndIndex

Code:

private static final int[] IMP = new int[]{-1, -1};
public int[] threeEqualParts(int[] A) {	
  // step 1 : count 1s
  int ones = 0;
  for (int a: A) {
    if (a == 1) ones++;
  }

  // step 2 : find thirdIndex which defines the 1s pattern
  int count = 0, thirdIndex = 0;
  for (int i = A.length - 1; i >= 0; i--)  {
    if (A[i] == 1) count++;
    if (count == ones / 3) { thirdIndex = i; break; }
  }

  // step 3: find firstEndIndex
  int res1 = findEndIndex(A, 0, thirdIndex - 1);
  if (res1 == -1) return IMP;

  // step 4: find secondEndIndex
  int res2 = findEndIndex(A, res1 + 1, thirdIndex - 1);
  if (res2 == -1) return IMP;

  return new int[]{res1, res2};
}

private int findEndIndex(int[] A, int left, int right) {
  while (A[left] == 0) { left++; }

  while (right < A.length) {
    if (A[right] != A[left]) return -1;
    left++; right++;
  }
}