The Sock Merchant problem is an algorithm challenge that tests our ability to work with arrays, counting, and basic data structures. The goal is simple: given a list of socks represented by integers (where each integer represents a color), determine how many matching pairs of socks exist. This problem is a great way to practice efficient counting techniques in Java.
1. Problem Statement
In this problem, we are given an array of integers where each integer represents the color of a sock. Our task is to count how many pairs of socks with matching colors there are. A pair consists of two socks of the same color, and each sock can only be used once.
Example
Consider the following input array:
[10, 20, 20, 10, 10, 30, 50, 10, 20]
In this case, the pairs are:
- (10, 10)
- (10, 10)
- (20, 20)
So, the total number of pairs is 3.
There are multiple ways to solve this problem efficiently in Java. In this article, we will explore two approaches: using a frequency array and using a HashSet. Both approaches aim to count matching pairs in linear time.
2. Using Arrays (Frequency Counting)
This approach works by counting how many times each sock color appears using a fixed-size array. It is efficient when the range of possible sock colors is known and small.
public class SockMerchantArray {
public static int countPairs(int[] socks) {
int[] frequency = new int[101]; // assuming sock colors range from 0 to 100
for (int sock : socks) {
frequency[sock]++;
}
int pairs = 0;
for (int count : frequency) {
pairs += count / 2;
}
return pairs;
}
public static void main(String[] args) {
int[] socks = {10, 20, 20, 10, 10, 30, 50, 10, 20};
IO.println("Total pairs: " + countPairs(socks));
}
}
This code works by using an integer array to store the frequency of each sock color. Each index represents a color, and the value at that index represents how many times that color appears. After counting all socks, we loop through the frequency array and divide each count by 2 to determine how many pairs can be formed.
3. Using HashSet (Pair Matching Technique)
This approach uses a HashSet to track unmatched socks. When a matching sock is found, a pair is formed, and the sock is removed from the set.
public class SockMerchantHashSet {
public static int countPairs(int[] socks) {
Set<Integer> unmatched = new HashSet<>();
int pairs = 0;
for (int sock : socks) {
if (unmatched.contains(sock)) {
pairs++;
unmatched.remove(sock);
} else {
unmatched.add(sock);
}
}
return pairs;
}
public static void main(String[] args) {
int[] socks = {10, 20, 20, 10, 10, 30, 50, 10, 20};
IO.println("Total pairs: " + countPairs(socks));
}
}
This solution works by storing socks that have not yet been paired in a HashSet. When a sock appears for the first time, it is added to the set. If it appears again, it means a pair has been found, so we increment the pair count and remove the sock from the set. This ensures that each sock is only used once.
Both solutions run in O(n) time because they each iterate through the input array once. The array-based approach uses constant space when the range is fixed, while the HashSet approach uses O(n) space in the worst case.
4. Conclusion
The Sock Merchant problem is an effective way to practice counting techniques and data structure usage in Java. By using either an Array or a HashSet, we can solve the problem efficiently in linear time. The array approach is faster when the input range is known, while the HashSet approach is more flexible for unknown ranges. Understanding these approaches will help you tackle more complex problems involving frequency counting and pair matching in the future.
5. Download the Source Code
This article explained how to solve the Sock Merchant problem using Java.
You can download the full source code of this example here: Java sock merchant problem
