# 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. Therefore for each element in increasing order, we start assigning values starting from number 1 till n.

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

Output:

4 3 6 5 2 7 1

## Java

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).

We have also use Heap to solve this problem. The idea remains similar to the previous approach but here we store array elements and their index as key-value pair in a Max Heap. The major benefit of using max-heap is that if we remove pairs from it, we get elements in decreasing order. Therefore for each element in decreasing order, we start assigning values starting from number n till 1. Note that min heap can also be used.

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

Output:

4 3 6 5 2 7 1

## Java

Output:

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

The time complexity of above solution remains same as previous approach i.e. O(nlog(n)). The auxiliary space used by the program is also O(n).

Exercise: Convert the above solution to use min-heap.     (2 votes, average: 5.00 out of 5) Loading...

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 🙂 Subscribe
Notify of Guest

nice problem with easy soln. Guest

Elegant solution, thanks! Guest
Tamara Vasylenko

Use Priority queue