Similar Problems

Similar Problems not available

Replace each element of an array by its corresponding rank - Leetcode Solution

Companies:

LeetCode:  Replace each element of an array by its corresponding rank Leetcode Solution

Difficulty: Unkown

Topics: hash-table  

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

Replace each element of an array by its corresponding rank Solution Code

1#include <bits/stdc++.h>
2using namespace std;
3
4// Function to replace each element of the array by its rank in the array
5void transform(vector<int>& arr)
6{
7    // create an empty ordered map
8    map<int, int> map;
9
10    // store (element, index) pair in the map
11    for (int i = 0; i < arr.size(); i++)
12        map[arr[i]] = i;
13
14    // keys are stored in sorted order in ordered map
15
16    // rank starts from 1
17    int rank = 1;
18
19    // iterate through the map and replace each element by its rank
20    for (auto i: map)
21        arr[i.second] = rank++;    // i.second stores the index of element i
22}
23
24int main()
25{
26    vector<int> arr = { 10, 8, 15, 12, 6, 20, 1 };
27
28    // transform the array
29    transform(arr);
30
31    // print the transformed array
32    for (int i = 0; i < arr.size(); i++)
33        cout << arr[i] << " ";
34
35    return 0;
36}