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:
arr[0], arr[1], ..., arr[i] is the first part,arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, andarr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part.If it is not possible, return [-1, -1].
Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.
Example 1:
Input: arr = [1,0,1,0,1] Output: [0,3]
Example 2:
Input: arr = [1,1,0,1,1] Output: [-1,-1]
Example 3:
Input: arr = [1,1,0,0,1] Output: [0,2]
Constraints:
3 <= arr.length <= 3 * 104arr[i] is 0 or 1Problem 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.
In this approach, we iterate through the array while counting the number of 1s. We need to ensure that the number of 1s is divisible by 3, otherwise it's impossible to split the array with equal parts. If it's divisible, each part must contain the same number of 1s.
After determining the number of 1s each part should have, we traverse the array again to find possible split points, and validate if the parts have equal binary values by comparing.
This Python solution first counts the number of 1s in the array. If the count is not divisible by 3, it returns [-1, -1] as it's impossible to divide the array into three parts with equal binary values. If the array contains no 1s, it returns [0, length-1] since every part can be all 0s. It then finds the starting indices of the three parts, where each part should contain an equal number of 1s.
It checks if the segments starting at these indices are of the same value. If yes, it returns the indices just before the start of the second and third parts.
Python
JavaScript
Java
Time Complexity: O(n), where n is the length of the array, as we are traversing the array a few times.
Space Complexity: O(1), as no additional space is used except for variables.
This approach uses hashing to store the indices of 1s as keys and their count as values for faster retrieval and comparison.
Once we determine the number of 1s each part should have (after verifying it's divisible by 3), we use these indices to segment the array into candidate parts. Hashing ensures we efficiently compare these binary segments.
This C# solution is similar in logic to the other languages, ensuring the array can be divided into three equal parts of ones. We store the locations of the ones using index positions, and only move once processed sections are validated as the same.
C#
Time Complexity: O(n)
Space Complexity: O(1)
We denote the length of the array as n, and the number of '1's in the array as cnt.
Obviously, cnt must be a multiple of 3, otherwise the array cannot be divided into three equal parts, and we can return [-1, -1] in advance. If cnt is 0, it means that all elements in the array are '0', and we can directly return [0, n - 1].
We divide cnt by 3 to get the number of '1's in each part, and then find the position of the first '1' in each part in the array arr (refer to the find(x) function in the following code), denoted as i, j, k respectively.
0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
^ ^ ^
i j k
Then we start from i, j, k and traverse each part at the same time, check whether the corresponding values of the three parts are equal. If they are, continue to traverse until k reaches the end of arr.
0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
^ ^ ^
i j k
At the end of the traversal, if k=n, it means that it satisfies the three equal parts, and we return [i - 1, j] as the answer, otherwise return [-1, -1].
The time complexity is O(n), where n is the length of arr. The space complexity is O(1).
Similar problems:
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Iterative Matching with Counting | Time Complexity: O(n), where n is the length of the array, as we are traversing the array a few times. Space Complexity: O(1), as no additional space is used except for variables. |
| Hashing to Check Parts | Time Complexity: O(n) Space Complexity: O(1) |
| Counting + Three Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Matching with Counting | O(n) | O(1) | Best general solution. Minimal memory usage and optimal for large arrays. |
| Hashing to Check Parts | O(n) | O(n) | Useful when implementing straightforward equality checks or when clarity is preferred over memory efficiency. |
Three Equal Parts | Leetcode 927 | Live coding session • Coding Decoded • 3,529 views views
Watch 9 more video solutions →Practice Three Equal Parts with our built-in code editor and test cases.
Practice on FleetCode