LeetCode 927 - Three Equal Parts

The problem asks us to partition a binary array arr into three non-empty contiguous segments such that each segment, when interpreted as a binary number (allowing leading zeros), is equal to the other two segments.

leetcodehardarraymath

LeetCode Problem 927

Difficulty: 🔴 Hard
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to partition a binary array arr into three non-empty contiguous segments such that each segment, when interpreted as a binary number (allowing leading zeros), is equal to the other two segments. The array contains only zeros and ones, and the goal is to return indices [i, j] where i + 1 < j such that the first segment is arr[0..i], the second segment is arr[i+1..j-1], and the third segment is arr[j..n-1]. If no such partition exists, we return [-1, -1].

The constraints tell us that arr can have up to 30,000 elements, so any solution that attempts to check all possible partitions naively will be too slow. Leading zeros are allowed, meaning segments like [0,1,1] and [1,1] are considered equal in value. This is important because it affects how we compare segments. Edge cases include arrays with all zeros, arrays with a number of ones not divisible by three, and arrays where the only valid splits require precise alignment of ones.

Approaches

A brute-force approach would consider every possible pair (i, j) that satisfies i + 1 < j, convert each segment into its decimal or binary string representation, and compare them. This would be correct but infeasible because there are O(n^2) pairs and O(n) work per comparison, resulting in O(n^3) time complexity. Given the constraint of up to 30,000 elements, this is far too slow.

The key observation for an optimal solution is that the binary value of a segment is determined by the positions of its ones, and leading zeros do not matter. Therefore, if the total number of ones in arr is divisible by three, each part must contain exactly total_ones / 3 ones. This allows us to locate the starting and ending indices of each part directly by counting ones. Once we know the segments that start with the first one of each part and end with the last one, we can compare the segments element by element. We also account for trailing zeros after the last one of the last segment to ensure alignment.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Check all possible partitions, convert each to integer or string, and compare
Optimal O(n) O(1) Count ones, identify segments by ones positions, compare only necessary elements

Algorithm Walkthrough

  1. Count the total number of ones in arr. If it is not divisible by three, immediately return [-1, -1] because equal binary parts are impossible.
  2. If total_ones is zero, every segment is zero, so return [0, n-1] as any split works.
  3. Calculate ones_per_part = total_ones / 3. This tells us how many ones must be in each segment.
  4. Identify the index of the first one and the last one in each of the three segments by scanning the array. For example, the first segment starts at the first one and ends at the ones_per_part-th one.
  5. Compare the three segments element by element to verify they are identical, accounting for trailing zeros. If any mismatch occurs, return [-1, -1].
  6. If segments match, compute the indices i and j as the end of the first segment and the start of the third segment minus one, adjusted for the number of trailing zeros needed to align the segments.
  7. Return [i, j] as the valid partition.

Why it works: Each segment must contain the same number of ones, and the sequence of ones and zeros in the trailing positions must match. By aligning the segments using the first and last one in each segment and verifying equality, we guarantee the binary values are identical, which satisfies the problem requirements.

Python Solution

from typing import List

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        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 = 0
        ones_count = 0

        for i, val in enumerate(arr):
            if val == 1:
                ones_count += 1
                if ones_count == 1:
                    first = i
                elif ones_count == ones_per_part + 1:
                    second = i
                elif ones_count == 2 * ones_per_part + 1:
                    third = i

        n = len(arr)
        length = n - third
        if arr[first:first + length] != arr[second:second + length] or arr[first:first + length] != arr[third:]:
            return [-1, -1]

        return [first + length - 1, second + length]

The implementation first counts the total number of ones and handles the zero and non-divisible cases. Then it determines the starting indices of the three parts based on ones count. The length of each segment to check is determined by the trailing zeros at the end of the array. Finally, the equality check is done slice by slice, and the indices are returned.

Go Solution

func threeEqualParts(arr []int) []int {
    totalOnes := 0
    for _, val := range arr {
        totalOnes += val
    }
    if totalOnes%3 != 0 {
        return []int{-1, -1}
    }
    if totalOnes == 0 {
        return []int{0, len(arr) - 1}
    }

    onesPerPart := totalOnes / 3
    n := len(arr)
    first, second, third := 0, 0, 0
    onesCount := 0

    for i, val := range arr {
        if val == 1 {
            onesCount++
            if onesCount == 1 {
                first = i
            } else if onesCount == onesPerPart+1 {
                second = i
            } else if onesCount == 2*onesPerPart+1 {
                third = i
            }
        }
    }

    length := n - third
    for i := 0; i < length; i++ {
        if arr[first+i] != arr[second+i] || arr[first+i] != arr[third+i] {
            return []int{-1, -1}
        }
    }

    return []int{first + length - 1, second + length}
}

The Go version is very similar to the Python version. Slices are used for comparisons through a loop instead of slice equality. Go-specific considerations include explicit handling of slices and using integer arithmetic safely.

Worked Examples

Example 1: [1,0,1,0,1]

total_ones = 3, ones_per_part = 1. The first ones are at indices [0, 2, 4]. Each part length is n - third = 5 - 4 = 1. The slices [0:1], [2:3], [4:5] all equal [1]. Return [0,3].

Example 2: [1,1,0,1,1]

total_ones = 4, not divisible by 3. Return [-1,-1].

Example 3: [1,1,0,0,1]

total_ones = 3, ones_per_part = 1. The first ones are at [0,1,4]. Length 5-4 = 1. Slices [0:1]=[1], [1:2]=[1], [4:5]=[1] match. Return [0,2].

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array at most twice: once to count ones and once to compare segments
Space O(1) Only a few integer variables are used, no additional arrays proportional to input

The reasoning: counting ones and identifying the start indices is linear. Slice comparisons only cover the necessary trailing sequence, not the entire array, so total work is O(n).

Test Cases

# Provided examples
assert Solution().threeEqualParts([1,0,1,0,1]) == [0,3]  # standard case
assert Solution().threeEqualParts([1,1,0,1,1]) == [-1,-1]  # impossible split
assert Solution().threeEqualParts([1,1,0,0,1]) == [0,2]  # another valid split

# Edge cases
assert Solution().threeEqualParts([0,0,0,0]) == [0,3]  # all zeros
assert Solution().threeEqualParts([1,1,1]) == [0,2]  # minimal valid split
assert Solution().threeEqualParts([1,0,0,1,0,0,1,0,0]) == [2,5]  # trailing zeros
assert Solution().threeEqualParts([1,0,1,0,1,0,1]) == [-1,-1]  # ones not