Javascript Sock Merchant Challenge - Solution 1

Ady Ngom on April 23, 2019

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 wil... [Read Full]
markdown guide

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.


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

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.



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


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

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

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


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?


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

code of conduct - report abuse