Number of Equivalent Domino Pairs Leetcode Solution

Problem statement

In the problem ” Number of Equivalent Domino Pairs,”  we are given a list of dominoes where each domino consists of two values like dominoes[i]=[a,b]. Two dominoes, dominoes[i] =[a,b] and dominoes[j]=[c,d]  are equivalent if (a==c and b==d) or (a==d and c==d).

Our task is to find out the total number of pair(i,j) where i!=j and dominoes[i] is equivalent to dominoes[j]. Given values of a and b lies in the range[1,9].

Example

dominoes = [[1,2],[2,1],[3,4],[5,6]]

1

Explanation: In this example dominoes[0] is equivalent to dominoes[1] because it is satisfying the condition (a==d and c==d). As this is the only pair satisfying equivalent domino criteria so the answer is one.

Approach for Number of Equivalent Domino Pairs Leetcode Solution

We can solve this problem by selecting a domino and then checking all other remaining dominoes if they are equivalent to the selected domino or not. we will do this for all dominoes and then divide the total count of equivalent dominoes by 2 will give the answer. But the time complexity for this approach would be O(n*n). We can solve this problem in O(n) time by following the below steps:

1. We will convert two numbers (a,b) into a single number, this will make checking equivalence easy.
2. This hash function will convert two numbers into one number c=min(a,b)*10+max(a,b).
3. Now we will create a hash table to count the frequency of each number.
4. We will traverse the dominoes array and will store the frequency of c in the hash table.
5. After calculating the frequency of c values we can calculate the number of equivalent dominoes. Suppose a number x has f frequency in the hash table then the number of equivalent pairs for value x will be fC2 that is (f*(f-1))/2.
6. We will traverse the hash table and will calculate the total number of equivalent dominoes by summing up the number of equivalent dominoes of each entry in the hash table.

Implementation

C++ code for Number of Equivalent Domino Pairs

#include <bits/stdc++.h> 
using namespace std; 
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> count;
        int res = 0;
        for (auto& d : dominoes) {
           count[min(d[0], d[1]) * 10 + max(d[0], d[1])]++;
        }
         for (auto const& pair: count)
         {
          int v= pair.second; 
          res += v * (v - 1) / 2;
         }

        return res;
    }

int main() 
{ 
    vector<vector<int>> dominoes
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
int ans=numEquivDominoPairs(dominoes); 
 cout<<ans<<endl;
 return 0;
}

1

Java code for Number of Equivalent Domino Pairs

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int[] d : dominoes) {
            int k = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]);
            count.put(k, count.getOrDefault(k, 0) + 1);
        }
        for (int v : count.values()) {
            res += v * (v - 1) / 2;
        }
        return res;
    }
  public static void main(String[] args) {
        int[][] dominoes=
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
        int ans=numEquivDominoPairs(dominoes); 
        System.out.println(ans);
  }
}

1

Complexity Analysis of Number of Equivalent Domino Pairs Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the dominoes array only once. Here n is the length of the dominoes array.

Space complexity

The space complexity of the above code is O(n) because we are creating a hash table.

References