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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Equivalent Domino Pairs

Number: 1227

Difficulty: Easy

Paid? No

Companies: Apple, Amazon

Problem Description

Given a list of domino pairs, where each domino is represented as [a, b], determine the number of pairs (i, j) such that dominoes[i] is equivalent to dominoes[j]. Two dominoes are equivalent if one can be rotated to become equal to the other (i.e., either a == c and b == d, or a == d and b == c).

Key Insights

  • A domino [a, b] is equivalent to [b, a], so normalization by sorting each pair makes comparison easier.
  • Use a hash table (or dictionary) to count the occurrence of each normalized domino representation.
  • For each domino type with frequency f, the number of equivalent pairs is f * (f - 1) / 2.
  • The solution runs with a single pass over the list for counting and a second pass over the hash table for pair calculation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of dominoes. Space Complexity: O(n) in the worst case for the hash table storage.

Solution

The approach is to convert each domino to its normalized form by sorting the pair (ensuring the smaller number comes first). Then, use a hash table to count how many times each normalized domino appears. Finally, calculate the number of pairs using the combination formula n * (n - 1) / 2 for each unique domino, and sum all these pair counts. This method avoids any unnecessary comparisons and efficiently solves the problem.

Code Solutions

# Defining the function to count equivalent domino pairs
def num_equiv_domino_pairs(dominoes):
    # Dictionary to maintain count of each normalized domino representation
    domino_count = {}
    
    # Loop over each domino and sort its values to normalize it
    for domino in dominoes:
        normalized = tuple(sorted(domino))  # Sort the domino, e.g., [2,1] becomes (1,2)
        # Increment the count in the dictionary
        domino_count[normalized] = domino_count.get(normalized, 0) + 1
    
    # Initialize the count for equivalent pairs
    pairs = 0
    # For each unique domino representation, calculate the pairs using combination formula
    for count in domino_count.values():
        pairs += count * (count - 1) // 2  # n choose 2
    
    return pairs

# Example Usage
dominoes = [[1,2],[2,1],[3,4],[5,6]]
print(num_equiv_domino_pairs(dominoes))  # Expected output is 1
← Back to All Questions