Watch 10 video solutions for Number of Equivalent Domino Pairs, a easy level problem involving Array, Hash Table, Counting. This walkthrough by codestorywithMIK has 6,234 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |