Number of Equivalent Domino Pairs

Here, the task is to consider each pair of numbers in the dominoes list as a unique identifier. We’re essentially creating a new number where the smaller number is on the left and the larger number is on the right (or simply, the numbers are in ascending order).

For this, we create a function f(domino) = min(d[0], d[1]) * 10 + max(d[0], d[1]). What this does is it forms a new 2-digit number where the tens place is occupied by the smaller number of the domino and the ones place by the larger number. This way, regardless of the order of numbers in the original domino, the transformed number is unique to that pair. This is a simple and clever trick to keep track of which dominoes are equivalent without having to worry about their original order.

For instance, in the example you provided, dominoes = [[1,2],[2,1],[3,4],[5,6]], the function would transform it into [12, 12, 34, 56].

So, [1,2] and [2,1] both become 12, showing that they are equivalent. [3,4] becomes 34 and [5,6] becomes 56, each unique to their respective pairs.

Once we have these transformed numbers, we can simply count how many times each number appears in the list to find out how many pairs of equivalent dominoes we have. This method allows us to solve the problem using simple mathematical operations and a counting mechanism.

To solve this problem, we can use a dictionary (hashmap) to count the occurrence of each pair. Since a pair (a,b) is considered equivalent to (b,a), we need to sort the pair before adding it to the hashmap. After we have counted all pairs, we can use the combination formula to calculate the number of equivalent pairs. This formula, n*(n-1)/2, calculates the number of ways to pick 2 items from n items.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from collections import defaultdict
from typing import List

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        pair_count = defaultdict(int)
        for domino in dominoes:
            pair = tuple(sorted(domino))  # sort the pair
            pair_count[pair] += 1

        total_pairs = 0
        for count in pair_count.values():
            total_pairs += count * (count - 1) // 2  # combination formula

        return total_pairs

In this code, we first import the required Python libraries and define our solution class and function. We initialize a defaultdict to store the count of each pair. The defaultdict is a special type of Python dictionary that provides a default value for non-existing keys, which makes it easier to use when counting.

Next, we iterate over each domino pair in the input list. For each pair, we sort the pair before adding it to our pair_count dictionary. This ensures that equivalent pairs, like (a, b) and (b, a), are treated as the same key in our dictionary.

Finally, we iterate over the count of each pair in our dictionary and use the combination formula to calculate the number of equivalent pairs for each count. We add these up to get the total number of equivalent pairs.

This approach ensures that we correctly count all equivalent pairs, as required by the problem statement.