Replace each element by its rank in the given array | faceprep

Program to replace each element by its rank in the given array is discussed here.  Given an array of distinct integers, we need to replace each element of the array with its rank. The minimum value element will have the highest rank.

For example, consider the array

  • Input array = {10, 8, 15, 12, 6, 20, 1}
  • Output array = {4, 3, 6, 5, 2, 7, 1}

replace elements by its rank

Algorithm

A solution can be provided using maps. The array element and its index are stored in two columns in the map and later the index is replaced by the element’s rank.

  •  Elements in a map will be stored in sorted order, so on iterating it, the elements will be in an increasing order sequence.
  •  Assign values for each element in increasing order starting from 1 to n, incrementing by 1 for each element.

Program to replace each element by its rank in the given array

// C++ program  to replace each element by its rank in the given array

#include
#include

using namespace std;

void transform(int arr[], int n)
{
map<int, int> map;

for (int i = 0; i < n; i++)
map[arr[i]] = i;

int rank = 1;

for (auto i: map)
arr[i.second] = rank++; // i.second stores the index of element i
}

int main()
{
int n;
cout <<“\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for (int i = 0; i < n; i++)
cin >> arr[i];

// transform the array
transform(arr, n);

cout <<“\nAfter ranking : “;
for (int i = 0; i < n; i++)
cout << arr[i] << ” “;

return 0;
}

// Java program  to replace each element by its rank in the given array

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

class Main
{
public static void transform(int[] arr)
{
Map<Integer, Integer> map = new TreeMap<>();

for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}

int rank = 1;

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
arr[entry.getValue()] = rank++;
}
}

public static void main(String[] args)
{
int[] A = { 10, 8, 15, 12, 6, 20, 1 };

transform(A);

System.out.println(Arrays.toString(A));
}
}

Output:

replace each element by its rank in the array

Time complexity: O(n log n)