Short Problem Definition:
Sherlock is given an array of N integers A0, A1 … AN-1 by Watson. Now Watson asks Sherlock how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.
That is, Sherlock has to count total number of pairs of indices (i, j) where Ai = Aj AND i ≠ j.
time complexity is O(n)
space complexity is O(n)
The first step is to create a count of all integers. Next there are choose(k,2)*2 distinct pairs for each integer count (this step similar to Handshake, but you count i,j and j,i as two distinct pairs). Count those together and you arrive at the answer.