Skip to main content
Talentd

Number of Equivalent Domino Pairs - Solution & Explanation

EasyArrayHash TableCounting12 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a == c and b == d), or (a == d and b == c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

 

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Example 2:

Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3

 

Constraints:

  • 1 <= dominoes.length <= 4 * 104
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9

Approach Overview

Problem Overview: You are given a list of dominoes where each domino is a pair of integers. Two dominoes are equivalent if one can be rotated to match the other, meaning [a,b] is the same as [b,a]. The task is to count how many pairs of equivalent dominoes exist in the array.

Approach 1: Using Hash Map for Count Tracking (O(n) time, O(n) space)

Normalize each domino so that the smaller number comes first: (min(a,b), max(a,b)). This removes the rotation ambiguity and gives every equivalent domino the same canonical representation. Iterate through the array and store frequencies of each normalized domino in a hash map. For every new domino, the number of equivalent pairs it forms equals the current count stored in the map, because each previous identical domino creates a new pair. This approach relies on constant-time hash lookups and works well for general counting problems involving duplicates. It heavily uses concepts from hash tables and counting.

Approach 2: Counting Using Array Indexing (O(n) time, O(1) space)

Domino values are limited to the range 1..9, which allows a compact encoding. Convert each domino into a two-digit number like 10 * min(a,b) + max(a,b). This creates a unique index between 11 and 99 for each normalized domino. Use a fixed array of size 100 to track how many times each encoded domino appears. As you iterate through the dominoes, add the current frequency of that index to the result and then increment the counter. The logic is identical to the hash map approach, but array indexing removes hashing overhead and guarantees constant memory usage. This technique is a specialized optimization of array-based frequency counting.

Recommended for interviews: The hash map counting approach is the most common answer. It clearly demonstrates how to normalize the domino representation and count combinations in linear time. The array indexing variant is slightly more optimized and shows deeper awareness of constraints, but the core insight interviewers expect is the normalization plus frequency counting pattern.

Approach 1: Using Hash Map for Count Tracking

This approach involves using a hash map (or dictionary) to count all the equivalent domino pairs efficiently. For each domino, we convert it to a canonical form where the smaller number comes first. We then use this form as a key in our map to count the occurrences of each pair. For each domino processed, increment the counter by the number of times this key has been seen before.

The function numEquivDominoPairs takes a list dominoes and uses a dictionary count to store the frequency of each canonical domino form. The canonical form is a tuple with elements sorted to handle both orientations of dominoes. As we process each domino, we increment our pairs count by how many times the canonical form has been seen before in count. Finally, we return the total number of pairs found.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(n) to store the frequency of each domino pair.

Try this approach in the editor →

Approach 2: Counting Using Array Indexing

This approach involves treating domino pairs as numbers to use their hash for direct indexing in an array (similar to a fixed-size hash map). By assigning a unique number to each domino combination using arithmetic, we can efficiently tally counts of equivalent pairs in a fixed-size array.

In this approach, we create an array count with size 100 (based on the possible values of [1-9, 1-9]). For each domino, we compute an integer key to represent it uniquely in both orientations. The key is derived by ensuring the smaller of the two numbers comes first, effectively treating the domino as a two-digit number. We then use this key to incrementally calculate pairs using direct array indexing.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1), as the size of the array is fixed and unrelated to input size.

Try this approach in the editor →

Approach 3: Counting

We can concatenate the two numbers of each domino in order of size to form a two-digit number, so that equivalent dominoes can be concatenated into the same two-digit number. For example, both [1, 2] and [2, 1] are concatenated into the two-digit number 12, and both [3, 4] and [4, 3] are concatenated into the two-digit number 34.

Then we traverse all the dominoes, using an array cnt of length 100 to record the number of occurrences of each two-digit number. For each domino, the two-digit number we concatenate is x, then the answer will increase by cnt[x], and then we add 1 to the value of cnt[x]. Continue to traverse the next domino, and we can count the number of all equivalent domino pairs.

The time complexity is O(n), and the space complexity is O(C). Here, n is the number of dominoes, and C is the maximum number of two-digit numbers concatenated in the dominoes, which is 100.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hash Map for Count Tracking

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(n) to store the frequency of each domino pair.

Counting Using Array Indexing

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1), as the size of the array is fixed and unrelated to input size.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map for Count TrackingO(n)O(n)General solution when counting normalized pairs or when value ranges are large
Array Indexing Frequency CountO(n)O(1)Best when domino values have a small fixed range like 1..9

Video Solution

Number of Equivalent Domino Pairs | Multiple Approaches | Dry Run | Leetcode 1128 | codestorywithMIK • codestorywithMIK • 6,296 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Equivalent Domino Pairs easy or hard?
Number of Equivalent Domino Pairs is classified as an Easy problem on LeetCode. The challenge focuses on recognizing that dominoes must be normalized before counting duplicates and then applying a straightforward hash map frequency technique.
Number of Equivalent Domino Pairs Python/Java solution
Python and Java solutions typically use a dictionary or HashMap to store counts of normalized domino pairs. Each time the same pair appears again, the current frequency contributes to the total number of equivalent pairs. Both implementations achieve O(n) time complexity.
How to solve Number of Equivalent Domino Pairs in O(n)?
Normalize each domino so the smaller value comes first, then track how many times that normalized pair has appeared. When you encounter the same pair again, it forms new pairs with all previous occurrences. Add the current frequency to the result and increment the count. This produces a linear-time counting solution.
What is the best approach for Number of Equivalent Domino Pairs?
The best approach uses a hash map to count normalized domino pairs. Each domino is converted to (min(a,b), max(a,b)) so that rotations are treated as the same pair. While iterating, add the existing frequency of that pair to the result and update the count. This runs in O(n) time with O(n) space.
Is Number of Equivalent Domino Pairs asked at Google/Amazon/Meta?
Domino pair counting problems appear in interviews at companies like Amazon and Google as variations of frequency counting or hash map problems. They test understanding of normalization, pair counting, and efficient use of hash tables in linear time.
What data structure is used in Number of Equivalent Domino Pairs?
The primary data structure is a hash table that stores frequencies of normalized domino pairs. Because domino values are limited to 1 through 9, an alternative implementation uses a fixed-size array for frequency counting, which reduces memory overhead and avoids hashing.
What is the time complexity of Number of Equivalent Domino Pairs?
The optimal solution runs in O(n) time because each domino is processed exactly once and hash map or array lookups take constant time. Space complexity is O(n) for the hash map approach or O(1) when using a fixed counting array based on the domino value range.

Ready to solve this problem?

Practice Number of Equivalent Domino Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays