algoadvance

Given a list of dominoes where each domino is represented as a list of two integers [a, b], return the number of pairs (i, j) for which the two dominoes are equivalent. Two dominoes (a, b) and (c, d) are considered equivalent if, and only if, either (a == c and b == d) or (a == d and b == c).

Example:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1
Explanation: The only equivalent pair is (0,1), because dominoes[0] is [1,2] and dominoes[1] is [2,1].

Clarifying Questions

1. Input Constraints:
   • What is the range of values for the numbers in the dominoes?
   • How many dominoes can be in the list?
   • Is input validation required?
2. Output Requirements:
   • Should we return the count of pairs or the pairs themselves?
3. Edge Cases:
   • How to handle an empty list of dominoes?
   • How to handle a list with only one domino?

Strategy

To solve this problem, we can follow these steps:

1. Normalize each domino such that the smaller number comes first. For example, a domino [2, 1] will be represented as [1, 2].
2. Use a dictionary to count occurrences of each normalized domino.
3. For each unique domino, calculate the number of pairs using the combination formula C(n, 2) = n * (n - 1) / 2 where n is the count of that domino.
4. Sum the results to get the final count.

Code

Here’s how we can implement this in Python:

from collections import defaultdict

def numEquivDominoPairs(dominoes):
    count_map = defaultdict(int)
    
    # Normalize and count each domino occurrence
    for domino in dominoes:
        normalized = tuple(sorted(domino))
        count_map[normalized] += 1
    
    pairs = 0
    # Calculate pairs
    for count in count_map.values():
        if count > 1:
            pairs += (count * (count - 1)) // 2
    
    return pairs

# Example usage
dominoes = [[1,2],[2,1],[3,4],[5,6]]
print(numEquivDominoPairs(dominoes)) # Output: 1

Time Complexity

• Normalization and Counting: We traverse through the dominoes list once to normalize and count, resulting in O(n) time complexity where n is the number of dominoes.
• Pair Calculation: We then traverse through the dictionary of counts which has at most n keys (in the worst case where all dominoes are unique) resulting in O(n).

Overall, the time complexity is O(n).

Space Complexity

• We use a dictionary to store counts of normalized dominoes, which can take up to O(n) space in the worst case where each domino is unique. Hence, the space complexity is O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?