algoadvance

Leetcode 1128. Number of Equivalent Domino Pairs

Problem Statement

Given a list of dominoes, each represented as a pair of integers [a, b], determine the number of pairs (i, j) for which dominoes[i] is equivalent to dominoes[j]. Two dominoes [a, b] and [c, d] are considered equivalent if either (a == c and b == d) or (a == d and b == c).

In other words, domino [1, 2] is equivalent to domino [2, 1].

Example

Clarifying Questions

Strategy

To solve this problem efficiently, we can use a hash map to record the frequency of each equivalent domino representation. For each domino, we can sort the pair (a, b) to make sure that [a, b] and [b, a] are always mapped to the same key in the hash map. Here’s the plan:

  1. Convert each domino to a normalized tuple (min(a, b), max(a, b)) to ensure the same representation for equivalent pairs.
  2. Use a hash map to count the frequency of each normalized domino.
  3. For each domino count in the hash map, calculate the number of pairs using the combination formula n * (n - 1) / 2 where n is the number of occurrences of a particular domino.
  4. Sum all these values to get the total number of equivalent domino pairs.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int numEquivDominoPairs(std::vector<std::pair<int, int>>& dominoes) {
        std::unordered_map<int, int> count;
        int result = 0;
        
        for (auto &domino : dominoes) {
            int a = domino.first;
            int b = domino.second;
            // Normalize the domino representation by ensuring a <= b
            int key = (std::min(a, b) * 10) + std::max(a, b);
            count[key]++;
        }
        
        for (auto &entry : count) {
            int n = entry.second;
            result += (n * (n - 1)) / 2;
        }
        
        return result;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     std::vector<std::pair<int, int>> dominoes = \{\{1, 2}, {2, 1}, {3, 4}, {5, 6}};
//     int result = sol.numEquivDominoPairs(dominoes);
//     std::cout << "Number of equivalent domino pairs: " << result << std::endl; // Output: 1
//     return 0;
// }

Time Complexity

This solution is efficient for the given constraints and will handle the maximum input size comfortably.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI