# Number of Equivalent Domino Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-equivalent-domino-pairs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-equivalent-domino-pairs
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
Given a list of `dominoes`, `dominoes[i] = [a, b]` is **equivalent to** `dominoes[j] = [c, d]` if and only if either (`a == c` and `b == d`), or (`a == d` and `b == c`) - that is, one domino can be rotated to be equal to another domino.

Return _the number of pairs_ `(i, j)` _for which_ `0 <= i < j < dominoes.length`_, and_ `dominoes[i]` _is **equivalent to**_ `dominoes[j]`.

**Example 1:**

**Input:** dominoes = [[1,2],[2,1],[3,4],[5,6]]
**Output:** 1

**Example 2:**

**Input:** dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
**Output:** 3

**Constraints:**

* `1 <= dominoes.length <= 4 * 104`
* `dominoes[i].length == 2`
* `1 <= dominoes[i][j] <= 9`

# Approaches
## Brute Force
This approach involves checking every possible pair of dominoes in the list to see if they are equivalent. It uses two nested loops to iterate through all pairs `(i, j)` where `i < j`.
**Time:** O(N^2), where N is the number of dominoes. The nested loops lead to approximately N^2 / 2 comparisons, which is quadratic. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory-efficient.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
### Explanation
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.

```java
class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int count = 0;
        int n = dominoes.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] d1 = dominoes[i];
                int[] d2 = dominoes[j];
                if ((d1[0] == d2[0] && d1[1] == d2[1]) || (d1[0] == d2[1] && d1[1] == d2[0])) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- 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.

## Hash Map / Frequency Count with Canonical Form
A much more efficient approach is to iterate through the list of dominoes just once. We can standardize each domino into a "canonical" form to make comparisons easier. For a domino `[a, b]`, its canonical form can be `[min(a, b), max(a, b)]`. We then use a hash map or an array to count the occurrences of each canonical form.
**Time:** O(N), where N is the number of dominoes. We iterate through the `dominoes` array only once. Each operation (calculating key, accessing array/map) takes constant time. · **Space:** O(1). The keys in our frequency map are derived from numbers 1-9. The number of unique canonical pairs is fixed and small (45 pairs from `(1,1)` to `(9,9)`). Thus, the space for the map/array is constant regardless of the input size `N`.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Optimal solution for the given problem constraints.
**Cons:** Requires extra space for the hash map or array, although it's constant for this problem's constraints.; Slightly more complex to reason about and implement compared to the brute-force approach.
### Explanation
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.

```java
// Using an array as a frequency map
class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] counts = new int[100]; // Keys are from 1*10+1=11 to 9*10+9=99
        int pairs = 0;
        for (int[] domino : dominoes) {
            int v1 = Math.min(domino[0], domino[1]);
            int v2 = Math.max(domino[0], domino[1]);
            int key = v1 * 10 + v2;
            
            // The number of pairs the current domino forms is the number
            // of equivalent dominoes we've already seen.
            pairs += counts[key];
            
            // Increment the count for this canonical form.
            counts[key]++;
        }
        return pairs;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution { public int numEquivDominoPairs ( int [][] dominoes ) { int [] cnt = new int [ 100 ]; int ans = 0 ; for ( var e : dominoes ) { int x = e [ 0 ] < e [ 1 ] ? e [ 0 ] * 10 + e [ 1 ] : e [ 1 ] * 10 + e [ 0 ]; ans += cnt [ x ]++; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int numEquivDominoPairs ( vector < vector < int >>& dominoes ) { int cnt [ 100 ]{}; int ans = 0 ; for ( auto & e : dominoes ) { int x = e [ 0 ] < e [ 1 ] ? e [ 0 ] * 10 + e [ 1 ] : e [ 1 ] * 10 + e [ 0 ]; ans += cnt [ x ] ++ ; } return ans ; } };
```

### Python

```python
class Solution : def numEquivDominoPairs ( self , dominoes : List [ List [ int ]]) -> int : cnt = Counter () ans = 0 for a , b in dominoes : ans += cnt [( a , b )] cnt [( a , b )] += 1 if a != b : cnt [( b , a )] += 1 return ans
```