@ ankit agarwal, you are right. thanx man.
On Oct 13, 11:37 am, prodigy <1abhishekshu...@gmail.com> 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 <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.
