Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count how many socks of each color exist, then for every color add floor(count / 2) to the total — each pair needs two matching socks. A hash map (or Counter) tallies colors in one pass; the answer is the sum of count // 2 over all colors.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise this as a frequency-counting problem and use integer division to convert per-color counts into pairs — instead of overcomplicating it with sorting or pairing logic.
Where candidates slip
Adding the raw count instead of count // 2 (counting socks, not pairs), or trying to physically pair socks with nested loops in O(n²).
How to stand out
Name the pattern out loud ('count frequencies, sum floor-halves'), note that n is a decoy, and mention a fixed-size array as a micro-optimization when colors are bounded.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewArray of sock colorsFor each color: count // 2YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Frequency Count — Hash Map (Optimal)
1Hint 1Explore hintHide hint
Forget about physically matching socks. If you knew exactly how many socks of each color you had, how many pairs could you make from a single color?
2Hint 2Explore hintHide hint
From c socks of one color you can make floor(c / 2) pairs. So the whole problem is: get the count per color, then sum those halves.
3Hint 3Explore hintHide hint
Walk the array once building a map color → count. Then iterate the map's values and add count // 2 to a running total.
A · Core idea
The key reframing is to stop thinking about pairing and start thinking about counting. Physically matching socks invites nested loops and O(n²) pain; counting collapses the whole task into arithmetic.
Why count // 2 is the entire answer. Once you know a color appears c times, the number of complete pairs you can build from those c identical socks is floor(c / 2) — two socks consumed per pair, and any odd leftover sits unmatched. Crucially, colors are independent: a red sock can never pair with a blue one, so the total is just the sum of count // 2 across every distinct color. There is no interaction between colors to reason about.
Why a hash map. We need to group identical values and get a count for each group. A hash map keyed by color gives O(1) average increment as we scan, so building all the counts is a single linear pass. We never sort, never compare socks against each other — we only ever ask 'how many of this color have I seen?'
Why integer division matters. Using / instead of // in Python (or forgetting that Java's int / already floors) is the classic bug. Three socks of a color must yield exactly one pair; 3 / 2 = 1.5 is wrong, 3 // 2 = 1 is right. Floor division also makes the odd-leftover case fall out for free — you never write an explicit 'is it odd?' branch.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]Hash-map state
see 10
Continue scanning
first 10 → insert 10 → 1
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
The decoy is the parameter n. Beginners assume every input is needed and try to weave n into the logic; the strong candidate notices the array alone is sufficient and that the real problem is 'frequency count, then sum the halves'. Spotting irrelevant inputs is itself a signal of clear thinking.
ComplexityO(n) time, O(k) space — One pass to build the counts (O(n)) plus one pass over the distinct colors (O(k), k ≤ n) = O(n) time. The map stores one entry per distinct color → O(k) space.
E · Edge cases and pitfalls6ar = [5] — Map = {5: 1}; 1 // 2 = 0 → returns 0. A lone sock makes no pair.Explore edge casesHide edge cases
Edge cases handled
ar = [5]Map = {5: 1}; 1 // 2 = 0 → returns 0. A lone sock makes no pair.ar = [7, 7, 7, 7]Map = {7: 4}; 4 // 2 = 2 → returns 2.ar = [1, 2, 3]All counts are 1 → every half is 0 → returns 0.
Pitfalls
- Adding the raw count instead of count // 2 — that counts socks, not pairs.
- Using float division in Python (c / 2 gives 1.5 for odd counts) — use //.
- Trying to weave the decoy parameter n into the logic when the array alone suffices.
Approach 2 of 2
Fixed-Size Count Array
1Hint 1Explore hintHide hint
Colors are constrained to a small range (1..100). Do you really need a hash map, or can you index directly?
2Hint 2Explore hintHide hint
Allocate an int array sized to the maximum color + 1 and increment counts[color] as you scan.
3Hint 3Explore hintHide hint
Then sum counts[i] / 2 across the array — same arithmetic, no hashing.
A · Core idea
When the key space is a small, known range of integers, a plain array is a faster hash map: the color is the index. This trades a tiny bit of fixed memory for the removal of all hashing overhead, and it is extremely cache-friendly.
Why it works here. The constraints cap colors at 100, so an int[101] covers every possible color with index = color. Incrementing counts[color] is a direct memory write — no hash computation, no collision handling. The aggregation step is identical to the map version: sum counts[i] / 2 over all slots.
When NOT to do this. If colors were unbounded (e.g. arbitrary 32-bit integers) the array would be enormous or impossible, and the hash map is the only viable choice. So this approach is a conditional optimization: correct and fast only because the problem promises a small range. Stating that condition aloud is what makes mentioning it impressive rather than naive.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
ar = [1, 1, 3, 3, 3]Fill array
counts[1] += 2, counts[3] += 3
counts[1]=2, counts[3]=32C · Code with teaching comments
Reference implementation previewpublic int sockMerchant(int n, List<Integer> ar) { int[] counts = new int[101]; for (int color : ar) { counts[color]++; }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(maxColor) spaceOpen the invariant and proofExplore the proofHide the proof
An array indexed by value is the degenerate, fastest form of a hash map — but only legal when values live in a small, known range. Recognising that constraint (1 ≤ ar[i] ≤ 100) is the cue to use it.
ComplexityO(n) time, O(maxColor) space — One linear pass to fill the count array and one fixed pass (≤ maxColor + 1) to sum halves = O(n). Space is O(maxColor), a constant 101 here.
E · Edge cases and pitfalls5ar = [100, 100] — counts[100] = 2 → 1 pair. The array must be size ≥ 101 to index 100 safely.Explore edge casesHide edge cases
Edge cases handled
ar = [100, 100]counts[100] = 2 → 1 pair. The array must be size ≥ 101 to index 100 safely.ar = [1]counts[1] = 1 → 0 pairs.
Pitfalls
- Sizing the array to maxColor instead of maxColor + 1 — off-by-one index out of bounds for color 100.
- Using this when colors are unbounded — the array becomes infeasible.
- Forgetting that unused slots are 0 and harmlessly add 0 to the total.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int sockMerchant(int n, List<Integer> ar) { Map<Integer, Integer> count = new HashMap<>(); for (int color : ar) { count.merge(color, 1, Integer::sum); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting socks instead of pairs
Each pair needs two socks, so a color seen c times yields c // 2 pairs, not c. Forgetting the halving doubles the answer.
Explore the code comparisonHide the code comparison
Counting socks instead of pairs
Each pair needs two socks, so a color seen c times yields c // 2 pairs, not c. Forgetting the halving doubles the answer.
Don't write this
return sum(count.values())Write this instead
return sum(c // 2 for c in count.values())2Float division instead of floor
3 / 2 is 1.5 in Python 3 — the answer must be an integer count of complete pairs. Floor division discards the unmatched leftover.
Explore the code comparisonHide the code comparison
Float division instead of floor
3 / 2 is 1.5 in Python 3 — the answer must be an integer count of complete pairs. Floor division discards the unmatched leftover.
Don't write this
return sum(c / 2 for c in count.values())Write this instead
return sum(c // 2 for c in count.values())3Brute-force pairing
Scanning for a partner for every sock with nested loops is O(n²) and needlessly complex; counting is O(n) and far simpler.
Explore the code comparisonHide the code comparison
Brute-force pairing
Scanning for a partner for every sock with nested loops is O(n²) and needlessly complex; counting is O(n) and far simpler.
Don't write this
for (int i = 0; i < ar.size(); i++)
for (int j = i + 1; j < ar.size(); j++)
if (ar.get(i).equals(ar.get(j)) && !used[j]) { /* pair... */ }Write this instead
Map<Integer, Integer> count = new HashMap<>();
for (int c : ar) count.merge(c, 1, Integer::sum);
int pairs = 0;
for (int v : count.values()) pairs += v / 2;Revise
Carry the pattern into the interview
Pattern to remember
Frequency count → sum of (count // 2)
Code pattern to memorize
count = {}
for color in ar:
count[color] = count.get(color, 0) + 1
pairs = sum(c // 2 for c in count.values())Rules to remember
- 1A pair is two socks of the same color → each color contributes
count // 2pairs, notcount. - 2Use integer (floor) division — three red socks make one pair, not 1.5.
- 3The parameter
n(number of socks) is a decoy; you can ignore it and just walk the array. - 4Order does not matter — this is pure frequency counting, so no sorting is needed.
- 5Odd leftovers are discarded automatically by floor division — never special-case them.
Use this pattern when
- You need to count matching groups / pairs by some key
- The question reduces to 'how many of each value, then combine'
- Order is irrelevant and you only care about multiplicities
- Input is small-to-medium and a single counting pass suffices
Choose another pattern when
- You need the positions/indices of matches → this only gives counts
- Pairs must be adjacent or ordered → sorting / two pointers instead
- Each element can join at most one of several different group types → matching/graph problem
- Values form a tiny fixed range and memory is tight → a fixed-size int array beats a hash map
Interview takeaway
Whenever a problem says 'how many pairs/groups of identical things', reach for a frequency map and combine the counts. Sock Merchant is the gentlest instance of the count-then-aggregate pattern that also powers Valid Anagram, Group Anagrams, and Top K Frequent Elements.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCount-then-aggregate. Build a frequency map in one pass, then combine the counts with simple arithmetic (here, sum of count // 2). The same skeleton powers Valid Anagram, Group Anagrams, and Top K Frequent Elements.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Valid AnagramComing soonSame frequency-count idea — compare character counts between two strings.
- Group AnagramsComing soonGroup by a frequency-derived key instead of summing counts.
- Top K Frequent ElementsComing soonBuild the same frequency map, then select the top counts.
- Drawing BookComing soonAnother HackerRank warm-up where the answer collapses to integer arithmetic.