Amazon Question: An array is containing only 0 and 1. Find out the largest subarray in which number of 1s are equal to number of 0s.

Solution: 

1. Replace 0 with -1.
2. Find the cumulative sum at each index.
3. In the cumulative sum array if at some index sum is 0 that means from index 0 to current index number of 0 and 1 are same.
4. If there are duplicates in the cumulative sum array that means the cumulative sum is 0 in between so there are equal number of 0s and 1s.
5. Just find out the longest one and return it.

Source Code:

string longestSubStrWithEqual0and1(int *arr, int size)
{
    string strResult = "";
    map<int, int> mapIntToInt;
    if(arr == NULL || size == 0)
        return strResult;
    int i=1;
    int* cumSumArr = new int[size];
    if(arr[0] == 1)
        cumSumArr[0] = 1;
    else if(arr[0] == 0)
        cumSumArr[0] = -1;
    else
        return strResult; // Error as there is interger other than 0 and 1 in array
    for(; i<size; ++i)
    {
        if(arr[i] == 0)
            cumSumArr[i] = cumSumArr[i-1] + (-1);
        else if(arr[i] == 1)
            cumSumArr[i] = cumSumArr[i-1] + 1;
        else
            return strResult; // Error as there is interger other than 0 and 1 in array
    }
   
    int maxLen =0;
    int startIndex = 0;
    int endIndex = 0;
    for(i=0; i<size; ++i)
    {
        if(mapIntToInt.find(cumSumArr[i]) == mapIntToInt.end())
        {
            mapIntToInt[cumSumArr[i]] = i;
        }
        else
        {
            int len = i - mapIntToInt[cumSumArr[i]];
            if(maxLen < len)
            {
                maxLen = len;
                startIndex = mapIntToInt[cumSumArr[i]] + 1;
                endIndex = i;
            }
        }
        if(cumSumArr[i] == 0)
        {
            maxLen = i + 1;
            startIndex = 0;
            endIndex = i;
        }
       
    }
    if(maxLen > 0)
    {
        for(i = startIndex; i <= endIndex; ++i)
        {
            strResult += ('0' + arr[i]);         }
    }
    delete [] cumSumArr;
    return strResult;
}