Largest subarray with equal number of 0s and 1s

You are given an array of integers. The integers are only 0 and 1 in the input array. The problem statement asks to find out the largest sub-array that can have equal count of 0s and 1s.

Table of Contents

Example

arr[]={0,1,0,1,0,1,1,1}

0 to 5 (total 6 elements)

Explanation

From the array position 0 to 5 there was equal no of 0s and 1s

0s count ⇒ 3

1s count ⇒ 3

And this is the largest sub-array that holds equal no 0s and 1s.

Algorithm to find Largest subarray with equal number of 0s and 1s

Declare a HashMap.
Set sum, maxLength, startingIndex to 0 and endingIndex to -1.
Traverse the array and update each element of the array as -1 if it is equal to 0.
Start loop from 0 to n-1(n is the length of the array).
1. Add each value of arr[i] to sum.
2. Check if the sum is equal to 0, if true,
  1. Then update maxLength as i+1, and endingIndex as i.
3. Check if the map contains the sum+n in it,
  1. Then update the length of maxLength as value i – map (sum+n )from the map and endingIndex as i.
4. Else put that sum+n into the map.
Print endingIndex – maxLength + 1 and endingIndex.

Explanation

Given an array and we are asked to find out the largest sub-array with an equal number of 0s and 1s. Find the range of the sub-array so that it should be the largest among all lengths of all sub-arrays which holds an equal number of 0s and 1s. We will be using the HashMap for storing the integer values in it. Hashing provides an efficient approach and better time complexity. Take the values sum, maxLength as 0 then we are going to update it simultaneously in the code. We will have one variable called endingIndex, this will hold the value of the last point of the range where should be the maximum length of the range of sub-array ends.

Traverse the array, to find if any of the value of the array is equal to 0, then we will be marking it as -1, and leave the array value which holds the 1 in it as it is. Because here we are not going to find out the actual range. The logic is to count equal no of zeroes and ones meaning even length range. So we will be marking the 0 as -1, and when we add the values within the array. If we find the sum as 0, it means we have found one pair of equal ones and zeroes, because every -1 and 1 make 0 as a sum since we marked each 0 as -1, so we can count that.

We are going, to sum up, every value in an array, and find if it is equal to 0, if equal just update the maxLength of the array and endingIndex of the array. We are going to put the sum+n into the map if it not already exist, and if it exists then check some conditions then update the value of maxLength and endingIndex. Print endingIndex – maxLength + 1 as a starting point of the range and endingIndex as the ending point of the range.

Largest subarray with equal number of 0s and 1s

Code

C++ code to find Largest subarray with equal number of 0s and 1s

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

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

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}

0 to 5

Implementation in Java to find Largest subarray with equal number of 0s and 1s

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

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

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}

0 to 5

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Here we can solve this problem in O(n) because we have used HashMap. Because HashMap can insert, delete or modify elements in O(1) time complexity.

Space Complexity

O(n) where “n” is the number of elements in the array. Since the number of elements that will be inserted in the worst-case into hashmap will be at most n. This linear space complexity is achieved.