We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Three Equal Parts

Difficulty: Hard

Problem 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 the three parts have equal binary values. If it is not possible, return [-1, -1].

Key Insights

  • The total number of 1s in the array must be divisible by 3 for it to be possible to split it into three equal parts.
  • The binary values represented by the parts must match, including leading zeros.
  • The split points must ensure that the sections are non-empty and the values are equal.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can follow these steps:

  1. Count the total number of 1s in the array. If this count is not divisible by 3, return [-1, -1].
  2. Identify the indices of the first, second, and third 1 from the end of the array.
  3. Compare the segments between these indices to ensure they represent the same binary value.
  4. Return the indices of the splits if valid.

The approach primarily uses a single pass to count and identify positions, and then another pass to verify the segments.

Code Solutions

def threeEqualParts(arr):
    total_ones = sum(arr)
    
    if total_ones % 3 != 0:
        return [-1, -1]
    
    if total_ones == 0:
        return [0, len(arr) - 1]

    ones_per_part = total_ones // 3
    first, second, third = -1, -1, -1
    count = 0

    for i in range(len(arr)):
        if arr[i] == 1:
            count += 1
            if count == 1:
                first = i
            elif count == ones_per_part + 1:
                second = i
            elif count == 2 * ones_per_part + 1:
                third = i

    while third < len(arr) and arr[first] == arr[second] == arr[third]:
        first += 1
        second += 1
        third += 1

    if third == len(arr):
        return [first - 1, second]
    
    return [-1, -1]
← Back to All Questions