Three Equal Parts

Three Equal Parts

What is this problem about?

Imagine an array of 0s and 1s representing a binary number. "Three Equal Parts" asks if you can divide this array into three non-empty contiguous parts such that all three parts represent the same binary value. If it's possible, you need to return the boundary indices of the parts; otherwise, return [-1, -1]. Leading zeros in each part are ignored when comparing the binary values.

Why is this asked in interviews?

This three equal parts interview question is a hard-level problem from Hotstar. It tests your ability to handle complex array partitioning and your understanding of binary representation. Since the number of 1s must be equal in each of the three parts, it evaluates whether you can use that property as a starting point for an efficient O(n) solution.

Algorithmic pattern used

This problem follows the Array, Math interview pattern.

1. Count the total number of 1s in the array. If the total is not divisible by 3, return [-1, -1].
2. If there are no 1s, any valid partition works (e.g., [0, n-1]).
3. Identify the positions of the 1s that start each of the three parts (the 1st, (count/3 + 1)th, and (2*count/3 + 1)th "1").
4. The key observation is that the third part dictates how many trailing zeros must be in all parts.
5. Use three pointers starting at the first "1" of each part and move them simultaneously. At each step, the bits must match.
6. The movement continues until the third pointer reaches the end of the array.
7. If all bits matched, return the indices of the gaps.

Example explanation

Array: [1, 0, 1, 0, 1, 0].

1. Total 1s = 3. Each part must have one "1".
2. 1s are at indices 0, 2, 4.
3. Part 1 starts at 0, Part 2 starts at 2, Part 3 starts at 4.
4. Move pointers:
   • (0, 2, 4) -> bits (1, 1, 1). Match!
   • (1, 3, 5) -> bits (0, 0, 0). Match!
5. Third pointer reached the end.
6. Gap 1 is at index 1, Gap 2 is at index 3. Result: [1, 4] (index of end of first part and start of third part). Wait, the format is usually [end_of_p1, start_of_p3].

Common mistakes candidates make

In "Three Equal Parts coding problem," the most common mistake is failing to account for trailing zeros. Leading zeros don't change a binary value, but trailing zeros do. Another error is not checking all bits after the 1s are balanced, which leads to incorrect results for cases where the 1s are in the right places but the 0s in between aren't.

Interview preparation tip

When dealing with binary arrays and equality, focus on the "1" bits first, as they are the "anchors" of the values. Practice using multiple pointers to compare segments of an array. This problem is an excellent test of index management and boundary condition handling.