Solution Explanation: Number of Equivalent Domino Pairs

The problem asks to find the number of pairs of equivalent dominoes in a given list. Two dominoes [a, b] and [c, d] are equivalent if either a == c and b == d, or a == d and b == c (meaning one can be rotated to match the other).

Approach: Counting

The most efficient approach leverages a counting technique using a hash map (or an array in this case, due to the limited range of domino values). The core idea is to represent each domino uniquely regardless of its orientation.

1. Unique Representation: We create a unique integer representation for each domino. Since domino values range from 1 to 9, we can concatenate the smaller value with the larger value to form a two-digit number. For example:

   • [1, 2] becomes 12
   • [2, 1] becomes 12 (same as [1,2])
   • [3, 4] becomes 34
   • [4, 3] becomes 34 (same as [3,4])

2. Counting Occurrences: We use a cnt array (size 100, because the concatenated number will always be between 10 and 99) to store the frequency of each unique domino representation. We initialize cnt to all zeros.

3. Iteration and Counting: We iterate through the dominoes list. For each domino:

   • We generate its unique integer representation (x) as described above.
   • We add the current count of x (cnt[x]) to the total count of equivalent pairs (ans). This is because cnt[x] represents the number of equivalent dominoes encountered before the current one.
   • We increment the count of x in the cnt array (cnt[x]++).

4. Return Result: Finally, we return the total count ans.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of dominoes. We iterate through the dominoes list once. The operations within the loop (generating the unique representation, accessing and updating the cnt array) are all constant time.

• Space Complexity: O(1). The cnt array has a fixed size of 100, regardless of the input size. Therefore, the space usage is constant.

Code Implementations

The code examples below demonstrate the approach in several programming languages. Note that the basic logic remains the same across all languages. The primary difference lies in the syntax and data structures used.

Python:

from collections import Counter
 
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        cnt = Counter()
        ans = 0
        for a, b in dominoes:
            x = min(a, b) * 10 + max(a, b) #efficient unique representation
            ans += cnt[x]
            cnt[x] += 1
        return ans
 

Java:

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] cnt = new int[100];
        int ans = 0;
        for (int[] domino : dominoes) {
            int x = Math.min(domino[0], domino[1]) * 10 + Math.max(domino[0], domino[1]);
            ans += cnt[x];
            cnt[x]++;
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int cnt[100] = {0};
        int ans = 0;
        for (auto& domino : dominoes) {
            int x = min(domino[0], domino[1]) * 10 + max(domino[0], domino[1]);
            ans += cnt[x];
            cnt[x]++;
        }
        return ans;
    }
};

Go:

func numEquivDominoPairs(dominoes [][]int) int {
	cnt := [100]int{}
	ans := 0
	for _, d := range dominoes {
		x := min(d[0], d[1])*10 + max(d[0], d[1])
		ans += cnt[x]
		cnt[x]++
	}
	return ans
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These code examples all implement the same efficient counting algorithm with a time complexity of O(n) and a space complexity of O(1). The choice of language depends on personal preference and the context of the problem.