1. Overview
In this tutorial, we’ll discuss the problem of pairing socks from an array that contains 
pairs of socks.
First, we’ll define the problem and provide an example that explains it.
Second, we’ll present a naive approach. Then we’ll discuss two different approaches to improve it, and obtain better solutions.
2. Defining the Problem
Suppose we have pairs of socks randomly distributed inside an array of length 
. Each sock may have one or more specifications, such as size, color, etc; therefore, we have to pair each sock with another of the same specifications.
To understand this more clearly, let’s look at a simple example.
Let’s say that we have an array with 
socks. Additionally, each sock has a special color and a special size:
Now suppose that the color of each cell represents the color of the corresponding sock, while the number written inside the cell represents the sock size. Consequently, we can find the solution to pairing the socks:
Note that in this tutorial, we’ll discuss finding only one possible solution; we won’t consider the case where we might have more than one answer.
3. Naive Approach
3.1. Main Idea
The main idea here is to iterate over the socks. For each sock, we’ll try to find a similar one that hasn’t been paired before.
3.2. Implementation
Let’s take a look at the implementation:
algorithm findSimilarPairsNaive(N, sock):
// INPUT
// N = the number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
taken <- an array of false, with length 2 * N
for i <- 0 to 2 * N - 1:
if taken[i] is true:
continue
taken[i] <- true
for j <- i + 1 to 2 * N - 1:
if sock[i] = sock[j]:
answer <- add (sock[i], sock[j]) to answer
taken[j] <- true
break
return answer
Initially, we declare a list called 
, which will store the result as pairs of socks. In addition, we declare an array called 
, which expresses whether each sock has been taken before or not. Furthermore, we initialize this array with 
values.
Next we iterate over the socks. If the sock hasn’t been taken before, we try to find a similar one by iterating over the remaining socks and checking for similarities. If a match is found, we add the similar socks to , and flag both of them as taken.
Finally, we return , which stores the similar pairs of socks in the given array.
3.3. Complexity
The time complexity here is 
. Let’s examine the reason behind this complexity.
To start, we iterate over all the socks. For each one, we iterate over all the socks located after it inside the array. We’ll find that the 
sock will iterate over 
socks because no socks come after it. Similarly, the 
sock will iterate over 
sock, and so on. As a result, this step will cost 
, which equals 
.
4. Sorting Approach
4.1. Main Idea
The main idea here is to sort the array of socks first. When we sort it, similar socks will be next to each other; therefore, we only have to iterate over the sorted array and check each sock with its adjacent.
4.2. Implementation
Let’s take a look at the implementation:
algorithm findSimilarPairsSorting(N, sock):
// INPUT
// N = the number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
sorted <- sort(sock)
i <- 0
while i <= 2 * N - 2:
if sorted[i] = sorted[i + 1]:
answer <- add (sorted[i], sorted[i + 1]) to answer
i <- i + 1
i <- i + 1
return answer
Initially, we declare a list called , which will store the result as pairs of socks. Then we sort the given array and store it in 
.
Next we iterate over the socks, and check the similarity between the 
sock and the 
one. If they are similar, we add the similar socks to , and increase the iterator 
by to prevent the sock from joining more than one pair.
Finally, we return , which stores the similar pairs of socks in the given array.
4.3. Complexity
The time complexity here is 
. Let’s examine the reason behind this complexity.
The main complexity of this approach is the sorting algorithm, so we prefer to choose an algorithm with 
complexity as merge sort.
Then we iterate over all the socks once, and we only need 
to do that.
5. Hash Approach
5.1. Main Idea
The main idea here is to use a HashSet to store the last appearance of a similar sock. Consequently, we iterate over the socks, and in each step, we check whether the HashSet contains a similar sock or not.
5.2. Implementation
Let’s take a look at the implementation:
algorithm findSimilarPairsHash(N, sock):
// INPUT
// N = the Number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
hash_set <- create an empty hash set
i <- 0
while i < 2 * N:
if hash_set contains sock[i]:
answer <- add (sock[i], hash_set.get(sock[i])) to answer
hash_set.delete(sock[i])
else:
hash_set.add(sock[i])
i <- i + 1
return answer
Initially, we declare a list called , which will store the result as pairs of socks. We also declare 
as an empty HashSet.
Then we iterate over the socks, and check whether contains a similar sock to the one. If it does, we add both the sock and the similar sock from to the result. In addition, we delete the similar one to prevent the sock from joining more than one pair. If the HashSet doesn’t contain a similar sock, we add the sock to .
Finally, we return , which stores the similar pairs of socks in the given array.
5.3. Complexity
The time complexity here is 
.
First, we iterate over all the socks once, and we only need to do that. At each step, we check if contains a special sock, which has a 
complexity. Also, the operation of adding and deleting from has a complexity.
6. Conclusion
In this article, we presented the problem of pairing socks. We also explained the main ideas behind three different approaches to solving this problem, and walked through their implementations.