Contiguous Array

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.

 

 

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int cnt=0,ans=0;
        
        unordered_map<int,int> mp;
        mp[0]=-1;
        for(int i=0;i<nums.size();++i)
        {
            cnt+= nums[i]==0 ?-1:+1;
               if(mp.find(cnt)!=mp.end())
                   ans=max(ans,i-mp[cnt]);
               else
                   mp[cnt]=i;
        }
        
       return ans;
    }
};