Use stack On Tue, Jul 26, 2011 at 5:22 PM, Shikhar <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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" * -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
