Teaching Kids Programming – Number of Equivalent Domino Pairs (Hash Table + Combination)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

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

Counting Equivalent Domino Pairs: Brute Force and Optimized Python Solutions

Leetcode 1128: Number of Equivalent Domino Pairs

Given a list of dominoes represented as pairs of integers, count how many pairs are equivalent. Two dominoes [a, b] and [c, d] are considered equivalent if a == c and b == d or a == d and b == c.

Solution 1: Brute Force Comparison

This is the most naive solution that checks every possible pair of dominoes.

from typing import List

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        count = 0
        n = len(dominoes)
        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

Time and Space Complexity:

• Time: O(n²), where n is the number of dominoes.
• Space: O(1), uses no extra space except counters.

Solution 2: Incremental Hash Map Count

This approach uses a dictionary to count previously seen normalized dominoes as we iterate.

from collections import defaultdict
from typing import List

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -< int:
        num = defaultdict(int)
        ans = 0
        for x, y in dominoes:
            val = tuple(sorted((x, y)))
            ans += num[val]
            num[val] += 1
        return ans

Time and Space Complexity:

• Time: O(n), linear scan with constant time operations.
• Space: O(k), where k ≤ 100 is the number of unique normalized domino pairs.

Solution 3: Frequency Count with Combinatorics

Instead of counting incrementally, we first compute frequency of each normalized domino pair and then calculate how many unordered pairs can be made from the counts.

from collections import defaultdict
from typing import List

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        num = defaultdict(int)
        for x, y in dominoes:
            val = tuple(sorted((x, y)))
            num[val] += 1
        return sum(i * (i - 1) // 2 for i in num.values())

Time and Space Complexity:

• Time: O(n), for building the hash map and summing the pairs.
• Space: O(k), same as Solution 2.

Comparison Table

Takeaways

1. The brute-force method is simple but inefficient for large inputs.
2. The hash map method is fast and intuitive, especially for streaming or real-time cases.
3. The frequency + math solution is the cleanest and mathematically elegant.

Interview Tip:

• Always start with the brute-force idea and gradually optimize.
• Knowing the formula n * (n - 1) // 2 for counting pairs is very handy!

–EOF (The Ultimate Computing & Technology Blog) —