Largest Span between 2 arrays

[Vinay96]

Given two arrays of numbers a1,…,an and b1,…,bn where each number is 0 or 1, the fastest algorithm to find the largest span (i,j) such that a[i]+a[i+1]+⋯+a[j]=b[i]+b[i+1]+⋯+b[j] or report that there is no such span,

(i)Takes 0(3^n) and Ω(2^n) time if hashing is permitted
(ii)Takes 0(n^3) and Ω(n^2.5) time in the key comparison mode
(iii)Takes Θ(n) time and space
(iv)Takes O(√n) time only if the sum of the 2n elements is an even number

[Ruturaj]

Ans is option (iii).

Here we are having difference from -n to n so there are 2n+1 possibility of diff.
We are having 2 cases :

1: if index 0 to n is maxLength
2: any subarray having maxLength

For this we are maintaining a diff array and checking if sum in both array is equal then change maxLength.

 public static int longestSpan(int arr[],int n,int arr2[])
     {
         int diff[]=new int[2*n+1];
         int maxLen=0,pre1=0,pre2=0;
         Arrays.fill(diff,-1);
         for(int i=0;i<n;++i)
         {
             pre1+=arr[i];
             pre2+=arr2[i];
             int cdiff=pre1-pre2;
//index finded by adding n as max neg val is -n
             int diffindex=n+cdiff;
//from 0 to i
             if(cdiff==0)
             {
                 maxLen=i+1;
             }
             else if(diff[diffindex]==-1)
             {
              diff[diffindex]=i;   
             }
             else
             {
                 maxLen=Math.max(maxLen,i-diff[diffindex]);
             }
         }
         return maxLen;
     }