1128. Number of Equivalent Domino Pairs

EasyArrayHash TableCounting
Leetcode Link

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1from collections import Counter
2
3class Solution:
4    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
5        # Initialize a counter to keep track of the occurrences of each normalized domino
6        domino_counter = Counter()
7        # Initialize a variable to store the number of equivalent domino pairs
8        equivalent_pairs_count = 0
9      
10        # Iterate over the list of dominoes
11        for domino in dominoes:
12            # Normalize the domino representation to be the same regardless of order
13            # by ensuring the smaller number is in the tens place.
14            normalized_domino = min(domino) * 10 + max(domino)
15          
16            # The current count of the normalized domino in the counter is the number of pairs
17            # that can be formed with the current domino, since all previous occurrences
18            # can form a pair with it.
19            equivalent_pairs_count += domino_counter[normalized_domino]
20          
21            # Increment the count of the normalized domino in the counter
22            domino_counter[normalized_domino] += 1
23      
24        # Return the total count of equivalent domino pairs
25        return equivalent_pairs_count
26```
27
28Remember that `List` needs to be imported from `typing` if you're using a version of Python earlier than 3.9 in which `list` itself is not yet directly usable as a generic type. If you're using Python 3.9 or later, you can omit the import and use `list` with lowercase 'l'.
29
30Here is the import statement for earlier versions of Python:
31
32```python
33from typing import List
34
1class Solution {
2  
3    public int numEquivDominoPairs(int[][] dominoes) {
4        // This array holds the count of normalized representations of dominoes.
5        int[] count = new int[100];
6        int numberOfPairs = 0; // This will store the total number of equivalent domino pairs.
7      
8        // Loop through each domino in the array of dominoes.
9        for (int[] domino : dominoes) {
10            int lesserValue = Math.min(domino[0], domino[1]); // Find the lesser value of the two sides of the domino.
11            int greaterValue = Math.max(domino[0], domino[1]); // Find the greater value of the two sides of the domino.
12
13            // Normalize the representation of the domino so that the
14            // lesser value comes first (e.g., [2,1] becomes [1,2]).
15            int normalizedDomino = lesserValue * 10 + greaterValue;
16
17            // If this normalized domino has been seen before, increment the number of pairs
18            // by the count of how many times the same domino has been encountered. Then,
19            // increment the count for this domino type.
20            numberOfPairs += count[normalizedDomino]++;
21        }
22
23        return numberOfPairs; // Return the total count of equivalent domino pairs.
24    }
25}
26
1class Solution {
2public:
3    // Function to count the number of equivalent domino pairs.
4    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
5        // Array to count occurrences of normalized domino pairs.
6        int count[100] = {0};
7      
8        // Variable to store the number of equivalent domino pairs.
9        int numOfPairs = 0;
10      
11        // Iterate through each domino in the given vector of dominoes.
12        for (auto& domino : dominoes) {
13            // Normalize the domino representation so that
14            // the smaller number comes first (e.g., [2,1] is treated as [1,2]).
15            int normalizedValue = domino[0] < domino[1] 
16                                  ? domino[0] * 10 + domino[1] 
17                                  : domino[1] * 10 + domino[0];
18          
19            // Increment the count for this domino representation.
20            // Since we're finding the number of equivalent pairs, we add
21            // the current count (before incrementing) to 'numOfPairs'
22            numOfPairs += count[normalizedValue]++;
23        }
24      
25        // Return the total number of equivalent domino pairs found.
26        return numOfPairs;
27    }
28};
29
1// Type definition for a dominos pair.
2type Domino = [number, number];
3
4// Global count array to keep track of normalized domino pairs.
5const count: number[] = new Array(100).fill(0);
6
7// Function to count the number of equivalent domino pairs.
8function numEquivDominoPairs(dominoes: Domino[]): number {
9
10    // Variable to store the number of equivalent domino pairs.
11    let numOfPairs: number = 0;
12
13    // Iterate through each domino in the given array of dominoes.
14    for (let domino of dominoes) {
15
16        // Normalize the domino representation so that
17        // the smaller number is the first element (e.g., [2,1] becomes [1,2]).
18        let normalizedValue: number = domino[0] < domino[1] 
19            ? domino[0] * 10 + domino[1]
20            : domino[1] * 10 + domino[0];
21
22        // Increment the count for this normalized domino representation.
23        // Since we're finding the number of equivalent pairs, we add
24        // the current count (before incrementing) to 'numOfPairs'.
25        numOfPairs += count[normalizedValue];
26
27        // Now increment the count for future pairs.
28        count[normalizedValue]++;
29    }
30
31    // Return the total number of equivalent domino pairs found.
32    return numOfPairs;
33}
34
35// Example usage:
36// const dominoes: Domino[] = [[1, 2], [2, 1], [3, 4], [5, 6]];
37// const result: number = numEquivDominoPairs(dominoes);
38// console.log(result); // Output will be the number of equivalent pairs.
39

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.


Recommended Readings