Number of Equivalent Domino Pairs solution and explanation
Google
9 more videos on this problem
Number of Equivalent Domino Pairs | Multiple Approaches | Dry Run | Leetcode 1128 | codestorywithMIKcodestorywithMIK · 25:35 · 6K views
LeetCode 1128: Number of Equivalent Domino Pairs - Interview Prep Ep 18Fisher Coder · 16:02 · 2K views
Daily Leetcode #1860: May 04, 2025 - 1128. Number of Equivalent Domino PairsProgramming Live with Larry · 4:53 · 779 views
LeetCode 1128 Number of Equivalent Domino Pairs - Java Solution Using Sorting & HashMap ExplainedAlgorithmicIQ · 13:32 · 507 views
1128. Number of Equivalent Domino Pairs | Leetcode Daily - PythonLeetcode Daily · 8:58 · 394 views
Number of Equivalent Domino Pairs - Leetcode 1128 - PythonTim Huang · 3:46 · 305 views
How to Solve "1128 Number of Equivalent Domino Pairs" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 8:07 · 300 views
Leetcode solving: 1128. Number of Equivalent Domino PairsMath Geeks · 3:55 · 221 views
LeetCode 1128 || Number of Equivalent Domino Pairs || Brute Force || Optimize || Java CodeNikhil Patel · 8:04 · 129 views
1128. Number of Equivalent Domino Pairs #leetcode #leetcodequestionandanswers #amazoninterviewCodeVia · 2:33 · 116 views
The problem
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 * 104dominoes[i].length == 21 <= 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.
def numEquivDominoPairs(dominoes):
count = {}
pairs = 0
for a, b in dominoes:
key = tuple(sorted((a, b)))
pairs += count.get(key, 0)
count[key] = count.get(key, 0) + 1
return pairsimport java.util.HashMap;
public class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
HashMap<String, Integer> count = new HashMap<>();
int pairs = 0;
for (int[] domino : dominoes) {
int a = domino[0], b = domino[1];
String key = a < b ? a + ":" + b : b + ":" + a;
pairs += count.getOrDefault(key, 0);
count.put(key, count.getOrDefault(key, 0) + 1);
}
return pairs;
}
}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.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(n) to store the frequency of each domino pair.
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.
def numEquivDominoPairs(dominoes):
count = [0] * 100
pairs = 0
for a, b in dominoes:
key = a * 10 + b if a <= b else b * 10 + a
pairs += count[key]
count[key] += 1
return pairspublic class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
int[] count = new int[100];
int pairs = 0;
for (int[] domino : dominoes) {
int a = domino[0], b = domino[1];
int key = a < b ? a * 10 + b : b * 10 + a;
pairs += count[key];
count[key]++;
}
return pairs;
}
}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.
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.
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.
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
int cnt[100]{};
int ans = 0;
for (auto& e : dominoes) {
int x = e[0] < e[1] ? e[0] * 10 + e[1] : e[1] * 10 + e[0];
ans += cnt[x]++;
}
return ans;
}
};function numEquivDominoPairs(dominoes: number[][]): number {
const cnt: number[] = new Array(100).fill(0);
let ans = 0;
for (const [a, b] of dominoes) {
const key = a < b ? a * 10 + b : b * 10 + a;
ans += cnt[key];
cnt[key]++;
}
return ans;
}func numEquivDominoPairs(dominoes [][]int) (ans int) {
cnt := [100]int{}
for _, e := range dominoes {
x := e[0]*10 + e[1]
if e[0] > e[1] {
x = e[1]*10 + e[0]
}
ans += cnt[x]
cnt[x]++
}
return
}impl Solution {
pub fn num_equiv_domino_pairs(dominoes: Vec<Vec<i32>>) -> i32 {
let mut cnt = [0i32; 100];
let mut ans = 0;
for d in dominoes {
let a = d[0] as usize;
let b = d[1] as usize;
let key = if a < b { a * 10 + b } else { b * 10 + a };
ans += cnt[key];
cnt[key] += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Hash Map for Count Tracking | Time Complexity: O(n), where n is the number of dominoes. |
| Counting Using Array Indexing | Time Complexity: O(n), where n is the number of dominoes. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map for Count Tracking | O(n) | O(n) | General solution when counting normalized pairs or when value ranges are large |
| Array Indexing Frequency Count | O(n) | O(1) | Best when domino values have a small fixed range like 1..9 |
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.