Algorithm
Problem Name: 1128. Number of Equivalent Domino Pairs
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 * 104dominoes[i].length == 21 <= dominoes[i][j] <= 9
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
int numOfPairs = 0;
Map < Integer, Integer> map = new HashMap<>();
for (int[] dominoe : dominoes) {
int key = Math.min(dominoe[0], dominoe[1]) * 10 + Math.max(dominoe[0], dominoe[1]);
numOfPairs += map.getOrDefault(key, 0);
map.put(key, map.getOrDefault(key, 0) + 1);
}
return numOfPairs;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numEquivDominoPairs = function(dominoes) {
const hash = {}
for (let dom of dominoes) {
const [a, b] = dom
const key = `${a},${b}`, alterKey = `${b},${a}`
if (hash[key] == null && hash[alterKey] == null) {
hash[key] = 1
} else {
if(hash[key] != null) hash[key] += 1
else hash[alterKey] += 1
}
}
let res = 0
Object.keys(hash).forEach(k => {
if(hash[k] > 1) res += sum(hash[k])
})
return res
};
function sum(n) {
let res = 0
while(n > 1) {
res += n - 1
n--
}
return res
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
return sum(v * (v - 1) // 2 for v in collections.Counter(tuple(sorted(d)) for d in dominoes).values())
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _1128_NumberOfEquivalentDominoPairs
{
public int NumEquivDominoPairs(int[][] dominoes)
{
var counts = new Dictionary < int, int>();
foreach (var domino in dominoes)
{
var index = Math.Min(domino[0], domino[1]) * 10 + Math.Max(domino[0], domino[1]);
if (!counts.ContainsKey(index))
counts[index] = 1;
else
counts[index]++;
}
var result = 0;
foreach (var value in counts.Values)
result += value * (value - 1) / 2;
return result;
}
}
}
Input
Output