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

 

Constraints:

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

 

Solution:

Transform the input pair into two digits number which is (min([0], [1]) * 10 + max([0], [1])), and use a map to count the frequency.

The number of pair will be [v * (v – 1) / 2], v means the frequency amount.

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> count = new HashMap<>();
        int numPair = 0;
        
        //dominoes into code (min * 10 + max)
        for (int[] d : dominoes) {
            int num = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]);
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        //cnt += v * (v - 1) / 2
        for (int v : count.values()) {
            numPair += v * (v - 1) / 2;
        }
        
        return numPair;
    }
}

 

Time complexity: O(N).

Space complexity: O(N).