Karl Max Karl Max - 3 months ago 9
C Question

How to find number of elements greater/smaller than an element in an array?

I want to find the fastest way to find the number of elements which are smaller/greater than each element in an array.

For example : Array is [5, 6, 8, 2, 4]. Considering first element, no of elements smaller than it is 2.

The best I could make myself was that each element be compared with the rest of the array elements but it takes a long time for large arrays with number of entries approx 10^5.

My code:

for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if( i!=j && (ar[i]>ar[j]) )
{
count++;
}
}
printf("%lld ",count);
}


Edit: I want to display the number of elements smaller than each array element. That is for the above example, I want the answer to be : 2 3 4 0 1
And the array can contain repeated values.

Answer

A simple approach will be:

  1. Sort the array first, possibly using qsort()
  2. Perform a binary search on the sorted array.
  3. Calculate the remaining elements from the desired elements, based on the size of the array.
Comments