1128. Number of Equivalent Domino Pairs

Description

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

Solutions

Solution 1: 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(int[][] dominoes) {
int[] cnt = new int[100];
int ans = 0;
for (var e : dominoes) {
int x = e[0] < e[1] ? e[0] * 10 + e[1] : e[1] * 10 + e[0];
ans += cnt[x]++;
}
return ans;
}
}

• 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;
}
};

• class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
cnt = Counter()
ans = 0
for a, b in dominoes:
ans += cnt[(a, b)]
cnt[(a, b)] += 1
if a != b:
cnt[(b, a)] += 1
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
}