Find the surpasser count for each element of an array

Given an array of integers having distinct elements, find the surpasser count for each element in it. In other words, for each element of the array, find the number of elements to its right which are greater than it.


 

For example,


Input:  { 4, 6, 3, 9, 7, 10 }

Output: { 4, 3, 3, 1, 1, 0 }

 

The simple solution would be for each element of the array, we count all elements greater than it to its right. The implementation of this approach can be seen here, which runs in O(n2) time.

 
We can reduce the time complexity to O(nlogn) by using Merge Sort Algorithm. The problem is similar to finding inversion count of the array. Since surpasser is just the opposite of inversion, we sort the array in descending order and maintain a map to store the surpasser count for each distinct element of the array.

C++

Download   Run Code

Output:

4 3 3 1 1 0

Java

Download   Run Code

Output:

4 3 3 1 1 null

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of