Leetcode – Number of Equivalent Domino Pairs Solution

Spread the love

The “Number of Equivalent Domino Pairs” problem is an interesting coding challenge that can be found on Leetcode. It involves array manipulation and has multiple ways to approach the solution, each varying in terms of computational efficiency. This article provides a comprehensive guide to solving the problem, taking a deep dive into different algorithms, and discussing their time and space complexities.

Problem Description

The problem statement on LeetCode is as follows:

Given a list of n dominoes, dominoes[i] = [a, i] 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 < n, dominoes[i] is equivalent to dominoes[j].

Example:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Brute-Force Approach

The most naive way to solve this problem would be to use nested loops to iterate over all pairs of dominoes to check if they are equivalent. If they are, increment a counter.

Here’s how this would look in Python:

def numEquivDominoPairs(dominoes):
    count = 0
    for i in range(len(dominoes)):
        for j in range(i+1, len(dominoes)):
            if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:
                count += 1
            elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:
                count += 1
    return count

Time Complexity:

The time complexity for this approach is O(n^2) where n is the number of dominoes.

Space Complexity:

The space complexity is O(1), as we are only using a single counter variable.

Using a Dictionary to Count Frequencies

A more efficient way to solve this problem is to use a dictionary to count the frequency of each (sorted) domino. Then, for each type of domino that appears n times, the number of equivalent pairs will be (n/2), which is n×(n−1)/2.

from collections import Counter

def numEquivDominoPairs(dominoes):
    count = Counter(tuple(sorted(d)) for d in dominoes)
    return sum(n * (n-1) // 2 for n in count.values())

Time Complexity:

The time complexity for this approach is O(n), where n is the number of dominoes.

Space Complexity:

The space complexity is O(n) for storing the count dictionary.

Using a Tuple of Tuples as Dictionary Keys

Instead of using sorted lists as dictionary keys, we can directly use tuples, which are hashable, thereby eliminating the overhead of sorting each domino.

def numEquivDominoPairs(dominoes):
    count = {}
    ans = 0
    for a, b in dominoes:
        key = tuple(sorted((a, b)))
        ans += count.get(key, 0)
        count[key] = count.get(key, 0) + 1
    return ans

Time Complexity:

The time complexity is O(n), the same as the previous method.

Space Complexity:

The space complexity is O(n) for storing the count dictionary.

Using Integer Encoding

Another creative approach involves encoding each domino as an integer by using the formula min(a,b)×10+max(a,b). This uniquely identifies each domino, and we can then use a counter to track the frequency of each unique domino.

def numEquivDominoPairs(dominoes):
    count = Counter(min(a, b) * 10 + max(a, b) for a, b in dominoes)
    return sum(n * (n-1) // 2 for n in count.values())

Time Complexity:

The time complexity is O(n).

Space Complexity:

The space complexity is O(n).

Conclusion

The “Number of Equivalent Domino Pairs” problem is a fascinating exercise in array manipulation and frequency counting. It starts off simple but offers avenues for various optimizations. While the brute-force approach is relatively straightforward to implement, it’s not efficient. Leveraging Python’s Counter class from the collections module or employing dictionary-based methods significantly improve the performance.

Leave a Reply