Abstract / Summary

Count how many pairs of dominoes have the same numbers in either order.

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 61% (300k+ 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 equivalent domino pairs. Two dominoes are considered equivalent when they contain the same numbers regardless of order, for example [1,2] and [2,1]. The algorithm iterates through the list of dominoes, normalizes each domino to a canonical representation where the smaller value appears first, and uses a hash map to keep track of how many times each canonical pair has been seen. For each new domino, the current count of its canonical key is added to the result, because each previous occurrence forms a new equivalent pair with the current domino. The final result is the total number of such pairs.

Key Steps

Normalizing the Domino

The first important operation is converting each domino into a deterministic key that treats [a,b] and [b,a] as identical. This is achieved by taking the minimum and maximum of the two values and forming a tuple.

key = (min(a, b), max(a, b))

The tuple serves as an immutable hashable object suitable for dictionary keys.

Accumulating Pair Counts

A defaultdict(int) named have stores the frequency of each normalized key encountered so far. When processing a new domino, the algorithm looks up the current count for its key and adds that count to the running total result. This addition reflects the number of new pairs formed with all previously seen equivalent dominoes.

result += have[key]
have[key] += 1

Returning the Result

After the loop finishes, the accumulated result holds the total number of equivalent domino pairs and is returned directly.

return result

Edge Cases Handled

When the input list contains a single domino, the loop runs once, the lookup in have yields zero because the key has not been seen before, and the result remains zero, which is correct because no pair can be formed.

If all dominoes are identical after normalization, the algorithm correctly counts the combinatorial number of pairs. For example, with three dominoes [2,5], [5,2], [2,5], the first domino contributes zero, the second adds one (pair with the first), and the third adds two (pairs with the first and second), resulting in a total of three pairs, matching the mathematical combination C(3,2).

Dominoes containing equal numbers, such as [3,3], are also normalized to (3,3). The same logic applies, and pairs of identical double dominoes are counted correctly.

The use of defaultdict(int) ensures that any key not previously encountered defaults to zero, eliminating the need for explicit existence checks and preventing key errors.

Performance Optimizations

The algorithm operates in a single pass over the input list, avoiding nested loops and thereby eliminating quadratic work. By using a hash map for frequency tracking, each lookup and update occurs in constant average time, which keeps the overall execution time proportional to the number of dominoes.

The canonical key creation uses built-in min and max functions, which are highly optimized in the Python runtime. Storing the key as a tuple leverages Python’s efficient hashing for small immutable sequences, resulting in fast dictionary operations.

Memory usage is limited to the distinct normalized domino patterns present in the input. The dictionary grows only with unique keys, not with the total number of dominoes, which is beneficial when many dominoes share the same values. The integer counters stored in the dictionary are simple and have minimal overhead.

Imagine you have a big box of dominoes. Each domino has two numbers on it, like a little tile with a pair of spots. Sometimes you might pick up a domino with a one and a two, and sometimes you might pick up one with a two and a one. Even though they look different, they are actually the same because they have the same two numbers on them.

To figure out how many matching pairs are in the box, the computer starts with an empty notebook. It picks up each domino one by one. First, it looks at the two numbers on the tile and always writes the smaller number first and the larger number second. This way, no matter which way the domino is facing, it always gets written down in a way that matches any identical ones.

The computer looks in the notebook to see if it has already seen a domino with these two numbers before. If it has, that means the new domino makes a matching pair with the ones already found. The computer keeps a score of these matching pairs. After noticing the domino, it writes it down in the notebook so that if another one just like it shows up later, it can count that as a new pair too. It keeps doing this until every domino has been looked at.

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	C++		Java		Python				TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python	Go		Rust	TS
	Progiez	C++		Java		Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim							C
	everthis		JS
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007					Python
	suxrobGM				C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
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