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

Leetcode 12th Day Challenge.

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

C# Program

public class Solution {
    
    public int FindMaxLength(int[] nums) {
        
        var map = new Dictionary<int,int>();
        
        int maxLen = 0, count = 0;
        
        map.Add(0,-1);
        
        for(int i=0;i<nums.Length;i++)
        {
            count = count + ((nums[i] == 1) ? 1 : -1);
           
            if(map.ContainsKey(count))
            {
                maxLen = Math.Max(maxLen, i - map[count]);
            }
            else
                map.Add(count,i);
        }
        
        return maxLen;
    }
}

Code Walk Through

Time Complexity: O(n)

Space Complexity: O(n)