Tags: "leetcode", "dynamic-programming", "prefix-sum", "hashmapclass Solution: def findMaxLength(self, nums: List[int]) -> int: lookup = {} lookup[0] = -1 max_len = 0 count = 0 for i, num in enumerate(nums): count += 1 if num else -1 if count in lookup: max_len = max(max_len, i-lookup[count]) else: lookup[count] = i return max_len", access_time 1-min read

Edit this post on Github

Contiguous Array

Created: April 13, 2020 by [lek-tin]

Last updated: April 13, 2020

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.

Solution

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        lookup = {}
        lookup[0] = -1
        max_len = 0
        count = 0

        for i, num in enumerate(nums):
            count += 1 if num else -1
            if count in lookup:
                max_len = max(max_len, i-lookup[count])
            else:
                lookup[count] = i

        return max_len