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.

Answer 2

at first sort all element and store in a another array (if elements is unsorted) then print element index from that array .

Answer 3

Use radix sort to sort your array in linear time. Each element will be in its own rank.

Answer 4

I give an idea. If you want, you can use this:

It's applicable if array value[0....n-1]

1. Firstly create a count_array from input array by counting sort technique( Ex: array = {2, 1, 3}, So count_array = { 0,1,1,1} // here array value use as count_array index value).
2. Then you can filter count_array like result_array = {0, 1, 2, 3} // you only add 1 with previous added value if count_array[i] == 1 (you can also do that in count_array. I use result _array for just understanding)
3. Then you make a rank_array from result_array By rank_array[i] = result_array[array[i]] - 1
4. Finally you can find your rank_array with O(n)

Example:

array = {2,1,3} 
count_array = {0,1,1,1}
result_array = {0,1,2,3}
rank_array = {1,0,2} //rank_array[i] = result_array[array[i]] - 1

Answer 5

in java 8, first array to list, then to stream. because of only one loop in stream, it should be O(n).

Integer[] arr = {2, 1,3 };
List <Integer> list = Arrays.asList(arr);
Integer[] outArr  = list.stream()
        .sorted()
        .map(e -> list.indexOf(e))
        .toArray(Integer[]::new);

result:{1,0,2}

Answer 6

You can use a map to map the index in the array to the value, sort on the values and return the indexes. It could look like this:

private static int[] ranks(int[] array) {
  Map<Integer, Integer> m = new HashMap<> ();
  for (int i = 0; i < array.length; i++) {
    m.put(i, array[i]);
  }
  return m.entrySet().stream()
                  .sorted(Entry.comparingByValue())
                  .mapToInt(Entry::getKey)
                  .toArray();
}

Example usage:

int[] ranks = ranks(new int[] { 2, 1, 3 });
System.out.println(Arrays.toString(ranks)); //outputs {1, 0, 2}

Answer 7

It is possible to compute this rank using a data structure called "Order statistic tree", it is a augmented data structure. In order to implement this structure you must implement a balanced binary tree (e.g. AVL-Tree or Red-Black Tree) and you add an additional attribute to each node. This is a very efficient way to compute ranks because it takes O(lg n) (where lg is base 2 logarithm) for each element. You can find more information about this data structure in "Introduction to Algorithms" in Chapter 14.

The problem with the sorting is that its running time is O(nlog(n)) and I think that it is inefficient if you want to rank few elements (i.e. less than n elements).