Sales by Match Algorithm 🧦

In this article, I'll be describing how I solved the Sales by Match Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

There is a large pile of socks that must be paired by colour. Given an array of integers representing the colour of each sock, determine how many pairs of socks with matching colours there are.

Example

n = 7
ar = [1, 2, 1, 2, 1, 3, 2]

There is one pair of colour 1 and one of colour 2. There are three odd socks left, one of each colour. The number of pairs is 2.

Function Description

Complete the sockMerchant function in the editor below. sockMerchant has the following parameter(s):

• int n: the number of socks in the pile
• int ar[n]: the colours of each sock

Returns

• int: the number of pairs

Samle Input:

n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]

Sample Output:

3

Solution 🔎

In plain English, given an array of integers representing the colour of a sock, we need to find out how many pairs of socks with matching colours exist. So we need to group two integers (sock colour) together, and then count these groups (pairs).

Pretty straightforward problem this time, although I passed all test cases only on the third try.😌 So how do we solve this?

Let's consider the sample input above.

n = 9

ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]

Step 1️⃣: It's all about grouping.🧦🧦

We're trying to get matching pairs of socks, so an easy way to start will be to first group all socks with the same colour.

1. let's create a variable grouped_socks to store our grouped socks. This will be an array containing sub arrays representing one colour.
2. Since we could not use any external python libraries, like itertools.groupby, to group easily, we applied this solution from stackoverflow.
3. We'll call set() on our array ar to return an array of distinct values.

    set(ar) 
    # {10, 20, 50, 30}
   

4. Next, for a given distinct value in ar, we'll count how many times that value appears in ar and then return the value multiplied by its count in our grouped_socks array. e.g. 10 appears 4 times in ar, so return [10, 10, 10, 10].
5. As usual we'll go the pythonic way! coughs in list comprehensions 😅😅

    grouped_socks = [[x] * ar.count(x) for x in set(ar)] 
    # [[10, 10, 10, 10], [20, 20, 20], [50], [30]]
   

Step 2️⃣: Grouping all pairs of socks.

After getting groups of same coloured socks, we need to get pairs within these groups.

1. We'll store our grouped pairs in a distinct_pairs variable.
2. The approach is to slice our grouped_socks into groups of two socks, while returning any remainders.

     distinct_pairs = [ group[i : i+2] for group in grouped_socks for i in range(0, len(group), 2) ]
    # [[10, 10], [10, 10], [20, 20], [20], [50], [30]]
   

Step 3️⃣: Count the number of identical pairs.

1. All that's left now is to simply count the pairs with matching colours by checking pairs contain at least two colours which are also identical.🤓
2. We'll store our count in a count_pairs variable.
3. We'll also create a variable. counter to keep track of our count.
4. len(pair) == 2 checks pairs that contain at least two colours
5. len(set(pair)) == 1 is true for any pair with identical colours.

6. We combine the two conditions above and finally, return the sum of our counter.

    count_pairs = [ counter+1 for pair in distinct_pairs if len(pair) == 2 and len(set(pair)) == 1]
   
    return sum(check_pairs)
    # 3
   

Step 4️⃣: Putting it all together.⚙️⚙️

Full code:

def sockMerchant(n, ar):
    # Write your code here
    counter = 0

    grouped_socks = [[x] * ar.count(x) for x in set(ar)] 

    distinct_pairs = [ group[i : i+2] for group in grouped_socks for i in range(0, len(group), 2) ]

    count_pairs = [ counter+1 for pair in distinct_pairs if len(pair) == 2 and len(set(pair)) == 1]

    return sum(count_pairs)


sockMerchant(9, [10, 20, 20, 10, 10, 30, 50, 10, 20])
# 3

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻