Replace each element of an array by its corresponding rank

Companies:
  • Adobe Interview Questions
  • Apple Interview Questions

Given an array of n elements, replace each element of the array by its corresponding rank. The rank of the lowest element is 1 and the highest element is n. Take a look at the example given below:

Input   :  2, 5, 3, 7, 6
Output:  1, 3,  2, 5, 4
Explanation: Since 2 is the smallest element in the array, its rank is 1, 3 is the second smallest element its rank is 2 and so on.     

Solution

The easiest way to solve this problem would be to iterate over the array and store the elements in a sorted map. The map would contain the element as key and the index of the element as the value.

Once we are done iterating over the array, we can just iterate over the sorted map. This will give us all the elements present in the sorted map in ascending order and we can fill up the rank of each element

Solution Implementation

#include <bits/stdc++.h>
using namespace std;

// Function to replace each element of the array by its rank in the array
void transform(vector<int>& arr)
{
    // create an empty ordered map
    map<int, int> map;

    // store (element, index) pair in the map
    for (int i = 0; i < arr.size(); i++)
        map[arr[i]] = i;

    // keys are stored in sorted order in ordered map

    // rank starts from 1
    int rank = 1;

    // iterate through the map and replace each element by its rank
    for (auto i: map)
        arr[i.second] = rank++;	// i.second stores the index of element i
}

int main()
{
    vector<int> arr = { 10, 8, 15, 12, 6, 20, 1 };

    // transform the array
    transform(arr);

    // print the transformed array
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    return 0;
}

 

Scroll to Top