Unlock the Secret to Counting Equivalent Domino Pairs in C++

Efficiently find matching dominoes using clever normalization and counting techniques.

Solving the "Number of Equivalent Domino Pairs" problem efficiently requires a smart approach to handle the equivalence condition where domino orientation doesn't matter. This guide will walk you through an optimal C++ solution.

Key Insights

Standardize Dominoes: Represent each domino [a, b] uniquely, regardless of orientation (e.g., [1, 2] and [2, 1] become the same), typically by ordering the numbers (e.g., always min, max).
Frequency Counting: Use an efficient data structure (like a hash map or a fixed-size array given the constraints) to count how many times each standardized domino appears.
Incremental Pair Calculation: Calculate the number of new pairs formed as you encounter each domino, avoiding a separate calculation step after counting.

Understanding Domino Equivalence

Why Standardization is Crucial

The core challenge lies in the definition of equivalence: [a, b] is the same as [b, a]. If we simply count occurrences of [1, 2] and [2, 1] separately, we won't correctly identify them as forming equivalent pairs. We need a canonical representation.

Creating a Canonical Form

To treat [a, b] and [b, a] identically, we can enforce a consistent order. A simple and effective way is to always place the smaller number first and the larger number second. For example:

[1, 2] becomes (1, 2)
[2, 1] also becomes (1, 2)
[5, 5] becomes (5, 5)
[3, 4] becomes (3, 4)

This ensures that any two equivalent dominoes will map to the exact same standardized form.

Representing dominoes consistently is key to solving the problem.

Generating a Unique Integer Key

While a pair (min_val, max_val) works conceptually, using a single integer key is often more convenient for hash maps or arrays. Given the constraint that domino values are between 1 and 9, we can combine the standardized pair into a unique integer.

A common technique is:

\[ \text{key} = \min(a, b) \times 10 + \max(a, b) \]

Let's see why this works:

[1, 2] -> min(1, 2) * 10 + max(1, 2) = 1 * 10 + 2 = 12
[2, 1] -> min(2, 1) * 10 + max(2, 1) = 1 * 10 + 2 = 12
[3, 4] -> min(3, 4) * 10 + max(3, 4) = 3 * 10 + 4 = 34
[9, 9] -> min(9, 9) * 10 + max(9, 9) = 9 * 10 + 9 = 99
[1, 1] -> min(1, 1) * 10 + max(1, 1) = 1 * 10 + 1 = 11

Since the values range from 1 to 9, the minimum possible key is 11 ([1, 1]) and the maximum is 99 ([9, 9]). Multiplying the smaller number by 10 ensures no overlap; for instance, (1, 2) gives 12, while (2, 1) is standardized to (1, 2) giving 12 as well, and a different pair like (2, 2) gives 22. This creates a unique integer representation for each distinct standardized domino within the range [11, 99].

Example Key Generation Table

This table illustrates how different domino inputs map to the same key if they are equivalent:

Input Domino	Standardized (min, max)	Generated Key (min * 10 + max)
`[1, 2]`	(1, 2)	12
`[2, 1]`	(1, 2)	12
`[5, 5]`	(5, 5)	55
`[3, 4]`	(3, 4)	34
`[4, 3]`	(3, 4)	34
`[9, 1]`	(1, 9)	19

The Algorithm: Counting Pairs Efficiently

Using Frequency Counting

Once we have a way to generate a unique key for each standardized domino, we can count how many times each key appears in the input list. A hash map (std::unordered_map<int, int>) or, given the small range of keys (11-99), a simple fixed-size array (int count[100] = {0};) is suitable for this.

Calculating Pairs Incrementally

Instead of counting all frequencies first and then calculating pairs using the combination formula \( C(f, 2) = \frac{f \times (f - 1)}{2} \) for each frequency \( f \), we can calculate the pairs "on the fly".

Consider iterating through the dominoes. For each domino:

Calculate its standardized key.
Look up the current count of this key in our frequency map/array. Let this be current_count.
This current_count represents the number of equivalent dominoes we have already seen *before* the current one. Each of those previous dominoes forms a pair with the current one. So, we add current_count to our total result.
Increment the frequency count for this key in the map/array to include the current domino.

This way, as we process the k-th occurrence of a specific domino key, we add k-1 to the result (pairing it with the k-1 previous occurrences). Summing these increments correctly calculates the total number of pairs without needing a final combination calculation step.

Example: `[[1,2], [2,1], [1,2]]`

Process [1,2]: Key is 12. count[12] is 0. Add 0 to result. Increment count[12] to 1. result = 0.
Process [2,1]: Key is 12. count[12] is 1. Add 1 to result. Increment count[12] to 2. result = 1. (Pair: first [1,2] and [2,1])
Process [1,2]: Key is 12. count[12] is 2. Add 2 to result. Increment count[12] to 3. result = 1 + 2 = 3. (Pairs: first [1,2] and third [1,2], second [2,1] and third [1,2])

The final result is 3, which matches the formula \( \frac{3 \times (3 - 1)}{2} = 3 \).

C++ Implementation

Efficient Solution using an Array

Given that the keys generated from domino values (1-9) fall within a small, predictable range [11, 99], using a fixed-size array is slightly more memory-efficient and potentially faster than a hash map due to lower overhead.

cpp #include <vector> #include <numeric> // For std::accumulate if needed, though not directly here #include <algorithm> // For std::min, std::max class Solution { public: int numEquivDominoPairs(std::vector<std::vector<int>>& dominoes) { // Array to store counts of each standardized key. Size 100 is sufficient // as keys range from 1*10+1=11 to 9*10+9=99. Initialize all to 0. int count[100] = {0}; int total_pairs = 0; // Accumulator for the result // Iterate through each domino in the input list for (const auto& domino : dominoes) { int val1 = domino[0]; int val2 = domino[1]; // Create the standardized key: smaller number * 10 + larger number int key = std::min(val1, val2) * 10 + std::max(val1, val2); // The number of equivalent dominoes seen *before* this one is count[key]. // Each of those forms a pair with the current domino. total_pairs += count[key]; // Increment the count for this key, reflecting that we've seen one more. count[key]++; } // Return the total accumulated number of pairs return total_pairs; } };

This code efficiently implements the on-the-fly pair counting strategy using a simple array for frequency tracking.

Visualizing the Solution Process

Algorithm Mindmap

This mindmap outlines the key steps involved in solving the Number of Equivalent Domino Pairs problem:

mindmap root["Problem: Count Equivalent Domino Pairs"] id1["Equivalence Definition"] id1_1["[a, b] == [c, d] or [d, c]"] id1_2["Order doesn't matter"] id2["Core Strategy"] id2_1["Standardize Dominoes"] id2_1_1["Sort values: (min, max)"] id2_2["Generate Unique Key"] id2_2_1["Integer Key: min * 10 + max"] id2_2_2["Range: 11 to 99"] id2_3["Count Frequencies"] id2_3_1["Use Hash Map (unordered_map)"] id2_3_2["Use Array (int count[100]) - Efficient for small range"] id2_4["Calculate Pairs"] id2_4_1["On-the-fly Method (preferred)"] id2_4_1_1["result += current_count"] id2_4_1_2["Increment count"] id2_4_2["Combination Formula (alternative)"] id2_4_2_1["Sum C(f, 2) = f*(f-1)/2 after counting"] id3["Implementation (C++)"] id3_1["Loop through dominoes"] id3_2["Calculate key"] id3_3["Update result & count array/map"] id4["Result"] id4_1["Total number of equivalent pairs"]

The mindmap highlights the flow from understanding the problem definition through standardization, key generation, counting, and finally calculating the result.

Approach Comparison: Performance Radar

Hash Map/Array vs. Brute Force

This radar chart compares the recommended Hash Map/Array approach against a naive Brute Force approach (checking every pair of dominoes) across several dimensions. The Hash Map/Array method clearly outperforms Brute Force, especially in time complexity and scalability.

The Hash Map/Array approach offers significantly better time complexity (O(n) vs O(n^2)) and scalability, making it the preferred method for the given constraints. While brute force might seem slightly simpler initially, its inefficiency makes it impractical for larger datasets.

Example Walkthroughs

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

Initialize count = {0} (array of 100 zeros), total_pairs = 0.
Domino [1,2]: Key = min(1,2)*10 + max(1,2) = 12. total_pairs += count[12] (0). total_pairs = 0. Increment count[12] to 1.
Domino [2,1]: Key = min(2,1)*10 + max(2,1) = 12. total_pairs += count[12] (1). total_pairs = 1. Increment count[12] to 2.
Domino [3,4]: Key = min(3,4)*10 + max(3,4) = 34. total_pairs += count[34] (0). total_pairs = 1. Increment count[34] to 1.
Domino [5,6]: Key = min(5,6)*10 + max(5,6) = 56. total_pairs += count[56] (0). total_pairs = 1. Increment count[56] to 1.

Final Result: 1

Example 2: `dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]`

Initialize count = {0}, total_pairs = 0.
Domino [1,2]: Key = 12. total_pairs += count[12] (0). total_pairs = 0. Increment count[12] to 1.
Domino [1,2]: Key = 12. total_pairs += count[12] (1). total_pairs = 1. Increment count[12] to 2.
Domino [1,1]: Key = min(1,1)*10 + max(1,1) = 11. total_pairs += count[11] (0). total_pairs = 1. Increment count[11] to 1.
Domino [1,2]: Key = 12. total_pairs += count[12] (2). total_pairs = 1 + 2 = 3. Increment count[12] to 3.
Domino [2,2]: Key = min(2,2)*10 + max(2,2) = 22. total_pairs += count[22] (0). total_pairs = 3. Increment count[22] to 1.

Final Result: 3

Video Explanation

Visualizing the Counting Strategy

For a more visual explanation of counting pairs and handling similar problems, this video provides helpful insights into different approaches, including the use of frequency counting.

This video discusses the "Number of Equivalent Domino Pairs" problem, covering multiple approaches and providing a dry run, which can solidify understanding of the counting logic.

Complexity Analysis

Time Complexity: O(n), where n is the number of dominoes. We iterate through the dominoes list exactly once. Calculating the key, accessing the array/map, and updating the count/result are all O(1) operations on average.
Space Complexity: O(1). When using the fixed-size array count[100], the space required is constant and does not depend on the number of dominoes n. Even if using an unordered_map, the maximum number of distinct keys is limited by the number of possible pairs from 1 to 9 (which is \( 9 + \binom{9}{2} = 9 + 36 = 45 \), well within a constant bound), making the space complexity effectively O(1) in this specific problem context.

Frequently Asked Questions (FAQ)

Why is standardization necessary?

Standardization ensures that dominoes considered equivalent (like [1, 2] and [2, 1]) are treated as the same item when counting. Without it, you would count them separately and miss the pairs formed between them. Creating a canonical form (e.g., always sorting the numbers (min, max)) allows us to group all equivalent dominoes under a single representation.

How does the `min * 10 + max` key work reliably?

This works because the numbers are single digits (1-9). Multiplying the minimum value by 10 effectively shifts it to the "tens" place, while the maximum value occupies the "units" place. Since `max` is always less than 10, it never interferes with the tens place created by `min * 10`. This guarantees a unique integer for every distinct pair `(min, max)` within the range 1-9. For example, `(1, 9)` -> 19, `(2, 2)` -> 22, `(3, 1)` standardizes to `(1, 3)` -> 13.

Explain the "on-the-fly" pair counting logic again.

When you encounter the `k`-th instance of a particular standardized domino key, it means you have already seen `k-1` identical/equivalent dominoes before. The current domino can form a pair with each of those `k-1` previous dominoes. By adding the current count (`k-1`) to the `total_pairs` *before* incrementing the count to `k`, you correctly sum up all the new pairs formed by the current domino. Summing these increments over the entire list gives the total number of pairs. It's equivalent to calculating \( \sum \frac{f \times (f-1)}{2} \) for the final frequencies \( f \), but integrated into the counting loop.

Could I use `std::map` instead of `std::unordered_map` or an array?

Yes, you could use `std::map`. However, `std::map` provides O(log k) lookups/insertions (where k is the number of unique keys), whereas `std::unordered_map` provides average O(1) time. Given the small, fixed range of keys, a simple array `int count[100]` offers the best performance (guaranteed O(1) access) and simplicity for this specific problem. `std::unordered_map` is a good general choice if the key range wasn't small or predictable. `std::map` would be less efficient here.