{x}
blog image

Three Equal Parts

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

Solution Explanation: 927. Three Equal Parts

This problem asks to partition a binary array into three non-empty parts with equal binary values. The solution leverages a counting strategy combined with a three-pointer approach for efficient traversal.

Algorithm:

  1. Count Ones: First, count the total number of 1s in the input array arr. If the count is not divisible by 3, it's impossible to create three equal parts, so we return [-1, -1]. If the count is 0 (all zeros), we can return [0, n-1] as a valid partition (where n is the array length).

  2. Find Partition Points: Divide the total count of 1s by 3 to get the number of 1s in each part. We then use a helper function find(x) to locate the index where the cumulative sum of 1s reaches x, x + count_per_part, and x + 2 * count_per_part. These indices (i, j, k) represent the end points of the three parts.

  3. Verify Equality: Starting from i, j, and k, we iterate simultaneously through the three parts. If at any point, the corresponding elements in the three parts are not equal, we know the partition is invalid, and we return [-1, -1]. If the iteration completes without finding any inequality and k reaches the end of the array, the partition is valid, and we return [i-1, j] (note: i-1 because i is the index after the first part).

Time Complexity Analysis:

The algorithm involves a single pass through the array to count 1s and a single pass for verification. The find() function also does a single pass. Therefore, the overall time complexity is O(n), where n is the length of the input array.

Space Complexity Analysis:

The algorithm uses only a constant amount of extra space for variables like counters and indices. The space complexity is O(1).

Code Examples (Python, Java, C++, Go, JavaScript):

The provided code snippets in different languages implement this algorithm effectively. The core logic remains consistent across all implementations, showcasing the efficiency and readability of the approach. The find() function is a helper function used to efficiently locate the indices that mark the boundaries of the three parts. The main part of the code then verifies the equality of these partitions.

Example Walkthrough (Python):

Let's consider the example arr = [1, 0, 1, 0, 1].

  1. cnt (number of 1s) = 3. This is divisible by 3.
  2. cnt / 3 = 1 (number of 1s per part).
  3. find(1) returns 0 (index i).
  4. find(2) returns 2 (index j).
  5. find(3) returns 4 (index k).
  6. The loop compares arr[1], arr[3], and arr[5] (though arr[5] is outside the bounds, the loop will stop at index 4). This comparison holds true.
  7. The function returns [0, 2].

This demonstrates how the algorithm efficiently finds a valid partition if one exists. If no such partition is possible, the algorithm correctly returns [-1, -1].