Find maximum length sub-array having equal number of 0’s and 1’s

Given an binary array containing 0 and 1, find maximum length sub-array having equal number of 0’s and 1’s.

 

For example,


Input:  { 0, 0, 1, 0, 1, 0, 0 }

Output: Largest subarray is { 0, 1, 0, 1 } or { 1, 0, 1, 0}

 


 

Naive solution would be to consider all sub-arrays and for each sub-array, we count total number of 0’s and 1’s present. If sub-array contains equal number of 0’s and 1’s, we update maximum length sub-array if required. The time complexity of naive solution is O(n3) as there are n2 sub-arrays and it takes O(n) time to find count 0’s and 1’s. The method can be optimized to run in O(n2) time by calculating count of 0’s and 1’s in constant time.

 

We can use map to solve this problem in linear time. The idea is to replace 0 with -1 and find out the largest subarray with 0 sum. To find largest subarray with 0 sum, we create an empty map which stores the ending index of first sub-array having given sum. We traverse the given array, and maintain sum of elements seen so far.

  • If sum is seen for first time, insert the sum with its index into the map.
     
  • If sum is seen before, there exists a sub-array with 0 sum which ends at current index and we update maximum length sub-array if current sub-array has more length.

C++

Download   Run Code

Java

Download   Run Code



Output:

[1, 4]

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Jerome Labonte
Jerome Labonte

Instead of going through the array three times to change 0 to -1, find the longest sub-array and then revert -1 to 0, wouldn’t it be more optimal to simple do this at line 32 ? :
sum += (arr[i] == 0)? -1: 1;

wpDiscuz