DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for How to Solve Sock Merchant Code Challenge
Jojo Zhang
Jojo Zhang

Posted on

How to Solve Sock Merchant Code Challenge

I started the Interview Preparation Kit on Hacker Rank yesterday. The thought of why not sharing how I solve those problems came to my mind. And here I am!

In this article, I'll use the UPER (Understand, Plan, Execute, Reflect) way of the problem-solving framework that I learned in Lambda School Computer Science Curriculum to walk through problems.

The challenge

HackerRank Sock Merchant Challenge 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.

Step 1: Understand

In this step, I'd dissect the problem into following questions,

  • What is the goal?
    To count the number of how many pairs of socks. This also gives info that the final result should be an integer.

  • What do I have for parameters?

    • n: the number(interger) of socks in the pile
    • ar: an array of the colors (also integer to represent the value of each color) of each sock
  • How to achieve the goal?

    In order to count pairs, we need to know what a pair means in this situation. Since the value of colors are different numbers, finding 2 of the same numbers will qualify a pair. Then we can add up those pairs.

Step 2: Plan

  • Implement the Input Example Implementing the input example in real life helps me figure out the algorithm. I keep asking myself how I would do it in real life.
n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]
Enter fullscreen mode Exit fullscreen mode

To put in a visual way, I made this simple illustration via draw.io
Imgur

In order for me to find pairs, I would sort this array first.
Imgur

Now, we can easily see and count that there're 3 pairs.
Imgur

With the help of an example and visual graph, I feel like I fully understand the problem and have a good plan in mind. Now I can start to write some pseudo-code to help me translate the logic to code.

Step 3: Execute

  • Write Pseudo Code
//Need to initiate a count variable to count pairs and return the value
//sort the given array
//loop through the sorted array 
//if the current item equals to the next item 
//then that's a pair, increment our count variable
//also increment i to skip the next item
//return the count value

Enter fullscreen mode Exit fullscreen mode
  • Time to Code
function sockMerchant(n, ar) {
  //Need to initiate a count variable to count pairs and return the value
  let count = 0
  //sort the given array
  ar = ar.sort()
  //loop through the sorted array 
  for (let i=0; i < n-1; i++) {
    //if the current item equals to the next item 
    if(ar[i] === ar[i+1]){
      //then that's a pair, increment our count variable
      count++
      //also increment i to skip the next item
      i+=1
    }
  }
  //return the count value
  return count
}
Enter fullscreen mode Exit fullscreen mode

Step 4: Reflect

There are 2 tricky parts of this solution

  1. Do not loop through the last item since we compare the current to the next item. There's no next item to the last item. and will throw an error
  2. When a pair is found, we also need to increment the looping index to skip the paired item

Other reflections including time complexity: there are definitely better solutions for time complexity since I sort the array first (O(n log(n))) and a for loop (O(n)).

This is how I solved this problem with UPER. Documenting the thought process is fun. I'll keep writing. Hope you like this.
Have a great day, everyone :)

Top comments (10)

Collapse
 
johnmilimo profile image
JMW

Solution in kotlin:

fun main() {
    val colors = arrayOf(10, 20, 20, 10, 10, 30, 50, 10, 20)
    var pairs = 0
    val colorFrequencies: MutableMap<Int, Int> = mutableMapOf()
    colors.forEach { color ->
        val count = colorFrequencies.getOrDefault(color, 0)
        colorFrequencies[color] = count+1
    }
    colorFrequencies.forEach { entry ->
        pairs += entry.value / 2
    }
    println(pairs)
}

Basically you store the frequency of each colour in a map, then you perform division by 2 on each entry value

Collapse
 
nomadkitty profile image
Jojo Zhang

Very interesting. I can see some syntax similarities between JavaScript and Kotlin. Thanks for sharing.

Collapse
 
saitejach127 profile image
Sai Teja

Great Article. Another approach to solving the problem would be to store the number of occurrences of each element in the array in a Hashmap and traverse the hashmap and add the count/2 to result of each element in the array.

int sockMerchant(int n, vector<int> ar) {
unordered_map<int,int> count;
for(int i=0;i<ar.size();i++){
count[ar[i]]++;
}
int result = 0;
for(auto it=count.begin();it!=count.end();it++){
result += (it->second/2);
}
return result;
}

Collapse
 
nomadkitty profile image
Jojo Zhang

This is a great idea and thanks for sharing

Collapse
 
briwa profile image
briwa

First off, it's a great article. Unrelated but I wrote a code that is something similar to this when developing a game to match a pair of emojis a while ago, so this article really takes me back.

One thing I'd like to point out that in your code (I assume it's Javascript but CMIIW), .sort already mutates the array, so you don't have to reassign it to a variable.

- ar = ar.sort()
+ ar.sort()

Nevertheless I think you got the right idea. Some would jump straight into a solution, but to me taking a step back and visualizing the problem is very essential in determining the right solution. Well done!

Collapse
 
nomadkitty profile image
Jojo Zhang

Thank you for your kind words. And you're right, I totally don't need to reassign the value to ar. Thanks for pointing it out :)

Collapse
 
khuongduybui profile image
Duy K. Bui

We can do it in time O(n) space O(k) with k = number of distinct colors.

function sockMerchant(n, array) {
  let count = 0;
  const seen = {};
  array.forEach((item) => {
    if (seen[item]) { // one sock of this color was seen before, so this completes a pair
      seen[item] = false;
      count++;
    } else { // this is the one in a pair
      seen[item] = true;
    }
  });
  return count;
}
Collapse
 
nomadkitty profile image
Jojo Zhang

Great idea. This is a definitely better solution than mine. Thank you for sharing.

Collapse
 
shivamseth05 profile image
Shivam Seth • Edited on

Complete the sockMerchant function below: ( Solution In Python)

def sockMerchant(n, ar):
pears = 0
color = set()
for i in range(len(ar)):
if ar[i] not in color:
color.add(ar[i])
else:
pears += 1
color.remove(ar[i])
return pears
if name == 'main':

n = int(input())

ar = list(map(int, input().rstrip().split()))
ar.sort()


result = sockMerchant(n, ar)
print(result)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
memitaru profile image
Ami Scott (they/them)

Great and easy to understand explanation. I especially liked the way you went through your thought process. Thanks for sharing!

This post blew up on DEV in 2020:

js visualized

πŸš€βš™οΈ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! πŸ₯³

Happy coding!