Longest Subarray With Equal Number of 0s and 1s

Given an array arr[] containing only 0s and 1s, find the longest subarray which contains equal no of 0s and 1s.

Examples: 

Input: arr[] = [1, 0, 1, 1, 1, 0, 0]
Output: 6
Explanation: arr[1 ... 6] is the longest subarray with three 0s and three 1s.

Input: arr[] = [0, 0, 1, 1, 0]
Output: 4
Explanation: arr[0 ... 3] or arr[1 ... 4] is the longest subarray with two 0s and two 1s.

Input: arr[] = [0]
Output: 0
Explanation: There is no subarray with an equal number of 0s and 1s.

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space

A simple approach is to generate all possible subarrays and check whether the subarray has equal number of 0s and 1s or not. To make this process easy we find cumulative sum of the subarrays taking 0s as -1 and 1s as +1. If the cumulative sum is equal to 0 for any subarray then update the current maximum length with the maximum of length of current subarray and its own value.

// C++ program to find the longest subarray with  // equal number of 0s and 1s using nested loop #include <iostream> #include <vector> using namespace std; int maxLen(vector<int> &arr) {  int res = 0;  // Pick a starting point as 's'  for (int s = 0; s < arr.size(); s++) {  int sum = 0;  // Consider all subarrays arr[s...e]  for (int e = s; e < arr.size(); e++) {  sum += (arr[e] == 0) ? -1 : 1;   // Check if it's a 0-sum subarray   if (sum == 0)   // update max size  res = max(res, e - s + 1);  }  }  return res; } int main() {  vector<int> arr = { 1, 0, 0, 1, 0, 1, 1 };  cout << maxLen(arr); } 

// C program to find the longest subarray with  // equal number of 0s and 1s using nested loop #include <stdio.h> int maxLen(int arr[], int n) {  int res = 0;  // Pick a starting point as 's'  for (int s = 0; s < n; s++) {  int sum = 0;  // Consider all subarrays arr[s...e]  for (int e = s; e < n; e++) {  sum += (arr[e] == 0) ? -1 : 1;  // Check if it's a 0-sum subarray  if (sum == 0)  // Update max size  res = (res > e - s + 1) ? res : (e - s + 1);  }  }  return res; } int main() {  int arr[] = {1, 0, 0, 1, 0, 1, 1};  int n = sizeof(arr) / sizeof(arr[0]);  printf("%d", maxLen(arr, n));  return 0; } 

// Java program to find the longest subarray with // equal number of 0s and 1s using nested loop import java.util.*; class GfG {  static int maxLen(int[] arr) {  int res = 0;  // Pick a starting point as 's'  for (int s = 0; s < arr.length; s++) {  int sum = 0;  // Consider all subarrays arr[s...e]  for (int e = s; e < arr.length; e++) {  sum += (arr[e] == 0) ? -1 : 1;  // Check if it's a 0-sum subarray  if (sum == 0)  // Update max size  res = Math.max(res, e - s + 1);  }  }  return res;  }  public static void main(String[] args) {  int[] arr = {1, 0, 0, 1, 0, 1, 1};  System.out.println(maxLen(arr));  } } 

# Python program to find the longest subarray with # equal number of 0s and 1s using nested loop def maxLen(arr): res = 0 # Pick a starting point as 's' for s in range(len(arr)): sum = 0 # Consider all subarrays arr[s...e] for e in range(s, len(arr)): sum += -1 if arr[e] == 0 else 1 # Check if it's a 0-sum subarray if sum == 0: # Update max size res = max(res, e - s + 1) return res if __name__ == "__main__": array = [1, 0, 0, 1, 0, 1, 1] print(maxLen(array)) 

// C# program to find the longest subarray with // equal number of 0s and 1s using nested loop using System; using System.Collections.Generic; class GfG {  static int maxLen(int[] arr) {  int res = 0;  // Pick a starting point as 's'  for (int s = 0; s < arr.Length; s++) {  int sum = 0;  // Consider all subarrays arr[s...e]  for (int e = s; e < arr.Length; e++) {  sum += (arr[e] == 0) ? -1 : 1;  // Check if it's a 0-sum subarray  if (sum == 0)  // Update max size  res = Math.Max(res, e - s + 1);  }  }  return res;  }  static void Main() {  int[] array = { 1, 0, 0, 1, 0, 1, 1 };  Console.WriteLine(maxLen(array));  } } 

// JavaScript program to find the longest subarray with // equal number of 0s and 1s using nested loop function maxLen(arr) {  let res = 0;  // Pick a starting point as 's'  for (let s = 0; s < arr.length; s++) {  let sum = 0;  // Consider all subarrays arr[s...e]  for (let e = s; e < arr.length; e++) {  sum += arr[e] === 0 ? -1 : 1;  // Check if it's a 0-sum subarray  if (sum === 0) {  // Update max size  res = Math.max(res, e - s + 1);  }  }  }  return res; } // driver code let array = [1, 0, 0, 1, 0, 1, 1]; console.log(maxLen(array)); 

6

[Expected Approach] Using Hash Map and Prefix Sum Technique - O(n) Time and O(n) Space

If we consider every 0 as -1, then this problem become same as the longest subarray with 0 sum problem.

We traverse the array and compute the prefix sum

1. If current prefix sum == 0, it means that subarray from index (0) till present index has equal number of 0's and 1's.
2. If we encounter a prefix sum value which we have already encountered before, which means that subarray from the previous index+1 till the present index has equal number of 0's and 1's as they give a cumulative sum of 0.

In a nutshell this problem is equivalent to finding two indexes i & j in arr[], such that prefix sums till i and j are same, and (j - i) is maximum. To store the first occurrence of each unique cumulative sum value we use a hash map where if we get that value again we can find the subarray size and compare it with the maximum size found till now.

// C++ program to find longest subarray with equal  // number of 0's and 1's Using Hashmap and Prefix Sum #include <iostream> #include <vector> #include <unordered_map> using namespace std; int maxLen(vector<int> &arr) {  unordered_map<int, int> mp;  int preSum = 0;   int res = 0;     // Traverse through the given array  for (int i = 0; i < arr.size(); i++) {    // Add current element to sum  // if current element is zero, add -1  preSum += (arr[i] == 0) ? -1 : 1;  // To handle sum = 0 at last index  if (preSum == 0)   res = i + 1;  // If this sum is seen before, then update   // result with maximum  if (mp.find(preSum) != mp.end())  res = max(res, i - mp[preSum]);   // Else put this sum in hash table  else   mp[preSum] = i;  }  return res; } int main() {  vector<int> arr = {1, 0, 0, 1, 0, 1, 1};    cout << maxLen(arr) << endl;  return 0; } 

// Java program to find longest subarray with equal // number of 0's and 1's Using HashMap and Prefix Sum import java.util.HashMap; class GfG {  static int maxLen(int[] arr) {  HashMap<Integer, Integer> mp = new HashMap<>();  int preSum = 0;  int res = 0;  // Traverse through the given array  for (int i = 0; i < arr.length; i++) {  // Add current element to sum  // if current element is zero, add -1  preSum += (arr[i] == 0) ? -1 : 1;  // To handle sum = 0 at last index  if (preSum == 0)  res = i + 1;  // If this sum is seen before, then update   // result with maximum  if (mp.containsKey(preSum))  res = Math.max(res, i - mp.get(preSum));  // Else put this sum in hash table  else  mp.put(preSum, i);  }  return res;  }  public static void main(String[] args) {  int[] arr = {1, 0, 0, 1, 0, 1, 1};  System.out.println(maxLen(arr));  } } 

# Python program to find longest subarray with equal # number of 0's and 1's Using HashMap and Prefix Sum def maxLen(arr): mp = {} preSum = 0 res = 0 # Traverse through the given array for i in range(len(arr)): # Add current element to sum # if current element is zero, add -1 preSum += -1 if arr[i] == 0 else 1 # To handle sum = 0 at last index if preSum == 0: res = i + 1 # If this sum is seen before, then update  # result with maximum if preSum in mp: res = max(res, i - mp[preSum]) # Else put this sum in hash table else: mp[preSum] = i return res if __name__ == "__main__": arr = [1, 0, 0, 1, 0, 1, 1] print(maxLen(arr)) 

// C# program to find longest subarray with equal // number of 0's and 1's Using Dictionary and Prefix Sum using System; using System.Collections.Generic; class GfG {  static int MaxLen(int[] arr) {  Dictionary<int, int> mp = new Dictionary<int, int>();  int preSum = 0;  int res = 0;  // Traverse through the given array  for (int i = 0; i < arr.Length; i++) {  // Add current element to sum  // if current element is zero, add -1  preSum += (arr[i] == 0) ? -1 : 1;  // To handle sum = 0 at last index  if (preSum == 0)  res = i + 1;  // If this sum is seen before, then update   // result with maximum  if (mp.ContainsKey(preSum))  res = Math.Max(res, i - mp[preSum]);  // Else put this sum in hash table  else  mp[preSum] = i;  }  return res;   }  static void Main() {  int[] arr = {1, 0, 0, 1, 0, 1, 1};  Console.WriteLine(MaxLen(arr));  } } 

// JavaScript program to find longest subarray with equal // number of 0's and 1's Using HashMap and Prefix Sum function maxLen(arr) {  let mp = new Map();  let preSum = 0;  let res = 0;  // Traverse through the given array  for (let i = 0; i < arr.length; i++) {  // Add current element to sum  // if current element is zero, add -1  preSum += (arr[i] === 0) ? -1 : 1;  // To handle sum = 0 at last index  if (preSum === 0)  res = i + 1;  // If this sum is seen before, then update   // result with maximum  if (mp.has(preSum))  res = Math.max(res, i - mp.get(preSum));  // Else put this sum in hash table  else  mp.set(preSum, i);  }  return res; } // Driver Code const arr = [1, 0, 0, 1, 0, 1, 1]; console.log(maxLen(arr)); 

6