Given a list of dominoes, dominoes[i] = [a, b] 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 < dominoes.length, and dominoes[i] is equivalent to dominoes[j].
Example 1:
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1
Example 2:
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]] Output: 3
Constraints:
1 <= dominoes.length <= 4 * 104dominoes[i].length == 21 <= dominoes[i][j] <= 9Problem Overview: You are given a list of dominoes where each domino is a pair of integers. Two dominoes are equivalent if one can be rotated to match the other, meaning [a,b] is the same as [b,a]. The task is to count how many pairs of equivalent dominoes exist in the array.
Approach 1: Using Hash Map for Count Tracking (O(n) time, O(n) space)
Normalize each domino so that the smaller number comes first: (min(a,b), max(a,b)). This removes the rotation ambiguity and gives every equivalent domino the same canonical representation. Iterate through the array and store frequencies of each normalized domino in a hash map. For every new domino, the number of equivalent pairs it forms equals the current count stored in the map, because each previous identical domino creates a new pair. This approach relies on constant-time hash lookups and works well for general counting problems involving duplicates. It heavily uses concepts from hash tables and counting.
Approach 2: Counting Using Array Indexing (O(n) time, O(1) space)
Domino values are limited to the range 1..9, which allows a compact encoding. Convert each domino into a two-digit number like 10 * min(a,b) + max(a,b). This creates a unique index between 11 and 99 for each normalized domino. Use a fixed array of size 100 to track how many times each encoded domino appears. As you iterate through the dominoes, add the current frequency of that index to the result and then increment the counter. The logic is identical to the hash map approach, but array indexing removes hashing overhead and guarantees constant memory usage. This technique is a specialized optimization of array-based frequency counting.
Recommended for interviews: The hash map counting approach is the most common answer. It clearly demonstrates how to normalize the domino representation and count combinations in linear time. The array indexing variant is slightly more optimized and shows deeper awareness of constraints, but the core insight interviewers expect is the normalization plus frequency counting pattern.
This approach involves using a hash map (or dictionary) to count all the equivalent domino pairs efficiently. For each domino, we convert it to a canonical form where the smaller number comes first. We then use this form as a key in our map to count the occurrences of each pair. For each domino processed, increment the counter by the number of times this key has been seen before.
The function numEquivDominoPairs takes a list dominoes and uses a dictionary count to store the frequency of each canonical domino form. The canonical form is a tuple with elements sorted to handle both orientations of dominoes. As we process each domino, we increment our pairs count by how many times the canonical form has been seen before in count. Finally, we return the total number of pairs found.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(n) to store the frequency of each domino pair.
This approach involves treating domino pairs as numbers to use their hash for direct indexing in an array (similar to a fixed-size hash map). By assigning a unique number to each domino combination using arithmetic, we can efficiently tally counts of equivalent pairs in a fixed-size array.
In this approach, we create an array count with size 100 (based on the possible values of [1-9, 1-9]). For each domino, we compute an integer key to represent it uniquely in both orientations. The key is derived by ensuring the smaller of the two numbers comes first, effectively treating the domino as a two-digit number. We then use this key to incrementally calculate pairs using direct array indexing.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1), as the size of the array is fixed and unrelated to input size.
We can concatenate the two numbers of each domino in order of size to form a two-digit number, so that equivalent dominoes can be concatenated into the same two-digit number. For example, both [1, 2] and [2, 1] are concatenated into the two-digit number 12, and both [3, 4] and [4, 3] are concatenated into the two-digit number 34.
Then we traverse all the dominoes, using an array cnt of length 100 to record the number of occurrences of each two-digit number. For each domino, the two-digit number we concatenate is x, then the answer will increase by cnt[x], and then we add 1 to the value of cnt[x]. Continue to traverse the next domino, and we can count the number of all equivalent domino pairs.
The time complexity is O(n), and the space complexity is O(C). Here, n is the number of dominoes, and C is the maximum number of two-digit numbers concatenated in the dominoes, which is 100.
| Approach | Complexity |
|---|---|
| Using Hash Map for Count Tracking | Time Complexity: O(n), where n is the number of dominoes. |
| Counting Using Array Indexing | Time Complexity: O(n), where n is the number of dominoes. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map for Count Tracking | O(n) | O(n) | General solution when counting normalized pairs or when value ranges are large |
| Array Indexing Frequency Count | O(n) | O(1) | Best when domino values have a small fixed range like 1..9 |
Number of Equivalent Domino Pairs | Multiple Approaches | Dry Run | Leetcode 1128 | codestorywithMIK • codestorywithMIK • 6,234 views views
Watch 9 more video solutions →Practice Number of Equivalent Domino Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor