Number of Equivalent Domino Pairs

• Initialize a variable pairs to 0.
• Use a nested loop to iterate through all unique pairs of indices (i, j) where i < j.
• For each pair of dominoes dominoes[i] and dominoes[j], check for equivalence.
• Let d1 = dominoes[i] and d2 = dominoes[j].
• The dominoes are equivalent if (d1[0] == d2[0] && d1[1] == d2[1]) or (d1[0] == d2[1] && d1[1] == d2[0]).
• If they are equivalent, increment the pairs counter.
• After checking all pairs, return the final pairs count.

The brute-force method is the most straightforward way to solve the problem. We can compare every domino with every other domino that comes after it in the list.

We initialize a counter for the number of equivalent pairs to zero. The outer loop runs from the first domino to the second-to-last domino (index i from 0 to n-2). The inner loop runs from the domino immediately following i to the last domino (index j from i+1 to n-1). This ensures that we only consider each pair (i, j) once and that i is always less than j.

Inside the inner loop, we perform the equivalence check. A domino [a, b] is equivalent to [c, d] if they are identical or if one can be rotated to match the other. This translates to the condition (a == c && b == d) || (a == d && b == c). If this condition is true, we've found an equivalent pair, so we increment our counter. After the loops complete, the counter will hold the total number of such pairs.

1class Solution {2    public int numEquivDominoPairs(int[][] dominoes) {3        int count = 0;4        int n = dominoes.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                int[] d1 = dominoes[i];8                int[] d2 = dominoes[j];9                if ((d1[0] == d2[0] && d1[1] == d2[1]) || (d1[0] == d2[1] && d1[1] == d2[0])) {10                    count++;11                }12            }13        }14        return count;15    }16}

• Initialize pairs = 0 and a frequency map (or an array) counts.
• Iterate through each domino in the dominoes list.
• For each domino, create a canonical representation. A simple way is to sort its values: v1 = min(domino[0], domino[1]), v2 = max(domino[0], domino[1]).
• Create a unique key from this canonical form. Since values are from 1 to 9, a key can be key = v1 * 10 + v2.
• Look up the key in the counts map/array. Let the current frequency be currentCount.
• Each of the currentCount dominoes seen so far can form a new pair with the current domino. Add currentCount to pairs.
• Increment the frequency for the key in the counts map/array.
• After the loop, return pairs.

To optimize from a quadratic to a linear time complexity, we need to avoid nested loops. We can achieve this by processing the list in a single pass and using a data structure to remember the dominoes we've already seen.

The key insight is to represent each domino in a standard, or canonical, form. Since [a, b] is equivalent to [b, a], we can define the canonical form as the pair with the smaller number first, i.e., [min(a, b), max(a, b)]. For example, both [1, 2] and [2, 1] map to the canonical form [1, 2].

We can then count the frequency of each canonical form. As we iterate through the dominoes, for each domino, we first convert it to its canonical form. Then, we check how many times we've already seen this canonical form. If we've seen it k times before, the current domino can form k new pairs. We add k to our total count of pairs and then update the frequency of this canonical form to k+1.

To implement the frequency count, we can use a hash map. Given the constraint that domino values are between 1 and 9, we can create a unique integer key for each canonical pair [v1, v2] by computing v1 * 10 + v2. This allows us to use a simple array of size 100 instead of a hash map, which can be slightly faster.

1// Using an array as a frequency map2class Solution {3    public int numEquivDominoPairs(int[][] dominoes) {4        int[] counts = new int[100]; // Keys are from 1*10+1=11 to 9*10+9=995        int pairs = 0;6        for (int[] domino : dominoes) {7            int v1 = Math.min(domino[0], domino[1]);8            int v2 = Math.max(domino[0], domino[1]);9            int key = v1 * 10 + v2;10            11            // The number of pairs the current domino forms is the number12            // of equivalent dominoes we've already seen.13            pairs += counts[key];14            15            // Increment the count for this canonical form.16            counts[key]++;17        }18        return pairs;19    }20}