Three Equal Parts: Binary Array Partitioning

May 25, 20265 min read

leetcodeproblemhardarraysmath

LeetCode 927, "Three Equal Parts," asks you to partition a binary array into three contiguous parts that all represent the same binary value. Given an array arr of 0s and 1s, you need to find indices [i, j] such that arr[0..i], arr[i+1..j-1], and arr[j..end] all represent the same number in binary. If no valid partition exists, return [-1, -1].

arr = [1,0,1,0,1,0]. Each part represents binary "10" (decimal 2). Return [1, 4].

Why this problem matters

This problem sits at the intersection of array manipulation and binary number properties. It teaches you to think about what makes two binary representations "equal," specifically that leading zeros don't change a value but trailing zeros do. The key realization is that you can't just split the array arbitrarily; you need the actual bit patterns (after ignoring leading zeros) to match across all three segments.

In interviews, this problem tests whether you can decompose a complex constraint into manageable sub-problems: counting, pattern matching, and index arithmetic. These same skills apply when working with data serialization, network protocols, or any domain where fixed-width binary fields matter.

The brute force approach

A naive approach would try all possible pairs (i, j) and convert each part to its decimal value:

def threeEqualParts(arr):
    n = len(arr)
    for i in range(n - 2):
        for j in range(i + 2, n):
            part1 = int("".join(map(str, arr[:i+1])), 2)
            part2 = int("".join(map(str, arr[i+1:j])), 2)
            part3 = int("".join(map(str, arr[j:])), 2)
            if part1 == part2 == part3:
                return [i, j]
    return [-1, -1]

This runs in O(n^3) time (two nested loops plus string conversion) and will time out on large inputs. We need a linear approach.

The key insight

The crucial observation is: if all three parts represent the same binary value, they must contain the same number of 1s. Since the total number of 1s must split evenly, the count of ones must be divisible by 3. If the count is zero, any partition works because all parts are just zeros.

Once you know each part contains exactly total_ones / 3 ones, you can find where each part's significant bits begin (at each group's first 1). The trailing zeros after the very last 1 in the array belong to all three parts equally, which constrains where the partition boundaries fall.

Think of it this way: the third part's trailing zeros are fixed by the array itself. Parts one and two must also include that many trailing zeros. This pins down the exact split points.

Walking through it step by step

Step 1: Count the 1s

Count total ones = 3. Since 3 % 3 == 0, a valid partition may exist. Each part must contain exactly 1 one.

Step 2: Find where each group of 1s starts

1st one at index 0, 2nd one at index 2, 3rd one at index 4. These mark the start of each part's significant bits.

Step 3: Match bit patterns from each start

Starting from each 1, read forward: Part1=[1,0], Part2=[1,0], Part3=[1,0]. All three bit sequences match.

Step 4: Account for trailing zeros

Trailing zeros after the last 1 (index 5) count for all parts. Here there is 1 trailing zero. Each part already includes it.

Step 5: Compute partition indices

Part 1 ends at i=1, Part 2 starts at i+1=2 and ends at j-1=3, Part 3 starts at j=4. Return [1, 4].

Practice this problem with spaced repetition

The optimized solution

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

    k = ones // 3
    indices = [i for i, v in enumerate(arr) if v == 1]

    first = indices[0]
    second = indices[k]
    third = indices[2 * k]

    trailing = len(arr) - 1 - indices[-1]

    while third + trailing < len(arr):
        if arr[first] != arr[second] or arr[first] != arr[third]:
            return [-1, -1]
        first += 1
        second += 1
        third += 1

    return [first - 1, second]

Here is how the code works:

Count the total number of 1s. If zero, return [0, len(arr) - 1] since all parts are zero. If not divisible by 3, return [-1, -1].
Collect the indices of all 1s and divide them into three groups of k = ones // 3.
Identify the starting positions of each group: first, second, and third.
Calculate trailing zeros: the number of zeros after the last 1 in the array.
Walk all three pointers forward in lockstep, comparing bits. The third pointer must reach the end of the array (accounting for trailing zeros).
If all bits match, the split points are [first - 1, second] after the loop finishes.

Complexity analysis

Metric	Value
Time	O(n)
Space	O(n)

The time is linear because we scan the array a constant number of times. Space is O(n) for the list of 1-indices, though you could reduce it to O(1) by finding the positions with a counting pass instead.

Building blocks

1. Counting and divisibility check

ones = sum(arr)
if ones % 3 != 0:
    return [-1, -1]

Many partition problems start with a divisibility check. If a quantity must split evenly among k parts, verify total % k == 0 first to fail fast.

2. Pointer synchronization pattern

while third + trailing < len(arr):
    if arr[first] != arr[second] or arr[first] != arr[third]:
        return [-1, -1]
    first += 1
    second += 1
    third += 1

Walking multiple pointers in lockstep to verify pattern equality is a powerful technique. You will see it in string matching, palindrome verification, and cycle detection problems as well.

The trailing zeros trick is what makes this problem "hard." Without it, you would need to handle leading zeros explicitly for each part, which is much messier.

Edge cases

All zeros: any split works, return [0, len(arr) - 1].
One count not divisible by 3: impossible, return [-1, -1].
Single 1 in the array: impossible (can't split one 1 into three equal parts).
No trailing zeros: the partition boundaries sit exactly at the end of each group of ones.
Large trailing zero blocks: the first and second parts must "absorb" extra trailing zeros, pushing their boundaries forward.

Build your pattern library with CodeBricks

From understanding to recall

Reading through a solution once gives you comprehension, but that is only half the battle. Research on memory shows that retrieval practice, actively recalling how an algorithm works without looking at it, builds durable knowledge far more effectively than passive review.

Try closing this page and writing the solution from scratch. Focus on the three-phase structure: count ones, find starting positions, verify with synchronized pointers. If you get stuck on the trailing zeros logic, that is the exact signal to revisit and practice again in a day or two.

Spaced repetition systems automate this cycle. Instead of cramming before an interview, you review problems at expanding intervals, catching them right before you would forget. This transforms dozens of LeetCode patterns from "I saw that once" into second nature.

Sort Array By Parity II - another array partitioning problem using index-based placement
3Sum with Multiplicity - counting and divisibility in the context of triplet sums
Flip String to Monotone Increasing - binary string analysis with a prefix/suffix split approach

Three Equal Parts rewards the kind of structured thinking that comes from deliberate practice. If you want a system that schedules these problems for you and tracks which patterns you have mastered, CodeBricks handles the logistics so you can focus on building real fluency.

Try CodeBricks free