Contiguous Array

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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s