Hackerrank Solution: Sock Merchant (a more optimal solution)

Problem Link 

Solution Link

Link to previous less efficient solution

Algorithm : linear array mapping

Explanation:
It is a programming problem for beginners. The problem is about array manipulation. In many array related programming problems array mapping of integers is used to keep track of the frequencies of the elements in the array of a test case. This helps reduce runtime like it does for the current challenge. In many problems of character arrays, this technique is also used to keep keep track of the frequencies of alphabets.

In this problem the range of element value is from 1 to 100. So we initialized a frequency array of 100 elements with 0 because we have not counted any element yet.

Then we traverse the given array and use the elements as indices in frequency array. We increment an element in the frequency array using the elements as indices until we reach the end of given array.
So now the frequency array holds the information of the number of distinct values in the given array.
Next we traverse the whole frequency array and if it is not 0 (the index is present as an element in the given array) we divide the value by 2 to determine the number of pairs of that value and add it to our answer.

Runtime : O(n) (due to traversing a one-dimensional array)
Required Space : O(n) (Using one dimension array)