Finding the largest subarray with equal number of 0's and 1's

Question

So, I have an array containing only 0's and 1's. I have to find out the largest subarray containing equal number of 0's and 1's. One can be a naive approach have complexity as O(n^2) where I take every element in outer loop and calculate possible subarrays in the inner loop and keep updating the maximum size, if found. Is there any other better approach (something like O(n)) that I can use? Thanks!

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

Answer 1

What is the Solution ?

So, In this solution, it would consider all subarrays and for each subarray, it'll count the total number of 0's and 1's present. If the subarray contains an equal number of both (0's and 1's) then update the largest array if required. Time Complexity for this solution is O(n^3) as there are n^2 subarrays in array size of n, and it will take O(n) to find count 0's and 1's. Here, we can optimize the method to run O(n^2) by calculating the count of 0's and 1's within constant time.

How can We Solve this?

Here, We can use the map to solve it in linear time. Idea is to replace 0 with -1 and find out the largest subarray with the sum of 0.

So to find the Largest Subarray, create an empty map that will stores the first subarray's ending having a given sum. Then traverse the given array and maintain the sum in elements.

• If the sum is seen for 1st time then enter the sum with the index in the map.
• If the sum is seen before, there exists a subarray with a sum of 0, which ends at the current index, and update the largest subarray if the current subarray has more length.

class Solution {
    // Function to find the largest subarray having an equal number
    // of 0's and 1's
    public static void findLargestSubarray(int[] nums)
    {
        // create an empty `HashMap` to store the ending index of the first
        // subarray having some sum
        Map<Integer, Integer> map = new HashMap<>();
 
        // insert (0, -1) pair into the set to handle the case when a
        // subarray with zero-sum starts from index 0
        map.put(0, -1);
 
        // `len` stores the maximum length of subarray with zero-sum
        int len = 0;
 
        // stores ending index of the largest subarray having zero-sum
        int end_index = -1;
 
        int sum = 0;
 
        // Traverse through the given array
        for (int i = 0; i < nums.length; i++)
        {
            // sum of elements so far (replace 0 with -1)
            sum += (nums[i] == 0)? -1: 1;
 
            // if the sum is seen before
            if (map.containsKey(sum))
            {
                // update length and ending index of largest subarray having zero-sum
                if (len < i - map.get(sum))
                {
                    len = i - map.get(sum);
                    end_index = i;
                }
            }
            // if the sum is seen for the first time, insert the sum with its
            // index into the map
            else {
                map.put(sum, i);
            }
        }
 
        // print the subarray if present
        if (end_index != -1)
        {
            System.out.println("[" + (end_index - len + 1) + ", " +
                                    end_index + "]");
        }
        else {
            System.out.println("No subarray exists");
        }
    }

Time Complexity : O(n) and requires O(n) extra space, where n is the size of the input.

Answer 2

Here's an O(n)-time, O(n)-space algorithm. I'm not sure it's optimal, but it beats quadratic time.

The basic idea is the following. Suppose that you scan from the left of the array to the right recording, at each step, the difference between the number of 1s and the number of 0s. If you write these values out at each step, you'll get something like this:

  1,   0,   1,    0,    0,   0,   0
0,   1,   0,   1,    0,    -1,  -2,  -3

If you have a sub array with the same number of 0s and 1s, then the net difference of 0s and 1s at the start of the subarray will equal the net number after the subarray. Therefore, this problem can be reframed as trying to find two equal values in the auxiliary array that are equal and as far apart as possible.

The good news is that every entry in the array is between -n and +n, so you can make a 2n+1 element table and store in it the indices of the first and last time each number appears. From there, it's easy to find the longest range. Overall, this needs O(n) space and everything can be populated and searched in O(n) time.

Hope this helps!