title: How to find what is the rank of each element in an integer array
body: <p>I want to find out the rank of each element in an array starting from 0.</p>
  
  <p><strong>For example:</strong></p>
  
  <pre><code>arr = {2, 1,3 } 
  rank will be {1,0 ,2}
  </code></pre>
  
  <p><strong>Explanation:</strong></p>
  
  <pre><code>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
  </code></pre>
  
  <p>What I have tried is <code>n^2</code> time complexity algorithm. I want an algorithm with linear time complexity <code>O(n)</code>.</p>
  
  <p>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.</p>
  
  <p>Thanks to the author </p>
  
  <pre><code>import java.io.IOException;
  import java.io.InputStream;
  import java.util.*;
  
  class rank{
      public static void main(String args[]){
          ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
          list.add(2);
          list.add(1);
          list.add(3);
          ArrayList&lt;Integer&gt; listCopy = new ArrayList&lt;Integer&gt;(list);
  
          Collections.sort(list); // sorting array
           //   System.out.println("List : " + listCopy);
           //  System.out.println("Sorted List : " + list);
  
          Map&lt;Integer, Integer&gt; rankMap = new HashMap&lt;Integer, Integer&gt;();
          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))
      }
  }
  </code></pre>