Number of Equivalent Domino Pairs

This problem can be solved by iterating through each domino and normalizing it to a canonical form, such as sorted values. Maintain a hash map to count occurrences of each normalized domino. For each domino, the number of previously seen equivalent dominoes adds directly to the result, ensuring an O(n) solution without redundant pair comparisons.

Problem Statement

You are given a list of dominoes, where each domino is represented as a two-element array [a, b]. Two dominoes are considered equivalent if one can be rotated to match the other, meaning [a, b] is equivalent to [c, d] if a == c and b == d, or a == d and b == c.

Return the total number of pairs (i, j) with 0 <= i < j < dominoes.length where dominoes[i] is equivalent to dominoes[j]. For example, given dominoes = [[1,2],[2,1],[3,4],[5,6]], the correct output is 1 because only the first two dominoes form an equivalent pair.

Examples

Example 1

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

Output: 1

Example details omitted.

Example 2

Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]

Output: 3

Example details omitted.

Constraints

• 1 <= dominoes.length <= 4 * 104
• dominoes[i].length == 2
• 1 <= dominoes[i][j] <= 9

Solution Approach

Normalize dominoes for consistent comparison

For each domino [a, b], sort the pair or choose a canonical representation (min(a,b), max(a,b)). This ensures equivalent dominoes map to the same key in a hash map, allowing consistent counting.

Use a hash map to count occurrences

Maintain a hash map where each key is a normalized domino and the value is the number of times it has appeared. Increment the count for the key each time a new domino is processed.

Compute pairs using previously seen counts

For each domino, add the current count of its normalized key in the hash map to the result. This counts all previous dominoes equivalent to the current one efficiently in a single pass.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each domino is processed once, and hash map operations are O(1). Space complexity is O(1) in practice since there are at most 45 possible domino combinations, making the hash map size effectively constant.

What Interviewers Usually Probe

• Looks for hash-based counting for array elements
• Wants O(n) solution without nested loops
• Checks for canonical representation handling rotations

Common Pitfalls or Variants

Common pitfalls

• Forgetting to normalize dominoes before hashing, leading to missed pairs
• Using nested loops, causing O(n^2) time instead of O(n)
• Not accounting for all previously seen equivalent dominoes correctly in the count

Follow-up variants

• Counting equivalent pairs with more than two elements per domino
• Finding the maximum number of equivalent domino groups instead of pairs
• Allowing domino values larger than single digits

FAQ

How does the array scanning plus hash lookup pattern apply here?

Each domino is converted to a canonical form and stored in a hash map; scanning the array while updating counts allows direct pair calculation.

Can this approach handle very large arrays of dominoes?

Yes, because the solution is O(n) time with a small, bounded hash map, making it efficient even for large inputs.

Why do we need to normalize dominoes?

Normalization ensures that equivalent dominoes like [2,1] and [1,2] map to the same key, allowing correct counting of pairs.

What is the maximum number of unique domino keys we can have?

Since domino values are between 1 and 9, there are at most 45 unique normalized domino keys.

How do we count pairs without iterating all pairs?

Use the hash map counts: for each domino, add the current count of its normalized key to the total, capturing all previous equivalent dominoes efficiently.