<p>Given a binary array <code>nums</code>, return <em>the maximum length of a contiguous subarray with an equal number of </em><code>0</code><em> and </em><code>1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums[i]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

from collections import defaultdict
import operator
import itertools

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        counts = defaultdict(int)
        counts[0] = 1
        prefix = list(itertools.chain([0], itertools.accumulate((1 if x > 0 else -1 for x in nums), operator.add)))
        ans = curr = 0
        for i in range(2, len(nums) + 1, 2):
            curr *= 2 if prefix[i-2] == 0 else 0
            ans += counts[curr - 1]
            counts[curr] += 1
        return ans + 1

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        prefix = list(itertools.accumulate((1 if x > 0 else -1 for x in nums), operator.add))
        if prefix[-1] == 0:
            return len(nums)
        
        lefts = {0:0}
        for i, p in enumerate(prefix):
            if p not in lefts:
                lefts[p] = i
        rights = dict()
        for i, p in enumerate(reversed(prefix)):
            if p not in rights:
                rights[p] = len(nums) - i - 1
        mv = -1
        for v in set(itertools.chain(lefts, rights)):
            if v in rights and v in lefts:
                val = rights[v] - lefts[v]
                if v == 0:
                    val += 1
                mv = max(mv, val)
        return mv
        
            
20100