Hacker Rank is the perfect playground to get your feet wet and build up your algorithms-building skills. The Sock Merchant challenge is one of the fun ones. It might be a bit scary if you have never been presented to problems this way, but I can guarantee you that you are subconsciously solving way more complex ones every day.
John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.
Two Solutions in less than 5mn of video
But if you are more the reading type, a quick explanation and the transcripts are just below to feed your cravings.
Solution 1 — Sort, compare and count pairs
In the first two minutes of the video, I explain the approach of sorting the passed in array first, and looking at each item side by side to find and increment the pair count. The final code produced is below.
And here is a complete transcript of the first segment
Video transcript — segment 1
So one way to solve for the sock merchant challenge is to sort the array, compare each item side by side to find a pair and total the number of pairs we find
So our first step, we will create a variable to hold the sorted array and use the built-in sort method the sort method can take a compare function as an argument. The passed-in compare function will ensure that items are sorted in ascending order
Next, we create a pairs variable which will hold the final count, we default it to 0
At this point, this would be the expected output from sorted if we were to pass in our socks array
Next, we set up a for loop.
We naturally start at index 0 but since we are going to compare items side by side we make a full stop at last index
Now we can compare each item of the array with its direct sibling to
Find a pair
We increment the pair’s value if we find a match. We also increment i
By one to skip the next item since we have already checked it
If the two items do not match the normal loop cycle will continue
We have now sorted and compared side by side let’s run our solution
Solution 2 — Dictionary, stock and count
The second and better performant approach is to create an object on the fly that stores the numbers of times each sock appears using the sock id as key.
When ran on a set of 10,000 items, it outperforms the first solution by a 400% gain in speed. Below is the produced code
And again the video transcript for the second solution at 2mn:15
Video transcript — segment 2
In part 1 we solved the challenge using a sort first and compare approach, let’s clean up and look at an alternative solution.
Using the stockAndCount function, we will create an object that will stock each of our colors as keys.
So we will still create a pairs variable, then we will have a colors variable here but using the reduce method here we will be building up this object as we go.
In the reduce callback we setup an accumulator and the current value — doing this on the fly we check to see if our current value exists as a key in our accumulator object, if so we add one to it if not we create the key and initialize it with 1.
Let’s not forget to add the empty object as the second argument and return the accumulator after each iteration
Let’s make sure the function is properly closed
What we have done above is what I call the Dictionary approach.
Now that we have an object with each color as a key ket’s loop through it.
We iterate through each key and we create a local pair variable. We initialize the pair by dividing the colors n key value by 2
Now we can check if the pair value is greater or at least equal to 1. If true we can increment the total pairs value on line 17 with the number of pairs found
We can then simply return the total count after the loop. Running it in the terminal gives us again 3 pairs — If that went too fast let’s add to our console statement and run it again
I will leave out intentionally the whys the second one is way more performant than the first one and I can assure you that one of you smart folks will come up with yet others that will leave the second in the dust. Please add to the discussion and share in the comments
What is most important and that they have both in common is that though they might seem naive at first, they do work and provide the right answer. Solutions can and will always be improved and refactored, but wrong will never magically turn into right — at least in this tech realm that we live.