Javascript Sock Merchant Challenge - Solution 1

READ FIRST: As noted in the comments and on the twitter thread, the solution in part 1 is not necessarily a performant one. A second solution will be shared in the second part and is usually more optimized for these types of challenges.

A quick preface

Truth be told I'm not a fan at all of algorithm code challenges. That might be surprising to hear from someone who's putting up a tutorial on how to solve one, and who on top of it has made a mission of 'fixing the Javascript Interview process'. The reality is that, if you are to get hired anywhere as a Javascript developer, it would be hard and almost impossible in the current state to bypass these types of challenges.

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.

The challenge

Hacker Rank Sock Merchant Page

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.

The code




function sortAndCount( n, arr ) {
    let sorted = arr.sort( (a,b) => a - b);
    let pairs = 0;

    for (let i = 0; i < n - 1; i++) {
        if ( sorted[i] === sorted[i + 1]) {
            pairs++;
            i += 1;
        }
    }

    return pairs;
}

Video Transcript

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

This is a good first solution suitable for small arrays but can surely be improved upon. Let me know about your take on it in the comments

Comments

[BHAVESH GUPTA]

A better approach:
Runtime: O(n)

1. Take input array as A.
2. Declare a dictionary, D.

3. Iterate over A and store each values frequency as:

   if i exists in D, then D[i]=D[i]+1
   else, D[i]=1

4. Iterate over D and sum half of each key-value pair.

[Ady Ngom]

Hello Bhavesh, thank you for your input. This is the first solution and not necessarily the most performant one as I have stated in the video. If you look at the gist that was created for this project here Sock merchant solutions you will that the second solution that is coming in part 2 is using the dictionary approach tou have suggested

javascript
function stockAndCount( n, arr ) {
let pairs = 0;
const colors = arr.reduce((acc, val) => {
(!!acc[val]) ? acc[val] += 1 : acc[val] = 1;
return acc;
}, {});

Object.keys(colors).forEach( n => {
    let _pair = parseInt( colors[n] / 2);
    if ( _pair >= 1 ) pairs += _pair;
});

return pairs;

}

Since this is unassuming of who is watching and what the level is, I start with the simple easy to grasp and evolve to the 'better' solution, better being relative here.

Stay tuned for the next episode and the reasoning why solution 2 will be a better approach.

Cheers

[BHAVESH GUPTA]

Good work, Sir.

[kurisutofu]

Could we add 0.5 to avoid reiteration and round up when getting the value for a specific color?

[Ady Ngom]

Reiteration is prevented by skipping to 2 indexes down if a match is found. I’m not clear on how 0.5 will help here since we are looking at full pairs values

[kurisutofu]

Yes, you're right. I somehow didn't notice you were using i++ and i+=1.
Sorry.

The 0.5 comment was regarding Bavesh's step 4, sorry I was not clear.

[Annie Liao]

Thanks for this. I used a similar approach but forgot about the built-in sort method. Also, really appreciated your preface, which is very encouraging, esp. for someone who felt crushed for not being able to solve the "easy" challenge.

[Ady Ngom]

Hey Annie thank you for the kind words and I'm so happy that you found the article helpful. No worries about being crushed we all go through those phases no matter how far we evolve in our careers.
Keep at it, and don't be hard on yourself. Speeding and rushing are two different things so let us all keep pacing ourselves.
Take care 🙂

[kurisutofu]

I had the same idea as Bhavesh but looking at the code in the article (I could not watch the video so sorry if it's in there), I'm a little confused.

Is arr populated with only the color integer? Like [1,2,1,1,3] for example?

Also, if you have something like [1,1,1], does the function need to return 1 or 2?

1 pair and 1 lonely sock?
Or 2 possible pairs?

[Ady Ngom]

Yes array is only populated with color integer and the challenge is specific about actual pairs so no possible. [1,1,1] should return 1 to satisfy the exercise requirements

[Rodrigo Orellana]

my version:

let ar = [1, 2, 1, 2, 1, 3, 2,1]

function sockMatching(ar) {
let tmp = [];
let dict = {}
let totalPares = 0;
ar.forEach(p => {
let idPar = 'p' + p;
if (!tmp.includes(p)) {
tmp.push(p);
dict[idPar] = 1;
} else {
dict[idPar]++;
if (dict[idPar] === 2) {
totalPares++;
dict[idPar] = 0;
}
}
})
return totalPares;
}

console.log(sockMatching(ar));

[Scale to zero]

Ady
Thanks for this...
Its helping me understand the order of computation better

So overall it is O(nlogn) * O(n)

// Complete the sockMerchant function below.
func sockMerchant(n: Int, ar: [Int]) -> Int {
var pair = 0
let sortedArr = ar.sorted() // O(nlogn)
var i=0
while (i<(sortedArr.count-1)) { // O(nlogn * n)
if sortedArr[i]==sortedArr[i+1]{
pair += 1
i += 1
}
i += 1
}
return pair
}

sockMerchant(n: 9, ar: [10, 20, 20, 10, 10, 30, 50, 10, 20])

[Rusimbi Patrick]

What is the time complexity on this one?