Find Maximum Length Subarray Having an Equal Number of 0’s and 1’s

Posted in

Find Maximum Length Subarray Having an Equal Number of 0’s and 1’s

Vinay Khatri
Last updated on June 10, 2022

    Problem

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

    Sample Input

    [0,1,1,0,1]

    Sample Output

    4

    Explanation

    The array is [0,1,1,0]

    Brute force approach

    The brute force method is quite simple. Within the provided array, we evaluate every conceivable subarray and count the number of zeros and ones in each subarray. Then we find the largest subarray with an equal number of zeros and ones. This approach is inefficient and the time complexity goes upto O(n2).

    Efficient Approach

    In this method, we utilize a count variable to track the number of ones and zeros encountered so far while traversing the array. The count variable is increased by one for every 1 encountered and by one for every 0 encountered. We begin our traversal of the array from the beginning. If the count of 0 and 1 ever become equal, it means that we've met an equal number of zeros and ones from the beginning of the array to the current index i Not only that, but if we meet the same count twice when traversing the array, it implies that the number of zeros and ones are the same between them.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    int findMaxLength(vector<int>&a) {
     	unordered_map<int,int>mp;
        	int one=0, zero=0;  //keep track of 1s and 0s
        	int ans=0;
        	int n=a.size();
        	for(int i=0;i<n;i++){
            	if(a[i]==0) zero++;  
            	if(a[i]==1) one++;
            	if(zero==one) ans=max(ans,i+1);  // if prefix has equal zero and ones
            	if(mp.find(zero-one)!=mp.end()){
                	    ans=max(i-mp[zero-one],ans);  //update answer
            	}
            	else{
                	    mp[zero-one]=i;
            	}
        	}
        	return ans;
    	}
    int main(){
        vectora{1,0,1,0,0};
        cout << findMaxLength(a);
    }
    

    Python Programming

    def findMaxLengthSubarray(nums):
            sum = 0
            h = {}
            res = 0
            for i in range(len(nums)):
                if(nums[i] == 0):
                    sum -= 1
                else:
                    sum += 1
                if(sum == 0):
                    res = max(res, i+1)  #if prefix has equal number of zeros and 1s
                elif(sum not in h):
                    h[sum] = i
                else:
                    res = max(res, i-h[sum]) #update the answer
            return res
    l = [0,1,0,1,0]
    print(findMaxLengthSubarray(l))
    

    C# Programming

    using System;
    using System.Collections.Generic;
    
    class Solution
    {
    
    static int FindMax(int[] nums) {
            var max = 0;
            var dif = 0;
            var Dif = new Dictionary<int, int> { [0] = -1 };   //create hashmap to store the key-value pair
    
            for (var index = 0; index < nums.Length; index++) {
                dif += nums[index] == 1 ? 1 : -1;
    
                if (Dif.TryGetValue(dif, out var start))
                    max = Math.Max(max, index - start);   // update the answer
                else
                    Dif[dif] = index;
            }
            return max;
        }
    public static void Main(String []args)
    {
        	int[] arr = {0, 1, 0, 1, 0};
        	int n = arr.Length;
        	Console.WriteLine(FindMax(arr));
    
    }
    }

    Output

    4

    People are also reading:

    Leave a Comment on this Post

    0 Comments