It is nothing but a common subsequence problem...isnt it ? On Wed, Oct 13, 2010 at 3:42 PM, Mridul Malpani <[email protected]>wrote:
> @ ankit agarwal, you are right. thanx man. > > On Oct 13, 11:37 am, prodigy <[email protected]> wrote: > > Let I,Q be input array,query array respectively. > > > > 1. Sort query array. O(klogk) > > 2. Allocate an array A of size N. > > 3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in > > I. O(nlogk) > > 4. Allocate an array B of size k with all elements initiated to -1. > > 5. for(counter=0,i=0,counter<n,i++) > > { > > if(B[i]==-1) > > counter++; > > if(A[i]!=-1) > > B[A[i]] = i > > } > > 6. Build min-heap of B.(use an auxiliary array C to keep track of > > position of last occurence of an element of Q in min-heap B.) > > 7. for(diff=i-B[1] ; i<n; i++) > > if(A[i]!=-1) > > B[C[A[i]] = i > > //percolate up or down if needed > > diff=max(diff,i-B[1]); > > > > 8. print diff > > > > On Oct 7, 1:20 pm, RAHUL KUJUR <[email protected]> wrote: > > > > > > > > > @prodigy: how is it coming O(nlogk) can u explain??? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
