Welcome to Subscribe On Youtube

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

All Problems

All Solutions