Rank Transform of an Array Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Facebook Google
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 3919

The problem Rank Transform of an Array Leetcode Solution provided us with an array of integers. The array or the given sequence is unsorted. We need to assign ranks to each integer in the given sequence. There are some restriction s for assigning the ranks.

  1. The ranks must start with 1.
  2. The larger the number, the higher the rank (larger in numeric terms).
  3. Ranks must be as small as possible for each integer.

Rank Transform of an Array Leetcode Solution

So, let’s take a look at a few examples.

arr = [40,10,20,30]
[4,1,2,3]

Explanation: It will be easier to understand the example if we sort the given input. After sorting, the input becomes [10, 20, 30, 40]. Now if we follow the given rules. The ranks will be [1, 2, 3, 4] as per the new modified array. If we match the elements in the output. They are the same, confirming the correctness of the output.

[100,100,100]
[1, 1, 1]

Explanation: Since all the elements in the input are the same. Thus all must have the same rank that is 1. Hence the output contains three instances of 1.

Approach for Rank Transform of an Array Leetcode Solution

The problem Rank Transform of an Array Leetcode Solution asked us to assign ranks to the given sequence. The conditions that are to be met are already stated in the problem description. So, instead of describing them once again. We will go through the solution directly. So, as seen in the example. It’s easier to assign ranks to a sorted sequence. So, we use an ordered map to store the elements in the given input sequence. Using an ordered map makes sure that the elements are in sorted order.

Now, we must deal with the third condition. The third condition states that we must assign the smallest ranks as much as possible. So, we simply assign numbers from 1 to the keys present on the map. This takes care of all three imposed conditions. The rank of larger numbers is higher. The ranks start from 1. They are as small as possible.

Now, we simply traverse through the input sequence and assign the ranks stored in the map.

Code

C++ code for Rank Transform of an Array Leetcode Solution

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

vector<int> arrayRankTransform(vector<int>& arr) {
    map<int, int> m;
    for(auto x: arr)
        m[x] = 1;
    int lst = 0;
    for(auto x: m){
        m[x.first] = lst + 1;
        lst++;
    }
    for(int i=0;i<arr.size();i++)
        arr[i] = m[arr[i]];
    return arr;
}

int main(){
    vector<int> input = {40, 10, 30, 20};
    vector<int> output = arrayRankTransform(input);
    for(auto x: input)
        cout<<x<<" ";
}

4 1 3 2

Java code Rank Transform of an Array Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int[] arrayRankTransform(int[] arr) {
        Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
        for(int x: arr)
            m.put(x, 1);
        int lst = 0;
        for(Integer x: m.keySet()){
            m.put(x, lst + m.get(x));
            lst = m.get(x);
        }
        for(int i=0;i<arr.length;i++)
            arr[i] = m.get(arr[i]);
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] input = {40, 10, 30, 20};
    int[] output = arrayRankTransform(input);
    for(int x: output)
      System.out.print(x+" ");
  }
}
4 1 3 2

Complexity Analysis

Time Complexity

O(NlogN), since we used an ordered map we have the logarithmic factor for insertion, deletion, and searching.

Space Complexity

O(N), because we use an ordered map to store the elements in the input.

Translate »