How to find what is the rank of each element in an integer array

Question

I want to find out the rank of each element in an array starting from 0.

For example:

arr = {2, 1,3 } 
rank will be {1,0 ,2}

Explanation:

rank of 2 is 1 because 2 is greater than exactly 1 element
rank of 1 is 0 because 1 is greater than exactly  0  element
rank of 3 is 2 because 1 is greater than exactly  2  element

What I have tried is n^2 time complexity algorithm. I want an algorithm with linear time complexity O(n).

Someone gave me solution for it in the comment section below but his comment has been deleted I don't know how. Which is correctly working for negative integers and positive integers as well as very large size of list.

Thanks to the author

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

class rank{
    public static void main(String args[]){
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(2);
        list.add(1);
        list.add(3);
        ArrayList<Integer> listCopy = new ArrayList<Integer>(list);

        Collections.sort(list); // sorting array
         //   System.out.println("List : " + listCopy);
         //  System.out.println("Sorted List : " + list);

        Map<Integer, Integer> rankMap = new HashMap<Integer, Integer>();
        int counter = 0;
        for(int x : list) {
            rankMap.put(x, counter); 
            // list value as key and rank as  value.
            counter++;
        }
        StringBuffer sb=new StringBuffer();
        for(int x : listCopy) {
            sb.append(rankMap.get(x) + " "); 
            // System.out.println(map.get(x));
        }
        System.out.println( sb.toString().substring(0, sb.length()-1))
    }
}

Answer 1

So with rank you mean the position where this element would end up after sorting the array?

You can start with a identity mapping map = {0,1,2} and then sort that, but using your arr as sort key.

Collections.sort(map, (c1, c2) -> arr[c2] > arr[c1] ? +1 : arr[c2] == arr[c1] ? 0 : -1);

This way you won't change your original array, but get a mapping from your array elements to its rank.

Obviously this algorithm depends on the complexity of your sort algorithm. You should end up with O(n log n) but maybe your data allows to use sorting algorithms with O(n) complexity. But that really depends on what you store in your big list.