We must use BIT<http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees>to solve this problem with O(nlogn).
Here <http://ideone.com/IaU3F> is my implementation. Thanks & Regards Anantha Krishnan On Tue, Jul 26, 2011 at 7:18 PM, Piyush Sinha <[email protected]>wrote: > You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create > another array ar_low[] such that ar_low[i] = number of elements lower > than or equal to ar[i] in ar[i+1:n-1]. > So the output of above should be {0,2,1,2,2,1,0} > > Time complexity : O(nlogn) > use of extra space allowed. > > > -- > *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. > -- 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.
