// sort ar[] and store in temp[] -- o(nlogn) for(i=0 to n-1) { //search position of ar[i] in temp[] binary search --o(logn) ar_low[i] = pos-1; delete temp[pos]; }
in binary search increase pos until next element is same . On Tue, Jul 13, 2010 at 4:09 PM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > make a balanced bst which also has the size of subtree at each node > start from ar[n-1] and insert each element and see what is it's rank in BST > for finding the rank when inserting each time you pick the right subtree > add size of left subtree to rank > O(nlogn) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.