Number of Equivalent Domino Pairs — Problem & Solution
Number of Equivalent Domino Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Equivalent Domino Pairs is an easy coding problem on arrays, hash table and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two dominoes [a, b] and [c, d] are equivalent if a == c and b == d, or if a == d and b == c — a domino may be rotated.
Given a list dominoes, return the number of pairs (i, j) with i < j where the two dominoes are equivalent.
Example 1
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1
Explanation: [1,2] and [2,1] are the same domino rotated.
Example 2
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3
Explanation: The three [1,2] dominoes give 3-choose-2 = 3 pairs.
Example 3
Input: dominoes = [[1,1]]
Output: 0
Constraints
1 <= dominoes.length <= 30dominoes[i].length == 21 <= dominoes[i][j] <= 9
Hints for Number of Equivalent Domino Pairs
Hint 1
Rotation means
[a, b]and[b, a]must hash to the same key — normalise by putting the smaller value first.Hint 2
min * 10 + maxpacks the normalised pair into a single integer key.Hint 3
Count as you scan: each new domino pairs with every equivalent one already seen.
How to solve Number of Equivalent Domino Pairs
Normalise each domino with the smaller value first so rotations share a key, then count pairs as you scan: each new domino pairs with every equivalent one already seen.
Approach
- Compute
key = min·10 + max. - Add
count[key]to the total, then incrementcount[key].
Why it works
Equivalence classes collapse to a single key, and summing the running count for each occurrence yields c(c-1)/2 pairs per class.
Complexity
- Time —
O(n) - Space —
O(1) — at most 100 keys
Pitfalls
- Values are ≤ 9, which is what makes the
10·a + bpacking collision-free.
Reference solution
Python
def numEquivDominoPairs(dominoes) -> int:
count = {}
total = 0
for a, b in dominoes:
key = a * 10 + b if a < b else b * 10 + a
total += count.get(key, 0)
count[key] = count.get(key, 0) + 1
return totalJava
public static int numEquivDominoPairs(int[][] dominoes) {
int[] count = new int[100];
int total = 0;
for (int[] d : dominoes) {
int key = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
total += count[key];
count[key]++;
}
return total;
}C++
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
int count[100] = {0};
int total = 0;
for (vector<int>& d : dominoes) {
int key = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
total += count[key];
count[key]++;
}
return total;
}JavaScript
var numEquivDominoPairs = function(dominoes) {
const count = new Map();
let total = 0;
for (let i = 0; i < dominoes.length; i++) {
const a = dominoes[i][0], b = dominoes[i][1];
const key = a < b ? a * 10 + b : b * 10 + a;
total += count.get(key) || 0;
count.set(key, (count.get(key) || 0) + 1);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets