Efficient Solution To Sock Matching Problem

Today, I encountered a problem through HackerRank that can be solved with a brute force data algorithm but has another solution that can greatly improve the runtime of your code and wanted to share it with everyone.

Problem - Sales by Match:

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

Example

n = 7
ar = [1,2,1,2,1,3,2]
There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

Solution #1 - Brute Force:

The first solution that occurred to me was to create a result variable and sort the array. I could then loop through the array looking for ar[i] === ar[i+1]. If a match was found, I would simply increment the variable by 1 and increment i by 1 as well to skip over the consumed sock. At the end of the loop, the result variable could just then be returned as the total pairs of socks. Below is the solution written out in JavaScript:

function sockMerchant(n, ar) {
    let result = 0;
    ar.sort((a,b) => a - b);
    for(let i = 0; i < n; i++){
        if(ar[i] == ar[i+1]){
            i++;
            result++;
        }
    }
    return result;
}

While this solution works, there is additional time complexity, due to the sorting of the array, then just that from the for loop.

Solution #2 - Hashing Data Structure:

This optimal time solution removes the need to sort the initial array and instead uses an object to store properties related to the array. I started by creating an object called "ones" and a result variable. When looping through the array, I could insert the value of the array at i as a property of the object. Then, I only needed to check if the ones object already contained the property at the i^th position of the array. If it did, I would increment the result variable and delete the property of array[i] from the ones object. If the property did not already exist, I would add it into the ones object. Then, after the for loop, the result variable is returned. Below is the solution, again, written out in JavaScript:

function sockMerchant(n, ar) {
    let ones = {}, result = 0;
    for(let i = 0; i < n; i++){
        if(ones.hasOwnProperty(ar[i])){
            result++;
            delete ones[ar[i]];
        }else{
            ones[ar[i]] = 0;
        }
    }
    return result;
}

With this solution, I'm able to reduce the time complexity to O(N), where N is the size of the array, and additional space complexity of O(K) where K is the size of the object created.

It's important though to always consider the constraints when determining which data algorithm to use in your solutions. If space (memory) is not an issue, then definitely go with the optimal time solution by using a Hashing Data Structure. Otherwise, a slightly slower, but more space efficient, solution with Brute Force should be utilized.

Thank you for reading and please comment below with any questions or suggestions. Also, feel free to follow me if you found this article helpful as I'll be posting more solutions to data algorithms in the near future. I hope you have a great rest of the day!