Leetcode 1128. Number of Equivalent Domino Pairs

Problem Explanation

The problem provides a list of dominoes where a domino is represented as a 2-element array [a, b] and asks to find the number of pairs of equivalent dominoes. Dominoes [a, b] and [c, d] are considered equivalent 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.

Let's take an example where dominoes = [[1,2],[2,1],[3,4],[5,6]]. In this case, the output should be 1 as domino [1,2] is equivalent to domino [2,1] by rotation. None of the other dominoes have any equivalent pair.

Approach Explanation

To solve this problem, we can use a hashmap where we store each domino as a 2-digit number with smaller digit at tens place and larger digit at ones place. With each domino, we update the count of equivalent dominoes in the map. Thus, for a new domino, the count of its equivalent dominoes is the number of pairs it can form with previously encountered dominoes.

1
2
3Assuming dominoes = [[1,2],[2,1],[3,4],[5,6]], hashmap count is initialized as empty
4
5For domino [1,2], the key is 12 and count[12] = 1
6For domino [2,1], the key is also 12 and count[12] = 2
7At this point, we found an equivalent domino for [1,2], so we increase ans by 1
8
9For rest of the dominoes [3,4] and [5,6], no equivalent domino is found so ans remains same.
10
11So, final answer is 1

Python Solution

1
2python
3class Solution:
4    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
5        ans = 0
6        count = {}
7
8        for domino in dominoes:
9            key = min(domino[0], domino[1]) * 10 + max(domino[0], domino[1])
10            if key in count:
11                ans += count[key]
12                count[key] += 1
13            else:
14                count[key] = 1
15
16        return ans

Java Solution

1
2java
3class Solution {
4    public int numEquivDominoPairs(int[][] dominoes) {
5        int ans = 0;
6        int[] count = new int[100];
7        for(int[] domino : dominoes) {
8            int val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] 
9                                             : domino[1] * 10 + domino[0];
10            ans += count[val];
11            count[val]++;
12        }
13        return ans;
14    }
15}

JavaScript Solution

1
2javascript
3var numEquivDominoPairs = function(dominoes) {
4    let ans = 0;
5    let count = new Map();
6
7    for (let domino of dominoes) {
8        let key = Math.min(domino[0], domino[1]) * 10 + Math.max(domino[0], domino[1]);
9        if (count.has(key)) {
10            ans += count.get(key);
11            count.set(key, count.get(key) + 1);
12        } else {
13            count.set(key, 1);
14        }
15    }
16
17    return ans;
18};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
6        int ans = 0;
7        unordered_map<int, int> count;
8
9        for (vector<int>& domino : dominoes) {
10            int key = min(domino[0], domino[1]) * 10 + max(domino[0], domino[1]);
11            ans += count[key];
12            ++count[key];
13        }
14
15        return ans;
16    }
17};

C# solution

1
2csharp
3public class Solution {
4    public int NumEquivDominoPairs(int[][] dominoes) {
5        int ans = 0;
6        Dictionary<int, int> count = new Dictionary<int, int>();
7
8        foreach (int[] domino in dominoes){
9            int key = Math.Min(domino[0], domino[1]) * 10 + Math.Max(domino[0], domino[1]);
10            if(count.ContainsKey(key)){
11                ans += count[key];
12                count[key] += 1;
13            }else{
14                count[key] = 1;
15            }
16        }
17
18        return ans;
19    }
20}

In all these solutions, we use a hashmap count to keep track of similar pairs. Key for each pair is obtained by considering smaller element*10+larger element. For each new dominoes pair, we increment ans by count[key] and increment count[key] by 1.In conclusion, the algorithm to find equivalent pairs in the list of dominoes applies a simple mathematical strategy to determine pair equivalency, and then map and count these pairs using a dictionary or hash map structure. Key to this approach is the equivalent mapping of domino pairs (a, b) and (b, a). The smaller integer is first in the mapping to maintain this equivalence.

The time complexity of this approach on average is O(n) where 'n' is the number of dominoes - because we go through each domino pair only once, making this approach highly efficient. The space complexity also averages to O(n) as in the worst-case scenario, hash map could contain all the domino pairs if no two are equivalent.

In real-world applications, this domino-equivalence problem or similar problems can be used in various fields like pattern recognition, image matching or analysis etc. where the concept of rotation invariance is useful and required. Other use cases can be found in fields like data mining, clustering, and bioinformatics, where relational pair matching and counting are often used.

By understanding and mastering such data structure manipulation and problem-solving strategies, one can significantly enhance their algorithmic skills, which are in high demand in today's tech industry. Hence, practicing such problems is a good way to improve your problem-solving skills as a programmer or software developer. Not just in Python, Java, JavaScript etc, these concepts can also be applied in almost every other modern programming languages with their corresponding data structures.