525. Contiguous Array

Problem Link

Description

---

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

Solution

---

Python3

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        mp = {}
        mp[0] = -1
        res = curr = 0
 
        for i, x in enumerate(nums):
            if x == 0:
                curr -= 1
            else:
                curr += 1
            
            if curr in mp:
                res = max(res, i - mp[curr])
            else:
                mp[curr] = i
        
        return res