Code Implementation

class Solution:
    def numEquivDominoPairs(self, dominoes):
        from collections import defaultdict
        counts = defaultdict(int)
        result = 0
        for a, b in dominoes:
            key = tuple(sorted((a, b)))
            result += counts[key]
            counts[key] += 1
        return result
      

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> counts;
        int result = 0;
        for (auto &d : dominoes) {
            int a = d[0], b = d[1];
            int key = a < b ? a * 10 + b : b * 10 + a;
            result += counts[key];
            counts[key]++;
        }
        return result;
    }
};
      

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] counts = new int[100];
        int result = 0;
        for (int[] d : dominoes) {
            int a = d[0], b = d[1];
            int key = a < b ? a * 10 + b : b * 10 + a;
            result += counts[key];
            counts[key]++;
        }
        return result;
    }
}
      

var numEquivDominoPairs = function(dominoes) {
    let counts = {};
    let result = 0;
    for (let [a, b] of dominoes) {
        let key = a < b ? `${a},${b}` : `${b},${a}`;
        result += counts[key] || 0;
        counts[key] = (counts[key] || 0) + 1;
    }
    return result;
};
      

Problem Description

You are given a list of dominoes, where each domino is represented as a list of two integers [a, b]. Two dominoes [a, b] and [c, d] are considered equivalent if either a == c and b == d, or a == d and b == c; that is, if they contain the same numbers, regardless of order.

Your task is to count the number of pairs of dominoes that are equivalent. Each domino can only be used once in a pair, and the pair (i, j) is the same as (j, i) (unordered pairs).

Constraints:

• 1 ≤ dominoes.length ≤ 4 * 10⁴
• 1 ≤ dominoes[i][j] ≤ 9

Thought Process

At first glance, it seems like we need to compare every pair of dominoes to check if they are equivalent. This brute-force approach would involve checking each domino against every other domino, leading to a time complexity of O(N²), which is not efficient for large input sizes.

However, by recognizing that the order of the two numbers in a domino doesn't matter, we can treat each domino as a "bag" of two numbers. If we can represent each domino in a standardized way (for example, always as (min, max)), then equivalent dominoes will have the same representation. This insight allows us to count how many times each unique domino occurs, and then use combinatorics to count the number of unique pairs that can be formed from those counts.

Solution Approach

• Step 1: Normalize Dominoes
  For each domino, convert it to a standard form, such as (min(a, b), max(a, b)). This ensures that [2, 3] and [3, 2] are treated as the same.
• Step 2: Count Occurrences
  Use a hash map (or array, since the values are small) to count how many times each normalized domino appears.
• Step 3: Calculate Pairs
  For each domino value that appears k times, there are k*(k-1)/2 ways to choose two dominoes to form a pair.
• Step 4: Aggregate Results
  Sum up all the pairs from each unique domino to get the final answer.

We use a hash map (dictionary) because it allows us to store and look up the count for each domino in constant time. This makes the entire solution run in linear time with respect to the number of dominoes.

Example Walkthrough

Let's walk through an example with input [[1,2], [2,1], [3,4], [5,6]].

1. Normalize each domino:
   • [1,2] → (1,2)
   • [2,1] → (1,2)
   • [3,4] → (3,4)
   • [5,6] → (5,6)
2. Count occurrences:
   • (1,2): 2 times
   • (3,4): 1 time
   • (5,6): 1 time
3. Calculate pairs:
   • (1,2): 2 dominoes → 1 pair (since 2 * 1 / 2 = 1)
   • (3,4): 1 domino → 0 pairs
   • (5,6): 1 domino → 0 pairs
4. Final answer: 1

This shows how the algorithm efficiently counts equivalent domino pairs by normalization and counting.

Time and Space Complexity

• Brute-force Approach: O(N²) time, O(1) space.
  This is because you would compare every domino with every other domino.
• Optimized Approach: O(N) time, O(N) space.
  We iterate over the dominoes once to count, and then once more (or less) to sum the pairs.

The space is O(N) because, in the worst case, all dominoes are unique (but since the values are small, the actual number of unique dominoes is limited).

Summary

By recognizing that equivalent dominoes can be represented in a normalized form, we avoid expensive pairwise comparisons. Using a hash map (or array) to count occurrences, we can efficiently compute the number of equivalent pairs using combinatorics. This approach leverages normalization, counting, and mathematical pairing to solve the problem in linear time, making it both elegant and efficient.