How to Solve HackerRanks’s Sock Merchant Problem in JavaScript

My favorite way to solve algorithms is by performing these steps:

1. Draw it out; and do it manually as a human would
2. Take those steps, and write it out, or pseudo code it into steps
3. THEN begin translating that into code.

Let’s take that approach to solve a recent problem I encountered on HackerRank while studying for upcoming technical interviews: The Sock Merchant.

The problem states that 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.

For example, there are n = 7 socks with colors ar=[1,2,1,2,1,3,2] . There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

I think the key here is to recognize two things going on:

1. There’s a bit of math happening, since I can only count a pair as 2
2. There’s a bit of counting, or track keeping happening. I have to keep track of how many pairs I find.

How do we do this with code?

SPOILER ALERT — SOLUTION BELOW!

function sockMerchant(n, ar) {
  let socks = {};
  let pairs = 0;
for (let element of ar) {
  socks[element] = socks[element] + 1 || 1;
    if (socks[element] % 2 === 0) {
      pairs += 1;
    }
  }
return pairs;
}

First we create a couple of variables to keep count how many socks of each kind we find, and how many pairs there are. Just like folding clothes. That’s what these lines of code do:

let socks = {};
let pairs = 0;

Consider the socks object, or hash map, as our folding table. We’re going to take a sock one at a time. And as we take this sock, if we’re seeing that particular sock (in our case, number) for the first time, we’ll place it on the table by itself. If we’ve seen it before, we’ll put it next to the sock of the same kind. That’s what these lines of code do:

socks[element] = socks[element] + 1 || 1;

This means that the value of a given element in the sock object is going to equal that same value plus 1 (assuming I’ve seen it before) or 1 (assuming it’s the first time I see it). So in the end, we should have an object that looks like this:

socks = {
1: 3, 
2: 3, 
3: 1
}

This way of creating maps is very useful for when you need to keep track of how many things of what there are for a given problem.

Now, we should only count those socks (numbers) that are pairs, or divisible by 2. That’s what the modulo or remainder operator, and these lines do:

if (socks[element] % 2 === 0) {
pairs += 1;
}

This means if the value of the key in that object gives me a remainder of 0 when I divide it by 2, then I want to add it to my pairs count.

And because we’re building and counting, one sock at a time as we build the sock map, and as we add more socks to it, we increment our pairs counter whenever we see an even number. By the end, the pairs variable will have all our matched socks.

We just need to remember to return it :-)

Thanks for reading!

And remember: grit > talent.