How to Compute the 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

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

Bruteforce Algorithm in O(N^2) pairs

The intuitive solution is to bruteforce the O(N^2) pairs and count if they are Equivalent domino pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int res = 0;
        for (int i = 0; i < dominoes.size(); ++ i) {
            for (int j = i + 1; j< dominoes.size(); ++ j) {
                if (((dominoes[i][0] == dominoes[j][0]) && 
                    (dominoes[i][1] == dominoes[j][1])) ||
                    ((dominoes[i][0] == dominoes[j][1]) && 
                    (dominoes[i][1] == dominoes[j][0]))) {
                    res ++;
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int res = 0;
        for (int i = 0; i < dominoes.size(); ++ i) {
            for (int j = i + 1; j< dominoes.size(); ++ j) {
                if (((dominoes[i][0] == dominoes[j][0]) && 
                    (dominoes[i][1] == dominoes[j][1])) ||
                    ((dominoes[i][0] == dominoes[j][1]) && 
                    (dominoes[i][1] == dominoes[j][0]))) {
                    res ++;
                }
            }
        }
        return res;
    }
};

The constant space is required and the performance of such algorithm is slow when the size of the input is significant.

O(N) counting using Hash map

The Equivalent pairs can be simplified by sorting the pairs. After re-arrangement of the pair values, we can count them in hash map. And another O(N) is to sum the total combinations. If there are n items for a domino pair, then there are n*(n-1)/2 equivalent domino pairs.

The following C++ uses the STL::minmax_element to return the min and max of the pair values. And the unordered_map (hash map) to do the counting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> data;
        for (const auto &n: dominoes) {
            const auto [minv, maxv] = minmax_element(begin(n), end(n));
            int key = *minv * 10 + *maxv;
            data[key] ++;
        }
        int res = 0;
        for (auto it = data.begin(); it != data.end(); ++ it) {
            auto key = it->first;
            res += data[key] * (data[key] - 1) / 2;
        }
        return res;
    }
};

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> data;
        for (const auto &n: dominoes) {
            const auto [minv, maxv] = minmax_element(begin(n), end(n));
            int key = *minv * 10 + *maxv;
            data[key] ++;
        }
        int res = 0;
        for (auto it = data.begin(); it != data.end(); ++ it) {
            auto key = it->first;
            res += data[key] * (data[key] - 1) / 2;
        }
        return res;
    }
};

A Linear space O(N) is required to store the counters for each domino pair.

–EOF (The Ultimate Computing & Technology Blog) —