Abstract / Summary

Given an array of integers, find the largest number of pairs that can be formed where each pair consists of equal elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 76% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of counting how many pairs and how many single elements remain after forming as many pairs as possible from a list of integers. It builds a frequency map of the input values, derives the total number of complete pairs and leftover singles, and returns these two numbers in a list. The algorithm processes the input in two linear passes and uses constant-time dictionary operations.

Frequency Construction

The first logical block creates a dictionary that records how many times each distinct integer appears in the input list. A defaultdict with an integer default value is used so that each new key starts at zero and can be incremented directly.

freq = defaultdict(int)
for n in nums:
    freq[n] += 1

This step ensures that every element contributes to the count of its value without needing explicit existence checks.

Pair and Single Accumulation

After the frequencies are known, the code iterates over the collection of counts. For each count f, integer division by two yields the number of complete pairs that can be formed from that value, while a bitwise AND with 1 extracts the remainder (either 0 or 1) indicating whether a single element is left unpaired.

one = 0  # singles
two = 0  # pairs
for f in freq.values():
    two += f // 2
    one += f & 1

The use of // and & 1 provides a concise and efficient way to compute both quantities in a single pass over the frequency values.

Result Formation

Finally, the method packages the accumulated pair count and single count into a list and returns it to the caller.

return [two, one]

The order of elements in the result matches the required output format: the first entry is the total number of pairs, the second entry is the number of leftover singles.

Edge Cases Handled

When the input list is empty, the frequency dictionary remains empty, the accumulation loop does not execute, and the method returns [0, 0], correctly indicating that no pairs or singles exist. If all elements are identical, the frequency map contains a single entry with a large count; the division and remainder operations correctly compute the maximum number of pairs and any possible leftover single. When every element is distinct, each frequency is 1; the loop adds zero to the pair total and increments the single counter for each element, resulting in a pair count of 0 and a single count equal to the length of the input list. The algorithm also gracefully handles very large counts for a single value because the arithmetic operations are performed using Python’s arbitrary-precision integers.

Performance Optimizations

The code leverages a defaultdict to avoid conditional checks when updating frequencies, which reduces overhead in the first pass. The second pass combines the computation of pairs and singles into a single loop, eliminating the need for separate traversals. Using integer division and a bitwise AND operation provides fast arithmetic without invoking more expensive functions. Memory usage is limited to the frequency dictionary, which stores at most one entry per distinct value, and a few integer variables for the aggregates, keeping the auxiliary space minimal. The overall design ensures that the algorithm scales linearly with the size of the input while maintaining a small constant factor in runtime.

Imagine there is a big scattered pile of colorful socks on the floor. To solve this, first start by creating a special container that keeps track of how many socks of each color exist. Go through the pile one by one, picking up each sock and putting it into the container so that it remembers the count for that specific color.

Once every sock is sorted into the container, it is time to match them up. Look at each pile of socks in the container to see if they can form pairs. When finding two socks of the same color, group them together as a pair. If there is an odd number of socks, one will be left over all by itself. Keep adding up all the pairs found and counting all the lonely socks that did not have a match. This makes it easy to know exactly how many pairs were made and how many single socks are still waiting for a friend.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java			C++				TS
	WalkCCC	Python		Java			C++
	leetcode.ca	Python	JS	Java		Go	C++	C	C#	Rust	TS
	Progiez	Python		Java			C++
github	chandansgowda	Python
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq						C++
	JoshCrozier		JS
	lkwq007	Python
	muhammadfarhankt					Go
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality