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.
