Largest subarray of 0's and 1's

Largest subarray of 0's and 1's

  June 16, 2018    

---

Problem
Given an array of 0's and 1's , give  size of  the  largest sub array with equal number of 0's and 1's .

Idea to change array to -1 and 1 and now problem changes to maximum subarray having sum 0.
Use a map to store least index for every sum and when we encounter same sum again it means that from that index (stored in map) to i (current) we have a subarray with sum 0.

Code

void manipulate(int a[])
    {
        for(int i=0;i<a.length;++i)
        {
            if(a[i]==0)
            a[i]=-1;
        }
    }
    int maxLen(int[] a)
    {
        manipulate(a);
         Map<Integer,Integer> m=new HashMap<>();
         int maxLen=0;
         int cursum=0;
         for(int i=0;i<a.length;++i)
         {
             cursum+=a[i];
             if(m.containsKey(cursum))
             {
                 maxLen=Math.max(maxLen,i-m.get(cursum));
             }
             else if(cursum==0)
             maxLen=i+1;
             else
             m.put(cursum,i);
         }
        // System.out.print(m+" "+cursum);
         return maxLen;
    }