DEV Community

Play Button Pause Button
Ady Ngom
Ady Ngom

Posted on

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (13)

Collapse
 
bhaveshg profile image
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.

Collapse
 
adyngom profile image
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


Enter fullscreen mode Exit fullscreen mode


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;
Enter fullscreen mode Exit fullscreen mode

}


Enter fullscreen mode Exit fullscreen mode

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

Collapse
 
bhaveshg profile image
BHAVESH GUPTA

Good work, Sir.

Collapse
 
kurisutofu profile image
kurisutofu • Edited

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

Collapse
 
adyngom profile image
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

Thread Thread
 
kurisutofu profile image
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.

Collapse
 
liaowow profile image
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.

Collapse
 
adyngom profile image
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 🙂

Collapse
 
kurisutofu profile image
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?

Collapse
 
adyngom profile image
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

Collapse
 
rodrigorellana profile image
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));

Collapse
 
mindmath profile image
Scale to zero • Edited

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])

Collapse
 
rusimbipatrick profile image
Rusimbi Patrick

What is the time complexity on this one?