Domain 1EasyCORE

Number of Equivalent Domino Pairs

The problem asks us to find the number of equivalent domino pairs in a given list of dominoes. Two dominoes are considered equivalent if they can be rotated to match each other. Specifically, `[a, b]` is equivalent to `[c, d]` if either (`a==c` and `b==d`) or (`a==d` and `b==c`). The input is a list of dominoes where each domino is represented as a pair of integers. The output should be the count of unique pairs `(i, j)` such that `0 <= i < j < dominoes.length` and the dominoes at these indices are equivalent.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1128. Number of Equivalent Domino Pairs

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 46.3%


Problem Breakdown

The problem asks us to find the number of equivalent domino pairs in a given list of dominoes. Two dominoes are considered equivalent if they can be rotated to match each other. Specifically, [a, b] is equivalent to [c, d] if either (a==c and b==d) or (a==d and b==c). The input is a list of dominoes where each domino is represented as a pair of integers. The output should be the count of unique pairs (i, j) such that 0 <= i < j < dominoes.length and the dominoes at these indices are equivalent.

Inputs:

  • A list of dominoes, where each domino is a list of two integers [a, b].

Outputs:

  • An integer representing the number of equivalent domino pairs.

Implicit Constraints or Edge Cases:

  • The list can be empty, in which case the output should be 0.
  • Each domino’s values are between 1 and 9, inclusive.
  • The brute-force approach would involve checking every pair of dominoes, which is inefficient for large inputs (up to 40,000 dominoes).

Intuition

The brute-force approach involves comparing each domino with every other domino to check if they are equivalent. This results in a time complexity of (O(n^2)), which is not efficient given the constraints.

A better approach involves recognizing that we can normalize each domino by sorting its values, so [a, b] becomes min(a, b), max(a, b). This way, all equivalent dominoes will have the same normalized form. We can then use a hash map (dictionary in Python) to count occurrences of each normalized domino. The number of pairs for a given normalized domino is determined by the combination formula (C(n, 2) = \frac{n(n-1)}{2}), where n is the count of that normalized domino.

Approach

  1. Normalization: For each domino [a, b], create a normalized form as (min(a, b), max(a, b)).
  2. Counting Occurrences: Use a dictionary to count how many times each normalized domino appears.
  3. Calculating Pairs: For each unique normalized domino with a count n, calculate the number of pairs using the combination formula (C(n, 2)).
  4. Summing Pairs: Sum up all the calculated pairs to get the final result.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the number of dominoes. We iterate through the list once to normalize and count, and then iterate through the dictionary to calculate pairs.
  • Space Complexity: (O(n)) in the worst case, where all dominoes are unique and stored in the dictionary.

Solution

def numEquivDominoPairs(dominoes):
    from collections import defaultdict
    
    # Dictionary to count occurrences of each normalized domino
    count = defaultdict(int)
    
    for a, b in dominoes:
        # Normalize the domino
        key = (min(a, b), max(a, b))
        # Increment the count for this normalized domino
        count[key] += 1
    
    # Calculate the number of equivalent pairs
    total_pairs = 0
    for n in count.values():
        if n > 1:
            total_pairs += n * (n - 1) // 2
    
    return total_pairs

Edge Cases Handled

  • Empty Input: If the input list is empty, the function returns 0 because there are no dominoes to compare.
  • All Unique Dominoes: If all dominoes are unique, the dictionary will have an entry for each domino with a count of 1, and the combination formula will not add any pairs.
  • All Identical Dominoes: If all dominoes are identical, the dictionary will have one entry with a high count, and the combination formula will correctly calculate the number of pairs.