LeetCode 1128. Number of Equivalent Domino Pairs Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Counting

We can concatenate the two numbers of each domino in order of size to form a two-digit number, so that equivalent dominoes can be concatenated into the same two-digit number. For example, both [1, 2] and [2, 1] are concatenated into the two-digit number 12, and both [3, 4] and [4, 3] are concatenated into the two-digit number 34.

Then we traverse all the dominoes, using an array cnt of length 100 to record the number of occurrences of each two-digit number. For each domino, the two-digit number we concatenate is x, then the answer will increase by cnt[x], and then we add 1 to the value of cnt[x]. Continue to traverse the next domino, and we can count the number of all equivalent domino pairs.

The time complexity is O(n), and the space complexity is O(C). Here, n is the number of dominoes, and C is the maximum number of two-digit numbers concatenated in the dominoes, which is 100.

PythonJavaC++GoTypeScriptRust

class Solution: def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int: cnt = Counter() ans = 0 for a, b in dominoes: x = a * 10 + b if a < b else b * 10 + a ans += cnt[x] cnt[x] += 1 return ans(code-box)

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; } }(code-box)

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; } };(code-box)

func numEquivDominoPairs(dominoes [][]int) (ans int) { cnt := [100]int{} for _, e := range dominoes { x := e[0]*10 + e[1] if e[0] > e[1] { x = e[1]*10 + e[0] } ans += cnt[x] cnt[x]++ } return }(code-box)

function numEquivDominoPairs(dominoes: number[][]): number { const cnt: number[] = new Array(100).fill(0); let ans = 0; for (const [a, b] of dominoes) { const key = a < b ? a * 10 + b : b * 10 + a; ans += cnt[key]; cnt[key]++; } return ans; }(code-box)

impl Solution { pub fn num_equiv_domino_pairs(dominoes: Vec<Vec<i32>>) -> i32 { let mut cnt = [0i32; 100]; let mut ans = 0; for d in dominoes { let a = d[0] as usize; let b = d[1] as usize; let key = if a < b { a * 10 + b } else { b * 10 + a }; ans += cnt[key]; cnt[key] += 1; } ans } }(code-box)