Can we find rank of each element in array with Linear Time Complexity O(n)?

Question

I am trying to solve this Leetcode problem, where it is asked to solve:

Given an array of integers arr, replace each element with its rank. For example:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

My code is as follows:

    class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        multimap<int, int> numbeToIndexrMap;
        int size = arr.size();
        vector<int> rank(size, 10);
        for(int i = 0; i < size; ++i){
            numbeToIndexrMap.insert({arr[i], i});
        }
        int rankIndex = 1;
        int previous = INT_MIN;
        for(auto i = numbeToIndexrMap.begin(); i != numbeToIndexrMap.end(); ){
            int currentNumber = i -> first;
            rank[i->second] = rankIndex;
            ++i;
            if(i != numbeToIndexrMap.end() && i -> first != currentNumber) ++rankIndex;
        }
        return rank;
    }
};

I found that we may use Sorting/Map to solve this problem with time complexity of O(NlogN). My question is whether we can do this on linear time O(n)?

Answer 1

Even in the hint section of that problem, they expect us to sort the array which will itself take time complexity of O(nlog(n)). Here, sorting is not important but necessary part of solution. So the thing that makes difference is how you search the rank from that sorted array. Naive approach will be to find index of each element of the original array in the sorted array using linear search O(n). So overall time complexity would be O(n*n). Best approach would be to find index of each element of original array in the sorted array using binary search O(log(n)). So the overall time complexity would be O(n*log(n)).