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

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:

• Convert a Binary Tree to Doubly Linked List
• Longest Increasing Subsequence using Dynamic Programming
• Reverse a Linked List
• Bottom View of a Binary Tree
• Find ancestors of a given node in a Binary Tree
• WAP to Print Triangle Using * Character
• Find maximum of minimum for every window size in a given array
• How to find and remove loops in a Linked List?
• Check if a subarray with 0 sum exists or not
• Find minimum jumps required to reach the destination