Sorry for the above mistake....its not O(n) On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
> Use stack > > > On Tue, Jul 26, 2011 at 5:22 PM, Shikhar <shikharko...@gmail.com> wrote: > >> Given an array of integers, for each element of the array, print the >> first number on the right side of the element which is smaller than >> it. print -1 is there is no such element. >> >> eg: 3,4,2,18,19,1,10 >> >> Ans: 2,2,1,10,10,-1,-1 >> O(n^2) solution is trivial. >> >> One solution could be: >> Insert the elements of the array in a binary search tree. The moment a >> node in the binary tree gets a left child, it is the element we are >> looking for. All the nodes in the right subtree of a node which has >> just received a left child can be assigned the value of the parents' >> left child as the first smaller element to the right. >> Thus, this solution is O(nlogn). >> >> Does this solution work for all possible cases of input? >> >> Is an O(n) solution possible? >> >> -- >> 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. >> >> > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-7483122727* > * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY > NEVER" > * > > -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY NEVER" * -- 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.
