Number of Equivalent Domino Pairs

Difficulty: Easy | Acceptance: 60.70% | Paid: No Topics: Array, Hash Table, Counting

Given a list of dominoes, dominoes[i] = [a, b] 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.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

• Examples
• Constraints
• Brute Force
• Hash Map with Sorted Keys
• 2D Array Counter

Examples

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 <= dominoes.length <= 4 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

Brute Force

Intuition Compare every pair of dominoes directly and count the equivalent ones.

Steps

• Initialize count to 0
• For each pair (i, j) where i < j
• Check if dominoes[i] is equivalent to dominoes[j]
• Increment count if equivalent
• Return count

class Solution:
    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:
        n = len(dominoes)
        count = 0
        for i in range(n):
            for j in range(i + 1, n):
                a, b = dominoes[i]
                c, d = dominoes[j]
                if (a == c and b == d) or (a == d and b == c):
                    count += 1
        return count

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large inputs

Hash Map with Sorted Keys

Intuition Normalize each domino by sorting its values, then count occurrences using a hash map.

Steps

• Create a hash map to count occurrences of each normalized domino
• For each domino [a, b], normalize to [min(a,b), max(a,b)]
• Use this normalized form as the key in the hash map
• For each count k, add k * (k-1) / 2 to the result
• Return the total count

class Solution:
    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:
        from collections import defaultdict
        
        count = defaultdict(int)
        for a, b in dominoes:
            key = (min(a, b), max(a, b))
            count[key] += 1
        
        result = 0
        for v in count.values():
            result += v * (v - 1) // 2
        return result

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Efficient solution using hash map for counting

2D Array Counter

Intuition Since domino values are limited to 1-9, use a fixed-size 2D array instead of a hash map.

Steps

• Create a 10x10 array initialized to 0
• For each domino [a, b], increment count[min(a,b)][max(a,b)]
• Sum up all pairs using the formula k * (k-1) / 2
• Return the total count

class Solution:
    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:
        count = [[0] * 10 for _ in range(10)]
        
        for a, b in dominoes:
            mn, mx = min(a, b), max(a, b)
            count[mn][mx] += 1
        
        result = 0
        for i in range(10):
            for j in range(10):
                v = count[i][j]
                result += v * (v - 1) // 2
        return result

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Most space-efficient solution due to fixed array size