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.
