1128. Number of Equivalent Domino Pairs #

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

Constraints:

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

Problem Summary #

Given a list dominoes consisting of some dominoes. If one domino can be rotated by 0 degrees or 180 degrees to obtain another domino, we consider these two dominoes equivalent. Formally, the premise for dominoes[i] = [a, b] and dominoes[j] = [c, d] to be equivalent is a==c and b==d, or a==d and b==c.

Under the premise of 0 <= i < j < dominoes.length, find the number of domino pairs (i, j) such that dominoes[i] and dominoes[j] are equivalent.

Note:

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

Solution Approach #

• Given a group of dominoes, find the number of identical dominoes in this group. The definition of identical dominoes is: the 2 numbers on the dominoes are the same (the same in forward order or reverse order both count as the same)
• Easy problem. Since a domino has 2 numbers, hash the 2 numbers of the domino into a 2-digit number and compare the values. Hash both the forward order and the reverse order into 2-digit numbers, then check in the bucket whether it already exists. If it does not exist, skip it; if it exists, count it.

Code #

package leetcode

func numEquivDominoPairs(dominoes [][]int) int {
	if dominoes == nil || len(dominoes) == 0 {
		return 0
	}
	result, buckets := 0, [100]int{}
	for _, dominoe := range dominoes {
		key, rotatedKey := dominoe[0]*10+dominoe[1], dominoe[1]*10+dominoe[0]
		if dominoe[0] != dominoe[1] {
			if buckets[rotatedKey] > 0 {
				result += buckets[rotatedKey]
			}
		}
		if buckets[key] > 0 {
			result += buckets[key]
			buckets[key]++
		} else {
			buckets[key]++
		}
	}
	return result
}