Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
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.
The brute force approach is really simple. We consider every possible subarray within the given array and count the number of zeros and ones in each subarray. Then, we find out the maximum size subarray with equal no. of zeros and ones out of them.\n\n
Time complexity : . We consider every possible subarray by traversing over the complete array for every start point possible.\n
Space complexity : . Only two variables and are required.\n
In this approach, we make use of a variable, which is used to store the relative number of ones and zeros encountered so far while traversing the array. The variable is incremented by one for every encountered and the same is decremented by one for every encountered.\n
We start traversing the array from the beginning. If at any moment, the becomes zero, it implies that we\'ve encountered equal number of zeros and ones from the beginning till the current index of the array(). Not only this, another point to be noted is that if we encounter the same twice while traversing the array, it means that the number of zeros and ones are equal between the indices corresponding to the equal values. The following figure illustrates the observation for the sequence
[0 0 1 0 0 0 1 1]:
In the above figure, the subarrays between (A,B), (B,C) and (A,C) (lying between indices corresponing to ) have equal number of zeros and ones.\n
Another point to be noted is that the largest subarray is the one between the points (A, C). Thus, if we keep a track of the indices corresponding to the same values that lie farthest apart, we can determine the size of the largest subarray with equal no. of zeros and ones easily.\n
Now, the values can range between to , with the extreme points corresponding to the complete array being filled with all 0\'s and all 1\'s respectively. Thus, we make use of an array (of size to keep a track of the various \'s encountered so far. We make an entry containing the current element\'s index () in the for a new encountered everytime. Whenever, we come across the same value later while traversing the array, we determine the length of the subarray lying between the indices corresponding to the same values.\n\n
Time complexity : . The complete array is traversed only once.\n
Space complexity : . array of size is used.\n
This approach relies on the same premise as the previous approach. But, we need not use an array of size , since it isn\'t necessary that we\'ll encounter all the values possible. Thus, we make use of a HashMap to store the entries in the form of . We make an entry for a in the whenever the is encountered first, and later on use the correspoding index to find the length of the largest subarray with equal no. of zeros and ones when the same is encountered again.\n
The following animation depicts the process:\n\n!?!../Documents/525_Contiguous_Array.json:1000,563!?!\n\n
Time complexity : . The entire array is traversed only once.\n
Space complexity : . Maximum size of the HashMap will be , if all the elements are either 1 or 0.\n
Analysis written by: @vinod23\n