1128. Number of Equivalent Domino Pairs

Problem Description

In this problem, we are given a list of tiles representing dominoes, each domino represented as a pair of integers [a, b]. Two dominoes [a, b] and [c, d] are defined to be equivalent if one can be rotated to become the other, meaning either (a == c and b == d) or (a == d and b == c). The goal is to return the number of pairs (i, j) where i is less than j and dominoes[i] is equivalent to dominoes[j].

Intuition

The intuition behind the solution is to efficiently count the pairs of equivalent dominoes. To do this, we can represent each domino in a standardized form so that equivalent dominoes will have the same representation, regardless of their orientation. We store the count of each unique domino in a hash map (Counter in Python).

Instead of using a tuple to represent the standardized domino (since [1, 2] is equivalent to [2, 1]), we create a unique integer representation x for each domino by multiplying the larger of the two numbers by 10 and adding the smaller one. This ensures that both [1, 2] and [2, 1] will have the same representation 12.

We then iterate over the list of dominoes and for each domino, we calculate its standardized representation x. We then increment the answer ans by the current count of x already seen (since for each new domino found, it can pair up with all previous identical ones). We update the counter by adding one to the count of x.

This approach allows us to efficiently calculate the number of pairs without the need to explicitly compare each pair of dominoes.

Solution Approach

The solution uses a hash map, implemented as a Counter object in Python, to count occurrences of the standardized representations of dominoes. The hash map allows for quick look-ups and insertions, which is key to the efficiency of this algorithm.

Walking through the implementation:

1. Initialize a Counter object (cnt) which will keep track of the counts of standardized representations of the dominoes.

2. Set ans to 0. This will hold the final count of equivalent pairs.

3. Iterate over each domino in the dominoes list, which is a list of lists where each sublist represents a domino [a, b].

4. For each domino, we create a standardized representation x. If a < b, we construct x by a * 10 + b, otherwise, if b <= a, by b * 10 + a. This step ensures equivalent dominoes have the same representation regardless of order.

5. We add to ans the current count of x from our Counter. This is due to the fact that if we have already seen a domino of this representation, the current one can form a pair with each of those. For instance, if x has a count of 2, and we find another x, we can pair this third one with each of the two previous ones, adding 2 to our ans.

6. We then increment the count of x in our Counter because we've encountered another domino of this type.

The time complexity of the algorithm is O(n), where n is the number of dominoes, since we go through each domino exactly once. The space complexity is O(n) as well, since in the worst case we might have to store a count for each unique domino.

Here is the algorithm translated into Python code:

1class Solution:
2    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
3        cnt = Counter()
4        ans = 0
5        for a, b in dominoes:
6            x = a * 10 + b if a < b else b * 10 + a
7            ans += cnt[x]
8            cnt[x] += 1
9        return ans

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Imagine we have the following list of dominoes:

1dominoes = [[1, 2], [2, 1], [3, 4], [5, 6], [6, 5], [3, 4]]

We want to find pairs of equivalent dominoes. Our approach involves creating a standardized representation for each domino.

1. Initialize the counter object cnt to keep track of domino representations.
2. Set ans to 0.
3. The first domino is [1, 2]. Because 1 < 2, its representation x is 1*10 + 2 = 12.
4. Since this is the first time we see x = 12, cnt[x] is 0 and so we do not add to ans.
5. Increment cnt[12] to 1.

Now, we move on to the second domino:

1. The second domino is [2, 1] which is equivalent to [1, 2]. Its representation is thus 12.
2. Now, as cnt[12] is 1, we add 1 to ans because this new domino can pair with one previous equivalent domino.
3. Increment cnt[12] to 2.

Next, we have [3, 4]:

1. For domino [3, 4], x is 3*10 + 4 = 34.
2. Since this is the first domino of its kind, no addition to ans.
3. Update cnt[34] to 1.

For [5, 6], we set x to 56 and follow the same steps.

Next, consider the domino [6, 5], which is equivalent to [5, 6]:

1. Its standardized form is 56.
2. We find cnt[56] equals 1, so we add 1 to ans.
3. Increment cnt[56] to 2.

Finally, for the second [3, 4] domino:

1. The standardized form is 34.
2. cnt[34] equals 1, so we increment ans by 1.
3. cnt[34] becomes 2.

After processing all the dominoes, our ans value is the sum of additions made which, in this example, is 0 + 1 + 0 + 0 + 1 + 1 = 3. Therefore, there are 3 equivalent pairs of dominoes in the list.

Representing this in Python code according to the given solution approach we have:

1from collections import Counter
2
3class Solution:
4    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
5        cnt = Counter()
6        ans = 0
7        for a, b in dominoes:
8            x = a * 10 + b if a < b else b * 10 + a
9            ans += cnt[x]
10            cnt[x] += 1
11        return ans
12
13# Initial dominoes list
14dominoes = [[1, 2], [2, 1], [3, 4], [5, 6], [6, 5], [3, 4]]
15
16# Instantiate solution and calculate the equivalent pairs
17solution = Solution()
18print(solution.numEquivDominoPairs(dominoes))  # Output: 3

The output, as expected, is 3, meaning we have found three pairs of equivalent dominoes in our list.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code iterates over each domino pair exactly once, which means the primary operation scales linearly with the number of dominoes. Inside the loop, the code performs constant-time operations: a conditional, basic arithmetic operations, and a lookup/update in a Counter data structure (which is a subclass of a dictionary in Python).

Dictionary lookups and updates typically operate in O(1) on average due to hashing. However, in the worst case, if a lot of collisions happen, these operations can degrade to O(n). Since this is unlikely with the hash functions used in modern Python implementations for primitive data types like integers, we will consider the average case for our analysis.

Hence, the time complexity is O(n) where n is the number of domino pairs in the input list, dominoes.

Space Complexity

The space complexity is determined by the additional space used by the algorithm, which is primarily occupied by the Counter object cnt. In the worst case, if all domino pairs are unique after standardization (by sorting each tuple), the counter object will grow linearly with the input. This means we will have a space complexity of O(n).

To summarize, the space complexity is O(n) where n is the number of domino pairs in dominoes.

Learn more about how to find time and space complexity quickly using problem constraints.