Find Largest Subarray with Equal Number of 0 and 1

• Write a program to find biggest sub-array having equal number of 0 and 1.

Given an array of size N which contains only 0 and 1. We have to find largest sub array containing equal number of 0 and 1.
For Example :
Input Array : 0 1 1 0 1 0, 0 1 1 1
Output : From index 0 to 7

---

Algorithm to find biggest sub array having equal number of 0 and 1
Let inputArray be an integer array of size N containing only 0 and 1.

• Outer for loop will fix one element(let it be K) and then inner for loop will find the sum of all sub arrays starting from K.
• While calculating sum of elements of a sub array add -1 if current element is 0 and 1 if current element is 1.
• At any time, if current sum becomes zero, then we found one sub array from K to current element which contains equal number of 0 and 1.

Time Complexity : O(n²)

---

C program to find largest sub array having equal count of 0 and 1

#include <stdio.h>
#include <limits.h>

void findMaxSubArray(int *array, int size) {
    int i, j, sum = 0, maxSize = INT_MIN, left;
    
    /* For every element array[i], find the sum of 
 all sub array starting form array[i] */
    for(i = 0; i < size-1; i++) {
     /* Here we are changing 0 to -1 */
        sum = array[i] ? 1 : -1;
        for (j = i+1; j < size; j++) {
            if (array[j] == 1)
                sum += 1;
            else 
                sum += -1;
            /* If sum is 0, that means we got equal numbers 
            of 0 and 1. Compare it with current maximum size */
            if (sum == 0 && (maxSize < j - i + 1)) {
                maxSize = j - i + 1;
                left = i;
            }
        }
    }
    
    if (maxSize == INT_MIN) {
        printf("SubArray Not Found");
    } else {
     printf("Sub Array from index %d to %d", left, left+maxSize-1);
    }
}

int main(){
    int i, array[10] = {0, 1, 1, 0, 1, 0, 0, 1, 1, 1}; 
    
    findMaxSubArray(array, 10);

    return 0;
}

Output

Sub Array from index 0 to 7