Problem Informations

• Problem Index: 1128
• Problem Link: Number of Equivalent Domino Pairs
• Topics: Array, Hash Table, Counting

Problem 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 \leq 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 \leq dominoes.length \leq 4 \times 10^{4}$
• $dominoes[i].length == 2$
• $1 \leq dominoes[i][j] \leq 9$

Intuition

The problem requires finding pairs of dominoes that are equivalent, meaning they can either be identical directly or by swapping their values. The challenge is to efficiently count the number of such pairs since the number of dominoes can be quite large. My initial thought is that we need a fast way to determine if two dominoes are equivalent because the direct comparison would be too slow for larger inputs.

Approach

To solve this problem, the key observation is that each domino can be represented uniquely irrespective of its orientation. For a domino [a, b], where $a \leq b$, we can always transform it into a single integer value. The transformation idea is to create a unique hash for each possible domino configuration, treating the domino [a, b] as equivalent to [b, a].

1. Unique Representation: For each domino represented as [a, b], its unique hash value can be calculated by ensuring $a \leq b$. We can calculate this as currentVal = a * 9 + b when $a < b$, or as currentVal = b * 9 + a when $a > b$. This provides a consistent type of hash for any [a, b] and [b, a].

2. Utilize a Frequency Counter: We utilize a vector appearance of size 91 (since $1 \leq a, b \leq 9$) as a frequency counter for the calculated currentVal. This is because the highest hash value occurs when both values are 9, i.e., $9 \times 9 + 9 = 90$.

3. Count Equivalent Pairs: As we iterate through the list of dominoes, for each domino:

   • Compute its unique hash value currentVal.
   • The number of existing dominoes with the same hash currentVal contributes directly to the number of pairs that can be formed where the current domino is one part of all such pairs.
   • Thus, we add the existing count of currentVal from appearance to our total count of equivalent pairs and update the appearance for this hash.

4. Return the Total Count: After processing all dominoes, the accumulated count variable will contain the total number of domino pairs that are equivalent.

This approach ensures that each domino is processed in constant time, resulting in an overall time complexity of $O(n)$, where $n$ is the number of dominoes. This is efficient given the constraints and ensures that we can handle even the upper limits of input size quickly.

Code

C++

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int count = 0;
        int currentVal;
        vector<int> appearance(91, 0); // To store counts of each unique domino configuration

        for (vector<int>& domino : dominoes) {
            // Calculate a unique value for the domino, irrespective of its orientation
            currentVal = (domino[0] < domino[1]) ? domino[0] * 9 + domino[1] : domino[1] * 9 + domino[0];
            
            // Increment the count of equivalent domino pairs found so far
            count += appearance[currentVal]++;
        }

        return count; // Return the total number of equivalent pairs
    }
};

Python

class Solution:
    def numEquivDominoPairs(self, dominoes):
        count = 0
        currentVal = 0
        appearance = [0] * 91  # To store counts of each unique domino configuration

        for domino in dominoes:
            # Calculate a unique value for the domino, irrespective of its orientation
            currentVal = (domino[0] * 9 + domino[1]) if (domino[0] < domino[1]) else (domino[1] * 9 + domino[0])
            
            # Increment the count of equivalent domino pairs found so far
            count += appearance[currentVal]
            appearance[currentVal] += 1

        return count  # Return the total number of equivalent pairs

Complexity

• Time complexity: $O(n)$

  The time complexity is $O(n)$ because the algorithm iterates through the list of dominoes exactly once. For each domino, it performs a constant time operation to compute a unique value, independent of the domino’s orientation, and updates the corresponding count in the appearance vector. Assuming $n$ as the number of dominoes, this results in a linear time complexity with respect to the size of the input list.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the appearance vector is used to store counts for up to 91 unique domino configurations ($1 \leq a, b \leq 9$ results in $\frac{9 \times 10}{2} = 45$ unique unordered pairs, each stored once and twice due to the bidirectional equivalence). This size of the vector does not depend on the input size $n$, and is thus considered constant in terms of space.