Skip to content

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\).

1
2
3
4
5
6
7
8
9
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        cnt = Counter()
        ans = 0
        for a, b in dominoes:
            x = a * 10 + b if a < b else b * 10 + a
            ans += cnt[x]
            cnt[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

Comments