@piyush: Just curious, how exactly can a stack be used in this problem? On Jul 26, 5:00 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > 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.
