The binary search trees can be used ...arrange the given elements in binary search tree ...search for each element in the tree ....count the number of nodes along its left successors until the leaf node is reached ...!! thats the ans !!
On Jul 26, 6:53 pm, Someshwar Chandrasekaran <[email protected]> wrote: > 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. > > A straight forward question > for i in 0 to n-1: > temp = 0; > for j in i+1 to n-1: > if arr[j]<= arr[i]: > temp++; > ar_low[i] = temp > > But the trick is to find a better algorithm with better complexity > > Regards, > B.C.Someshwar > > -- > 'Talk sense to a fool and he calls you foolish.' - Euripides > > My Blog: somsekaran.wordpress.com -- 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.
