Day 13 of 30-Day LeetCode Challenge

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

C++ Solution :

int findMaxLength(vector<int>& nums) {
if(nums.size()==0) return 0;
for(int i=0;i<nums.size();++i) if(nums[i]==0) nums[i] = -1;
//Since all 0’s are converted to -1, now the problem
//reduces to finding maximum length subarray with sum 0
int prefixSum[nums.size()];
prefixSum[0] = nums[0];
for(int i=1;i<nums.size();++i) prefixSum[i] = prefixSum[i-1]+nums[i];
int result = 0;
unordered_map<int, int> mp;
for(int i=0;i<nums.size();++i){
if(mp.find(prefixSum[i])==mp.end()) mp.insert(make_pair(prefixSum[i],i));
else { result = max(result, i-mp[prefixSum[i]]); }
if(prefixSum[i]==0) result = max(result, i+1); //handles corner case
}
return result;
}