Replace each element of the array by its corresponding rank in the array

Given an array of distinct integers, replace each element of the array by its corresponding rank in the array.


 

The minimum element in the array has rank 1, the second minimum element has rank of 2 and so on.. For example,


Input:  { 10, 8, 15, 12, 6, 20, 1 }

Output: { 4, 3, 6, 5, 2, 7, 1 }

 

 
The idea is to store each element’s index in an ordered map (Since the array contains all distinct integers, we can use array elements and their index as key-value pair in the map). Since elements are stored in sorted order in ordered map, if we iterate through the map, we get elements in increasing order. So, for each element in increasing order, we start assigning values to it starting from number 1 till n.

 
Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Output:

4 3 6 5 2 7 1

Java

Download   Run Code

Output:

[4, 3, 6, 5, 2, 7, 1]

 
The time complexity of above solution is O(nlog(n)) (assuming O(log(n)) time operation for std::map/TreeMap) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Tony
Guest
Tony

nice problem with easy soln.

Jarvis
Guest
Jarvis

Elegant solution, thanks!