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 <kujurismonu2...@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.