Given a binary array A[] consisting of 0’s and 1’s. The task is to return the length of the largest subarray which contains an equal number of 0’s and 1’s.
Examples:
Input: A[] =[0, 1]
Output: 2
Explanation: [0, 1] is the longest subarray with equal number of 0 and 1.
Confused about your next job?
Input: A[] = [1, 0, 1, 1, 1, 0, 0]
Output: 6
Explanation: [0, 1, 1, 1, 0, 0] is the longest subarray with equal number of 0s and 1s.
Approach 1: Brute Force
The most naive approach is to simply generate all possible subarrays of the given array. Now, for each subarray, check whether the count of 0’s and 1’s are the same. If true, maximize the length.
C++ Code
int findMaxLength(int nums[], int n) { int maxlen = 0; for (int start = 0; start < n; start++) { int zeroes = 0, ones = 0; for (int end = start; end < n; end++) { if (nums[end] == 0) { zeroes++; } else { ones++; } if (zeroes == ones) { maxlen = max(maxlen, end - start + 1); } } } return maxlen; }
Java Code
public int findMaxLength(int[] nums) { int maxlen = 0; for (int start = 0; start < nums.length; start++) { int zeroes = 0, ones = 0; for (int end = start; end < nums.length; end++) { if (nums[end] == 0) { zeroes++; } else { ones++; } if (zeroes == ones) { maxlen = Math.max(maxlen, end - start + 1); } } } return maxlen; }
Python Code
def findMaxLength(nums): maxlen = 0 for start in range(0, len(nums)): zeroes = 0 ones = 0 for end in range(start, len(nums)): if nums[end] == 0: zeroes += 1 else: ones += 1 if zeroes == ones: maxlen = max(maxlen, end - start + 1) return maxlen
Time Complexity: O(N^2), where N is the size of the array A[]
Space Complexity: O(1), as no extra space is used.
Approach 2: Using HashMap
The idea is to use a hashmap to store the count of 0’s and 1’s. At any moment, when the count of 0s and 1s are the same, maximize the length of the subarray.
Let us understand this approach with an example:
Algorithm:
- Initialise a hashmap.
- Initialise two variables maxLen = 0 and count = 0.
- Traverse through the array and if the current element A[i] is 1, increment the count, else decrement the value of count.
- Now, check if the value of count is already present in the hashmap:
- If True, maximize the length of the subarray obtained so far.
- Else, insert (count, i) in the map.
- Return the value of maximum length obtained.
Implementation of the Approach:
C++ Code
int findMaxLength(int nums[], int n) { map < int, int > map; map.insert({0, -1}); int maxlen = 0, count = 0; for (int i = 0; i < n; i++) { count = count + (nums[i] == 1 ? 1 : -1); if (map.find(count) != map.end()) { maxlen = max(maxlen, i - map.get(count)); } else { map.insert({count, i}); } } return maxlen; }
Java Code
public int findMaxLength(int[] nums) { Map < Integer, Integer > map = new HashMap < > (); map.put(0, -1); int maxlen = 0, count = 0; for (int i = 0; i < nums.length; i++) { count = count + (nums[i] == 1 ? 1 : -1); if (map.containsKey(count)) { maxlen = Math.max(maxlen, i - map.get(count)); } else { map.put(count, i); } } return maxlen; }
Python Code
def findMaxLength(self, nums: List[int]) -> int: count = 0 map = { 0: -1} max_length = 0 for i, number in enumerate( nums ): if number: count += 1 else: count -= 1 if count in map: max_length = max( max_length, ( i - map[count] ) ) else: map[ count ] = i return max_length
Time Complexity: O(N), where N is the size of the array A[]
Space Complexity: O(N), as a map is used
Practice Questions:
FAQ
- How to find the smallest subarray having equal number of 0s and 1s?
Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length.
- What is the time and space complexity of the hashing approach?
The time and space complexity of the hashmap approach is O(N).