We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Equivalent Domino Pairs

Difficulty: Easy

Problem Description

Given a list of dominoes, where each domino is represented as a pair [a, b], determine the number of pairs (i, j) such that 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j]. A domino is considered equivalent if one can be rotated to match the other.

Key Insights

  • Two dominoes [a, b] and [c, d] are equivalent if:
    • They are identical in order: a == c and b == d
    • They are equivalent when rotated: a == d and b == c
  • To efficiently count equivalent pairs, we can use a hash map to track the frequency of each unique domino configuration (considering both orientations).
  • The number of ways to choose 2 dominoes from a set of n equivalent dominoes is given by the combination formula C(n, 2) = n * (n - 1) / 2.

Space and Time Complexity

Time Complexity: O(n), where n is the number of dominoes, as we traverse the list once and perform constant-time operations for each domino. Space Complexity: O(n), for storing the frequency of domino configurations in the hash map.

Solution

To solve the problem, we can use a hash map to count the occurrences of each unique domino configuration. We iterate through the list of dominoes, ensuring that each domino is stored in a canonical form (e.g., always storing the smaller number first). We then calculate the number of equivalent pairs using the counts stored in the hash map.

Code Solutions

from collections import defaultdict

def numEquivDominoPairs(dominoes):
    count = defaultdict(int)
    for a, b in dominoes:
        # Store the domino in a canonical form
        key = tuple(sorted((a, b)))
        count[key] += 1

    # Calculate the number of equivalent pairs
    result = 0
    for freq in count.values():
        if freq > 1:
            result += freq * (freq - 1) // 2

    return result
← Back to All Questions