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
- Normalization: For each domino
[a, b], create a normalized form as(min(a, b), max(a, b)). - Counting Occurrences: Use a dictionary to count how many times each normalized domino appears.
- Calculating Pairs: For each unique normalized domino with a count
n, calculate the number of pairs using the combination formula (C(n, 2)). - 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.