# Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

# Example 1:
# Input: [0,1]
# Output: 2
# Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
# Example 2:
# Input: [0,1,0]
# Output: 2
# Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
# Note: The length of the given binary array will not exceed 50,000.

class Solution:
    # time:O(n)
    # space:O(n)
    def findMaxLength(self, nums: List[int]) -> int:
        max_len = 0
        balance_cnt = 0
        # init with count 0 at index -1
        hash_tbl = {0: -1}
        for idx in range(len(nums)):
            if nums[idx] == 1:
                balance_cnt += 1
            else:
                balance_cnt -= 1
            if balance_cnt in hash_tbl:
                max_len = max(max_len, idx - hash_tbl[balance_cnt])
            else:
                hash_tbl[balance_cnt] = idx
        return max_len
