Construct a BST using ar[], where each node contains the ar index
information as well (in addition to the value).
Now iterating through ar. For each element, traverse the BST by value,
counting only those nodes where the value AND index# are greater then self.
Once done traversal, update ar_low.

-- 



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.

Reply via email to