Skip to content

← leetcode

Number of Equivalent Domino Pairs

· Easy

LeetCode problem 1128

You can just store the count of all the pairs in a 9x9 grid and calculate the number of pairs using the n * (n-1) / 2 formula, where n denotes the number of equivalent dominoes that exist.

code

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<vector<int>> grid (9, vector<int>(9, 0));
        for (auto& domino : dominoes) {
            ++grid[domino[0]-1][domino[1]-1];
        }
        int ans = 0;
        for (int i = 0; i < 9; ++i) {
            for (int j = i; j < 9; ++j) {
                int total_pairs = grid[i][j];
                if (i != j) {
                    total_pairs += grid[j][i];
                }
                ans += (total_pairs-1) * (total_pairs) / 2;
            }
        }
        return ans;
    }
};

complexity

  • Time: either O(n) where n is the size of the array dominoes or O(m^2) where m is the number of pips on each side of the domino
  • Space: O(m^2)

learnings

  • who in the flamingo makes dominoes with both sides numbered between 1-9?!

time taken

  • 7 minutes and 24 seconds
    • I tried to use a pair<int, int> as a key in an unordered_map before realising that it was not feasible oops
    • I could have just made a vector of all the pairs and used hashed its index into the unordered_map instead