Problem of The Day: Number of Equivalent Domino Pairs

Problem Statement

leetcode problem link

Intuition

We are asked to count the number of pairs of dominoes that are equivalent. Two dominoes are equivalent if one can be rotated to match the other. Since each domino consists of exactly two numbers, we can sort the pair so that both [a, b] and [b, a] are treated the same. This way, we can count identical (unordered) pairs efficiently.

Approach

We iterate through the list of dominoes and for each domino, we sort the two values to normalize its representation (e.g., [2, 1] becomes (1, 2)). We then use a dictionary (freq) to count how many times each normalized pair has occurred. For every new occurrence of a pair, we add the number of times it has appeared before to the result, because each new domino can form a valid pair with all previous identical dominoes.

Complexity

• Time complexity:
  \(O(n)\)
  We iterate through the list of dominoes once, and each operation inside the loop is constant time.

• Space complexity:
  \(O(n)\)
  In the worst case, all dominoes are unique (even after sorting), and we store each one in the dictionary.

Code

from collections import defaultdict

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        """
        :type dominoes: List[List[int]]
        :rtype: int
        """
        freq = defaultdict(int)
        res = 0
        for x, y in dominoes:
            pair = tuple(sorted([x, y]))
            if pair in freq:
                res += freq[pair]
            freq[pair] += 1
        return res

Editorial

Approach: Tuple Representation + Counting

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        num = [0] * 100
        ret = 0
        for x, y in dominoes:
            val = x * 10 + y if x <= y else y * 10 + x
            ret += num[val]
            num[val] += 1
        return ret