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:
-
Initialize a
Counter
object (cnt
) which will keep track of the counts of standardized representations of the dominoes. -
Set
ans
to0
. This will hold the final count of equivalent pairs. -
Iterate over each domino in the
dominoes
list, which is a list of lists where each sublist represents a domino[a, b]
. -
For each domino, we create a standardized representation
x
. Ifa < b
, we constructx
bya * 10 + b
, otherwise, ifb <= a
, byb * 10 + a
. This step ensures equivalent dominoes have the same representation regardless of order. -
We add to
ans
the current count ofx
from ourCounter
. 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, ifx
has a count of 2, and we find anotherx
, we can pair this third one with each of the two previous ones, adding 2 to ourans
. -
We then increment the count of
x
in ourCounter
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 EvaluatorExample 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.
- Initialize the counter object
cnt
to keep track of domino representations. - Set
ans
to 0. - The first domino is
[1, 2]
. Because1 < 2
, its representationx
is1*10 + 2 = 12
. - Since this is the first time we see
x = 12
,cnt[x]
is 0 and so we do not add toans
. - Increment
cnt[12]
to 1.
Now, we move on to the second domino:
- The second domino is
[2, 1]
which is equivalent to[1, 2]
. Its representation is thus12
. - Now, as
cnt[12]
is 1, we add 1 toans
because this new domino can pair with one previous equivalent domino. - Increment
cnt[12]
to 2.
Next, we have [3, 4]
:
- For domino
[3, 4]
,x
is3*10 + 4 = 34
. - Since this is the first domino of its kind, no addition to
ans
. - 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]
:
- Its standardized form is
56
. - We find
cnt[56]
equals 1, so we add 1 toans
. - Increment
cnt[56]
to 2.
Finally, for the second [3, 4]
domino:
- The standardized form is
34
. cnt[34]
equals 1, so we incrementans
by 1.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.
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time