Formatted question description: https://leetcode.ca/all/1128.html

1128. Number of Equivalent Domino Pairs (Easy)

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

Related Topics:
Array

Solution 1.

// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& A) {
        map<vector<int>, int> m;
        int ans = 0;
        for (auto &v : A) {
            sort(begin(v), end(v));
            ans += m[v];
            m[v]++;
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& A) {
        for (auto &v : A) sort(begin(v), end(v));
        sort(begin(A), end(A));
        int ans = 0;
        for (int i = 0, N = A.size(); i < N;) {
            int start = i;
            while (i < N && A[i] == A[start]) ++i;
            int len = i - start;
            ans += (len - 1) * len / 2;
        }
        return ans;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& A) {
        int cnt[10][10] = {}, ans = 0;
        for (auto &v : A) {
            if (v[0] > v[1]) swap(v[0], v[1]);
            ans += cnt[v[0]][v[1]]++;
        }
        return ans;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public int numEquivDominoPairs(int[][] dominoes) {
          int length = dominoes.length;
          for (int i = 0; i < length; i++) {
              int[] domino = dominoes[i];
              if (domino[0] > domino[1]) {
                  int temp = domino[0];
                  dominoes[i][0] = dominoes[i][1];
                  dominoes[i][1] = temp;
              }
          }
          Arrays.sort(dominoes, new Comparator<int[]>() {
              public int compare(int[] array1, int[] array2) {
                  if (array1[0] != array2[0])
                      return array1[0] - array2[0];
                  else
                      return array1[1] - array2[1];
              }
          });
          int equivalentCount = 0;
          int consecutive = 1;
          for (int i = 1; i < length; i++) {
              int[] prevDomino = dominoes[i - 1];
              int[] curDomino = dominoes[i];
              if (prevDomino[0] == curDomino[0] && prevDomino[1] == curDomino[1])
                  consecutive++;
              else {
                  equivalentCount += consecutive * (consecutive - 1) / 2;
                  consecutive = 1;
              }
          }
          if (consecutive > 1)
              equivalentCount += consecutive * (consecutive - 1) / 2;
          return equivalentCount;
      }
  }
  

• // OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      int numEquivDominoPairs(vector<vector<int>>& A) {
          map<vector<int>, int> m;
          int ans = 0;
          for (auto &v : A) {
              sort(begin(v), end(v));
              ans += m[v];
              m[v]++;
          }
          return ans;
      }
  };
  

• class Solution(object):
      def numEquivDominoPairs(self, dominoes):
          count = dict()
          for domi in dominoes:
              hash_ = domi[0] * 10 + domi[1] if domi[0] < domi[1] else domi[1] * 10 + domi[0]
              if hash_ in count:
                  count[hash_] += 1
              else:
                  count[hash_] = 1
          res = 0
          for v in count.values():
              res += v * (v - 1) / 2
          return res
  

All Problems

All Solutions