#927

Hard

LeetCode Problem Workspace

Three Equal Parts

Divide a binary array into three contiguous parts such that each part represents the same integer value in binary, using array and math logic.

array math

Problem Statement

Given a binary array arr containing only 0s and 1s, partition it into three non-empty contiguous subarrays such that each subarray represents the same binary value. Return indices [i, j] satisfying i + 1 < j that define the first and second split points.

If no valid partition exists that produces equal binary values in all three parts, return [-1, -1]. Each subarray must maintain the original order of elements, and leading zeros are allowed but ignored when comparing integer values.

Examples

Example 1

Input: arr = [1,0,1,0,1]

Output: [0,3]

Example details omitted.

Example 2

Input: arr = [1,1,0,1,1]

Output: [-1,-1]

Example details omitted.

Example 3

Input: arr = [1,1,0,0,1]

Output: [0,2]

Example details omitted.

Constraints

3 <= arr.length <= 3 * 104
arr[i] is 0 or 1

Solution Approach

Count total ones and validate divisibility

Compute the total number of 1s in the array. If this number is not divisible by three, an equal split is impossible, so return [-1, -1]. Handle the special case where there are zero ones by returning any valid split.

Identify target segment patterns

Determine the number of ones each part must contain. Traverse the array to locate the starting index of each part containing the correct number of ones. Compare segments by aligning trailing ones and ensuring they match exactly, accounting for leading zeros.

Calculate split indices

Once the three matching segments are identified, compute the split indices i and j by accounting for trailing zeros needed to maintain alignment. Return [i, j] if all three segments match; otherwise, return [-1, -1].

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for single-pass counting and alignment checks, where n is the length of the array. Space complexity is O(1) additional memory if segments are compared via indices without extra arrays.

What Interviewers Usually Probe

Checking if total ones count is divisible by three is crucial.
Careful handling of leading zeros distinguishes correct from incorrect partitions.
Aligning segments from the last one backwards helps validate equality efficiently.

Common Pitfalls or Variants

Common pitfalls

Assuming leading zeros affect integer comparison, which can cause wrong splits.
Forgetting to handle arrays with zero ones as a valid equal split.
Incorrectly computing indices when trailing zeros are required for alignment.

Follow-up variants

Partition a binary array into k equal-value parts instead of three, requiring generalization of ones distribution.
Find the minimal length of the first part to achieve three equal binary values for optimization problems.
Allowing arrays with non-binary integers and defining equality via decimal value rather than binary string comparison.

FAQ

What is the main challenge in the Three Equal Parts problem?

The primary challenge is aligning three segments of a binary array so that each represents the same integer value, handling leading zeros, and ensuring proper index calculation.

How do I handle arrays with zero ones?

If the array contains only zeros, any split producing three non-empty parts is valid because all segments represent the integer zero.

Does the order of elements in arr matter?

Yes, the original order must be preserved; the three parts must be contiguous subarrays maintaining the original sequence.

Can this solution scale to large arrays?

Yes, the approach is linear O(n) in time and constant O(1) extra space, making it efficient for arrays up to 3 * 10^4 elements.

How do trailing zeros affect the solution?

Trailing zeros at the end of segments must match to ensure the binary values are equal, so split indices should account for them carefully.

terminal

Solution

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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]

Continue Practicing

#932 beautiful array #939 minimum area rectangle #914 x of a kind in a deck of cards