Three Equal Parts - Video Solutions

Problem Overview: You get a binary array. The task is to split it into three non‑empty parts so that each part represents the same binary value (leading zeros allowed). Return the split indices, or [-1, -1] if no such partition exists.

Approach 1: Iterative Matching with Counting (O(n) time, O(1) space)

This approach relies on counting the number of 1s in the array. If the total count is not divisible by 3, equal partitions are impossible. Once the count is known, locate the starting index of the first 1 in each of the three segments. These indices define the canonical binary pattern each segment must match. Then iterate forward simultaneously from the three start positions and verify that every bit matches until the end of the array. Because binary equality depends on the suffix pattern rather than prefix zeros, aligning these segments ensures all three represent the same number.

The key insight is that equal binary values must share the same trailing sequence of bits after the first 1. By identifying the three starting points of those sequences and comparing them directly, you avoid building strings or performing numeric conversions. This method performs a single pass for counting and another pass for matching, giving O(n) time with constant extra space. It relies purely on index arithmetic and sequential iteration, making it efficient for large arrays.

Approach 2: Hashing to Check Parts (O(n) time, O(n) space)

This alternative method builds explicit representations of candidate partitions and compares them using hashing. As you iterate through the array, construct prefix segments and track possible cut points. Each candidate segment can be normalized by trimming leading zeros and converting the remaining bits into a comparable string or hashed value. If all three normalized representations match, the partition is valid.

Hashing simplifies equality checks because you only compare hash values rather than full sequences. However, generating normalized strings or hashes requires additional memory proportional to the input size. While still linear in time, the space complexity becomes O(n). This technique is easier to reason about if you're comfortable with hashing but is less optimal than the counting approach.

The logic also connects closely with bit manipulation and numeric representation concepts from math. Two binary sequences represent the same value when their significant bits match, ignoring leading zeros.

Recommended for interviews: Iterative Matching with Counting is the expected solution. Interviewers typically look for the observation that the number of 1s must be divisible by three and that the three segments must share the same suffix pattern. Showing a brute-force or hashing idea first demonstrates reasoning, but the constant-space linear scan shows stronger algorithmic insight.