Largest subarray with equal number of 0s and 1s

PHOTO EMBED

Mon Feb 07 2022 15:51:57 GMT+0000 (UTC)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #hashing

// Efficient : (HASHING Using Prefix Sum) : Time Complexity: O(n), Auxiliary Space: O(n)

class LargestSubArray {

	// This function Prints the starting and ending
	// indexes of the largest subarray with equal
	// number of 0s and 1s. Also returns the size
	// of such subarray.

	int findSubArray(int arr[], int n)
	{
		int sum = 0;
		int maxsize = -1, startindex = 0;
		int endindex = 0;

		// Pick a starting point as i

		for (int i = 0; i < n - 1; i++) {
			sum = (arr[i] == 0) ? -1 : 1;

			// Consider all subarrays starting from i

			for (int j = i + 1; j < n; j++) {
				if (arr[j] == 0)
					sum += -1;
				else
					sum += 1;

				// If this is a 0 sum subarray, then
				// compare it with maximum size subarray
				// calculated so far

				if (sum == 0 && maxsize < j - i + 1) {
					maxsize = j - i + 1;
					startindex = i;
				}
			}
		}
		endindex = startindex + maxsize - 1;
		if (maxsize == -1)
			System.out.println("No such subarray");
		else
			System.out.println(startindex + " to " + endindex);

		return maxsize;
	}

	/* Driver program to test the above functions */

	public static void main(String[] args)
	{
		LargestSubArray sub;
		sub = new LargestSubArray();
		int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
		int size = arr.length;

		sub.findSubArray(arr, size);
	}
}
content_copyCOPY

Given an array containing only 0s and 1s, find the largest subarray which contains equal no of 0s and 1s. The expected time complexity is O(n). Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0} Output: 1 to 6 (Starting and Ending indexes of output subarray) Input: arr[] = {1, 1, 1, 1} Output: No such subarray Input: arr[] = {0, 0, 1, 1, 0} Output: 0 to 3 Or 1 to 4 --------------------------------------------------------------------------------------------------------- Method 2: Hashmap. Approach: The concept of taking cumulative sum, taking 0’s as -1 will help us in optimizing the approach. While taking the cumulative sum, there are two cases when there can be a sub-array with equal number of 0’s and 1’s. When cumulative sum=0, which signifies that sub-array from index (0) till present index has equal number of 0’s and 1’s. When we encounter a cumulative sum value which we have already encountered before, which means that sub-array 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 array[] such that array[i] = array[j] and (j-i) is maximum. To store the first occurrence of each unique cumulative sum value we use a hash_map wherein if we get that value again we can find the sub-array size and compare it with the maximum size found till now. Algorithm : 1.) Let input array be arr[] of size n and max_size be the size of output sub-array. 2.) Create a temporary array sumleft[] of size n. Store the sum of all elements from arr[0] to arr[i] in sumleft[i]. 3.) There are two cases, the output sub-array may start from 0th index or may start from some other index. We will return the max of the values obtained by two cases. 4.) To find the maximum length sub-array starting from 0th index, scan the sumleft[] and find the maximum i where sumleft[i] = 0. 5.) Now, we need to find the subarray where subarray sum is 0 and start index is not 0. This problem is equivalent to finding two indexes i & j in sumleft[] such that sumleft[i] = sumleft[j] and j-i is maximum. To solve this, we create a hash table with size = max-min+1 where min is the minimum value in the sumleft[] and max is the maximum value in the sumleft[]. Hash the leftmost occurrences of all different values in sumleft[]. The size of hash is chosen as max-min+1 because there can be these many different possible values in sumleft[]. Initialize all values in hash as -1. 6.) To fill and use hash[], traverse sumleft[] from 0 to n-1. If a value is not present in hash[], then store its index in hash. If the value is present, then calculate the difference of current index of sumleft[] and previously stored value in hash[]. If this difference is more than maxsize, then update the maxsize. 7.) To handle corner cases (all 1s and all 0s), we initialize maxsize as -1. If the maxsize remains -1, then print there is no such subarray.

https://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/