<p>You are given an array <code>arr</code> which consists of only zeros and ones, divide the array into <strong>three non-empty parts</strong> such that all of these parts represent the same binary value.</p>

<p>If it is possible, return any <code>[i, j]</code> with <code>i + 1 &lt; j</code>, such that:</p>

<ul>
	<li><code>arr[0], arr[1], ..., arr[i]</code> is the first part,</li>
	<li><code>arr[i + 1], arr[i + 2], ..., arr[j - 1]</code> is the second part, and</li>
	<li><code>arr[j], arr[j + 1], ..., arr[arr.length - 1]</code> is the third part.</li>
	<li>All three parts have equal binary values.</li>
</ul>

<p>If it is not possible, return <code>[-1, -1]</code>.</p>

<p>Note that the entire part is used when considering what binary value it represents. For example, <code>[1,1,0]</code> represents <code>6</code> in decimal, not <code>3</code>. Also, leading zeros <strong>are allowed</strong>, so <code>[0,1,1]</code> and <code>[1,1]</code> represent the same value.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> arr = [1,0,1,0,1]
<strong>Output:</strong> [0,3]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> arr = [1,1,0,1,1]
<strong>Output:</strong> [-1,-1]
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> arr = [1,1,0,0,1]
<strong>Output:</strong> [0,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= arr.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>arr[i]</code> is <code>0</code> or <code>1</code></li>
</ul>

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)

        # part 1

        # get total_count and create prefix_sum
        total_count = 0
        prefix_sum = [0] * n
        for i in range(n):
            total_count += arr[i]
            prefix_sum[i] = total_count

        # checking if multiple of 3
        if total_count % 3 != 0:
            return [-1, -1]
        elif total_count == 0:
            return [0, n - 1]

        # binary search to get first occurrence of `val` using prefix_sum
        def bin_search(val):
            start = 0
            end = n - 1
            mid = 0

            while start <= end:
                mid = (start + end) // 2
                if prefix_sum[mid] >= val:
                    if start == end:
                        return mid
                    end = mid
                else:
                    start = mid + 1

            return mid

        
        # count of ones in each part and count of ending_zeroes
        part_count = total_count // 3
        ending_zeroes = n - 1 - bin_search(total_count)

        # value of i and j using binary_search and ending_zeroes
        i = bin_search(part_count) + ending_zeroes + 1
        j = bin_search(total_count - part_count) + ending_zeroes + 1



        # part 2

        # disregard starting zeroes in first part
        a = 0
        while a < n and arr[a] == 0:
            a += 1

        # disregard starting zeroes in second part
        b = i
        while b < n and arr[b] == 0:
            b += 1

        # disregard starting zeroes in third part
        c = j
        while c < n and arr[c] == 0:
            c += 1

        # check if indices have same order of ones and zeroes
        while c < n:
            if arr[a] == arr[b] and arr[b] == arr[c]:
                a += 1
                b += 1
                c += 1
            else:
                return [-1, -1]

        if a == i and b == j:
            return [i - 1, j]
        else:
            return [-1, -1]
18400