I guess a <O(nk),O(k)> solution exists. Have a maxHeap of k elements in our case its 3.
Iterate through the array, compare the (difference between the position along a number line between ) and the top element of the maxHeap. It it happens to be lesser than the top element, pop off the top element and push the current element into the maxHeap. Proceeding till the end of the array we will be getting the 3 friends of a given person. Hope I am not wrong. Thanks, Immanuel On Thu, May 19, 2011 at 7:33 PM, Dave <dave_and_da...@juno.com> wrote: > @Sravanreddy001: You are to find _each_ person's friends. Can you do > that in O(n)? > > Dave > > On May 19, 8:59 am, sravanreddy001 <sravanreddy...@gmail.com> wrote: > > Also, I think there is no need for sorting the number, its still okey if > the > > 3rd person is standing 1st and has the lowest number line value. > > > > And, finding the closest 3 number takes, 3*n time.. so.. its O(n) running > > time.. > > > > @Dave.. good catch.. :) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
