title: Count number of identical pairs
body: <p>An identical pair in array are 2 indices <code>p,q</code> such that</p>
  
  <p><code>0&lt;=p&lt;q&lt;N</code> and <code>array[p]=array[q]</code> where <code>N</code> is the length of the array.</p>
  
  <p>Given an unsorted array, find the number identical pairs in the array.</p>
  
  <p>My solution was to sort the array by values,
  keeping track of indices.</p>
  
  <p>Then for every index <code>p</code> in sorted array, count all <code>q&lt;N</code> such that and </p>
  
  <pre><code>sortedarray[p].index &lt; sortedarray[q].index and 
  sortedarray[p] = sortedarray[q]  
  </code></pre>
  
  <p>Is this the correct approach. I think the complexity would be </p>
  
  <pre><code>O(N log N) for sorting based on value  +
  
  O(N^2) for counting the newsorted array that satisfies the condition. 
  </code></pre>
  
  <p>This means I am still looking at <code>O(N^2)</code>. Is there a better way ?</p>
  
  <p>Another thought that came was for every P binary search the sorted array for all Q that satisfies the condition. Would that not reduce the complexity of the second part to <code>O(Nlog(N))</code></p>
  
  <p>Here is my code for second part</p>
  
  <pre><code>    for(int i=0;i&lt;N;i++){
  
                      int j=i+1;
  
              while( j&lt;N &amp;&amp; sortedArray[j].index &gt; sortedArray[i].index &amp;&amp;
                     sortedArray[j].item == sortedArray[i].item){
  
                          inversion++;
                          j++;
              }
        }
     return inversion;
  </code></pre>
  
  <p>@Edit: I think, I mistook the complexity of second part to be <code>O(N^2)</code>.</p>
  
  <p>As in every iteration in while loop, no rescan of elements from indices 0-i occurs, linear time is required for scanning the sorted array to count the inversions. The total complexity is therefore</p>
  
  <p><code>O(NlogN)</code> for sorting and <code>O(N)</code> for linear scan count in sorted array.</p>