pylist

525. Contiguous Array

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:
        d = dict() # key: accumulated sum, value: index
        d[0] = -1
        accu = 0
        for i, n in enumerate(nums):
            if n == 1:
                accu += 1
            else:
                accu -= 1
            if accu not in d:
                d[accu] = i
            # if accu in d: # not necessary
            #     d[accu] = min(d[accu], i)
            
        accu = 0
        max_len = 0
        for i, n in enumerate(nums):
            if n == 1:
                accu += 1
            else:
                accu -= 1
            max_len = max(max_len, i - d[accu])
            
        return max_len

Care