Number of Equivalent Domino Pairs

Problem

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].

Examples

Example 1:

1
2
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Example 2:

1
2
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3

Constraints:

1 <= dominoes.length <= 4 * 10^4
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

Solution

Method 1 - Using Frequency Map

The problem asks us to count the number of pairs of equivalent dominoes. A domino [a, b] is equivalent to [c, d] if (a == c and b == d) or (a == d and b == c). To simplify the comparison, we can treat each domino as a sorted tuple (min(a, b), max(a, b)). This ensures that equivalent dominoes will have the same representation regardless of their order.

Here are the steps:

Transform Dominoes: Convert each domino to its canonical form (min(a, b), max(a, b)).
Count Frequencies: Use a dictionary or hash map to store the frequency of each canonical form.
Calculate Pairs: For each canonical form with a count x, the number of pairs is calculated using the formula x * (x - 1) // 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> freq = new HashMap<>();
        int ans = 0;

        // Convert domino into a unique key using sorted values
        for (int[] d : dominoes) {
            int key = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]); // unique key representation
            freq.put(key, freq.getOrDefault(key, 0) + 1);
        }

        // Calculate pairs
        for (int count : freq.values()) {
            ans += (count * (count - 1)) / 2;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:
        from collections import Counter

        # Transform dominoes into sorted tuples
        freq: Counter = Counter((min(d[0], d[1]), max(d[0], d[1])) for d in dominoes)
        
        # Compute pairs
        ans: int = sum(cnt * (cnt - 1) // 2 for cnt in freq.values())

        return ans

Complexity

⏰ Time complexity: O(n).We traverse the list of dominoes once (O(n)), and calculating pairs for each unique domino is O(1).
🧺 Space complexity: O(u). Where u is the number of unique domino representations stored in the hash map.

Problem#

Examples#

Solution#

Method 1 - Using Frequency Map#

Code#

Complexity#