Problem Description

You are given a list of dominoes where each domino is represented as a pair of integers [a, b]. Two dominoes are considered equivalent if one can be rotated to match the other. Specifically, domino [a, b] is equivalent to domino [c, d] if:

• Either a == c and b == d (they are exactly the same)
• Or a == d and b == c (one is the rotated version of the other)

For example, [1, 2] and [2, 1] are equivalent dominoes because rotating [2, 1] gives us [1, 2].

Your task is to count the number of pairs (i, j) where i < j and dominoes[i] is equivalent to dominoes[j].

The solution uses a clever counting approach. It normalizes each domino by creating a two-digit number where the smaller value is always placed first. For instance, both [1, 2] and [2, 1] would be converted to the number 12 (since 1 < 2). Similarly, [3, 4] and [4, 3] would both become 34.

As we iterate through the dominoes:

1. For each domino, we create its normalized representation x
2. We add the current count of x to our answer (this represents all previous equivalent dominoes we can pair with)
3. We increment the count for x by 1 for future dominoes to pair with

This way, we efficiently count all pairs of equivalent dominoes in a single pass through the array.

Intuition

The key insight is recognizing that equivalent dominoes are essentially the same piece, just potentially rotated. When counting pairs, we need a way to identify which dominoes are equivalent regardless of their orientation.

Think about it this way: if you have a physical domino with numbers [1, 2], you can place it as either [1, 2] or [2, 1] by rotating it. They're the same domino! So we need a way to give both orientations the same "identity."

The natural approach is to create a canonical form for each domino - a standard way to represent it regardless of rotation. We can achieve this by always arranging the numbers in a consistent order, like smallest first. This way, both [1, 2] and [2, 1] become (1, 2) in our canonical form.

Once we have this canonical representation, counting pairs becomes straightforward. As we process each domino:

• We check how many dominoes with the same canonical form we've seen before
• Each of those previously seen dominoes can form a pair with the current one
• We then record that we've seen one more domino of this type

The formula a * 10 + b (where a < b) is just a clever way to create a unique identifier for each canonical form. Since domino values are single digits (0-9), multiplying the first by 10 and adding the second creates a unique two-digit number. For example, [1, 2] becomes 12, and [3, 4] becomes 34. This makes it easy to use a counter or array to track occurrences.

The beauty of this approach is that we only need one pass through the array, making it efficient with O(n) time complexity.

Solution Approach

The solution uses a counting approach with hash map to efficiently track equivalent dominoes.

Data Structure: We use a Counter (hash map) to store the frequency of each normalized domino representation.

Algorithm Steps:

1. Initialize variables:

   • cnt: A Counter to track occurrences of each normalized domino
   • ans: Running total of equivalent pairs, initially 0

2. Process each domino: For each domino [a, b] in the input:

   a. Normalize the domino: Create a canonical representation by ensuring the smaller number comes first:

   x = a * 10 + b if a < b else b * 10 + a

   This converts the domino into a unique two-digit number. For example:

   • [1, 2] → 12
   • [2, 1] → 12 (same as above)
   • [3, 4] → 34

   b. Count pairs with previous dominoes:

   ans += cnt[x]

   If we've seen cnt[x] dominoes with the same normalized form before, the current domino can form cnt[x] pairs with them.

   c. Update the counter:

   cnt[x] += 1

   Record that we've now seen one more domino with this normalized form.

3. Return the result: After processing all dominoes, ans contains the total number of equivalent pairs.

Example Walkthrough:

Consider dominoes = [[1,2], [2,1], [3,4], [1,2]]

• Process [1,2]: x = 12, ans += 0 (no previous 12s), cnt[12] = 1
• Process [2,1]: x = 12, ans += 1 (one previous 12), cnt[12] = 2
• Process [3,4]: x = 34, ans += 0 (no previous 34s), cnt[34] = 1
• Process [1,2]: x = 12, ans += 2 (two previous 12s), cnt[12] = 3

Final answer: 3 pairs

Time Complexity: O(n) where n is the number of dominoes
Space Complexity: O(n) for the counter in worst case when all dominoes are unique

Example Walkthrough

Let's walk through the solution with dominoes = [[1,2], [3,4], [2,1], [1,2], [4,3]]

Initial State:

• cnt = {} (empty counter)
• ans = 0 (no pairs found yet)

Step 1: Process [1,2]

• Normalize: Since 1 < 2, we get x = 1*10 + 2 = 12
• Add pairs: ans += cnt[12] = 0 (no previous dominoes with value 12)
• Update counter: cnt[12] = 1
• State: cnt = {12: 1}, ans = 0

Step 2: Process [3,4]

• Normalize: Since 3 < 4, we get x = 3*10 + 4 = 34
• Add pairs: ans += cnt[34] = 0 (no previous dominoes with value 34)
• Update counter: cnt[34] = 1
• State: cnt = {12: 1, 34: 1}, ans = 0

Step 3: Process [2,1]

• Normalize: Since 2 > 1, we get x = 1*10 + 2 = 12 (same as [1,2]!)
• Add pairs: ans += cnt[12] = 1 (found 1 previous domino to pair with)
• Update counter: cnt[12] = 2
• State: cnt = {12: 2, 34: 1}, ans = 1

Step 4: Process [1,2]

• Normalize: Since 1 < 2, we get x = 1*10 + 2 = 12
• Add pairs: ans += cnt[12] = 2 (found 2 previous dominoes to pair with)
• Update counter: cnt[12] = 3
• State: cnt = {12: 3, 34: 1}, ans = 3

Step 5: Process [4,3]

• Normalize: Since 4 > 3, we get x = 3*10 + 4 = 34 (same as [3,4]!)
• Add pairs: ans += cnt[34] = 1 (found 1 previous domino to pair with)
• Update counter: cnt[34] = 2
• State: cnt = {12: 3, 34: 2}, ans = 4

Final Answer: 4 pairs

The pairs are:

• (0,2): [1,2] and [2,1]
• (0,3): [1,2] and [1,2]
• (1,4): [3,4] and [4,3]
• (2,3): [2,1] and [1,2]

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of dominoes. The algorithm iterates through the dominoes list exactly once, and for each domino, it performs constant-time operations: creating a normalized key x, accessing and updating the counter, and adding to the answer.

The space complexity is O(C), where C represents the maximum number of distinct normalized domino representations possible. Since each domino [a, b] is normalized to a two-digit number (with the smaller value as tens digit and larger value as units digit), and both a and b range from 0 to 9, there are at most 10 × 10 = 100 possible distinct keys in the counter. Therefore, C = 100, making the space complexity O(100) or simply O(1) in terms of constant space relative to the input constraints.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Normalization Logic

A common mistake is incorrectly normalizing the domino representation, which can lead to collisions or incorrect equivalence detection.

Pitfall Example:

# Wrong: Simple addition doesn't uniquely identify dominoes
normalized_key = first_val + second_val  # [1,3] and [2,2] both give 4!

# Wrong: Concatenation without proper multiplication
normalized_key = str(min(first_val, second_val)) + str(max(first_val, second_val))
# This creates strings, not numbers, affecting performance and storage

Solution: Always use a multiplication factor that ensures unique representation:

normalized_key = min(first_val, second_val) * 10 + max(first_val, second_val)

2. Overflow Risk with Large Values

If domino values can be larger than single digits, the multiplication by 10 won't work correctly.

Pitfall Example:

# If dominoes can have values like [12, 5]
normalized_key = 5 * 10 + 12  # Gives 62
# But [6, 2] also gives 62!

Solution: For larger values, use tuples as keys or a larger multiplication factor:

# Option 1: Use tuples (more general)
normalized_key = (min(first_val, second_val), max(first_val, second_val))

# Option 2: Use appropriate multiplication factor
max_val = 100  # If values go up to 99
normalized_key = min(first_val, second_val) * max_val + max(first_val, second_val)

3. Not Handling the Counting Logic Correctly

Some might try to count all pairs at once after collecting frequencies, leading to incorrect results or double counting.

Pitfall Example:

# Wrong approach: Counting pairs after collecting all frequencies
for domino in dominoes:
    normalized_key = ...
    domino_count[normalized_key] += 1

# Then trying to calculate pairs
for count in domino_count.values():
    total_pairs += count * (count - 1) // 2  # This works but less efficient

Solution: The incremental counting approach in the original solution is both elegant and efficient - it counts pairs as we go, avoiding the need for a second pass.

4. Forgetting Edge Cases

Not considering special cases like dominoes with equal values.

Pitfall Example:

# Forgetting that [2,2] should be treated the same way
if first_val != second_val:  # Wrong: unnecessary special case
    normalized_key = min(first_val, second_val) * 10 + max(first_val, second_val)
else:
    normalized_key = first_val * 10 + second_val

Solution: The normalization logic should work uniformly for all cases:

# This works for both [2,2] and [1,2] cases
normalized_key = min(first_val, second_val) * 10 + max(first_val, second_val)