Number Of Equivalent Domino Pairs - Leetcode Solution

The problem "Number of Equivalent Domino Pairs" on LeetCode can be solved using a Hash Table (also known as a Dictionary or Map).

The problem statement is as follows:

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

To solve this problem using a Hash Table, we need to store the count of each unique domino pair in a dictionary. We can then traverse through the list of dominoes and for each domino, we can check if its equivalent pair is already present in the dictionary. If it is present, then we increment the count in the dictionary, else we add this pair to the dictionary with a count of 1.

Let's look at the Python code implementation:

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        count = {}
        res = 0
        for d in dominoes:
            key = tuple(sorted(d))
            if key in count:
                res += count[key]
                count[key] += 1
            else:
                count[key] = 1
        return res

Here, we first create an empty dictionary count to store the count of each unique domino pair. We also initialize the result variable res to 0.

Then we iterate through the list of dominoes using a for-loop and for each domino, we compute its equivalent pair as a tuple using the sorted method. We then check if this pair is already present in the dictionary. If it is, then we add the count of that pair to the result res and also increment its count in the dictionary. If it is not present, then we add this pair to the dictionary with a count of 1.

Finally, we return the result res.

The time complexity of this solution is O(nlogn) due to the sorted method used inside the loop, where n is the length of the input list of dominoes. However, the space complexity is O(n) as we need to store the count of each unique domino pair in the dictionary.

1