Jobs

Interviews

Discussions

Number of Equivalent Domino Pairs

Easy

Asked by:

16 views

Topics:

Arrays

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 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

Try coding it in LeetCode

Number of Equivalent Domino Pairs

Easy

Asked by:

16 views

Topics:

Arrays

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 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers within each domino pair? Could they be negative, zero, or very large?
What is the maximum number of domino pairs that can be present in the input array?
If there are no equivalent domino pairs, should I return 0, or is there a specific error code I should return?
Does the order of the numbers within a domino matter when determining equivalence (e.g., is [1, 2] equivalent to [2, 1])?
Are there any memory constraints I should be aware of given the potential size of the input?

Brute Force Solution

Approach

We're given a set of dominoes and need to find how many pairs are equivalent. The brute force approach will simply compare each domino to every other domino to see if they're the same.

Here's how the algorithm would work step-by-step:

Take the first domino in the set.
Compare it to every other domino in the set, one at a time.
If a domino is the same as the first domino (either in the same order or with the numbers flipped), mark that we found a matching pair.
Move on to the next domino in the original set.
Again, compare it to every other domino in the set.
Keep track of how many equivalent pairs we find in total. Note, that you may want to avoid re-counting any pairs.

Code Implementation

def num_equiv_domino_pairs(dominoes):
   number_of_pairs = 0
   number_of_dominoes = len(dominoes)

   # Iterate through each domino in the list
   for first_domino_index in range(number_of_dominoes):
       for second_domino_index in range(first_domino_index + 1, number_of_dominoes):
           # Ensure we don't compare a domino to itself.

           first_domino = dominoes[first_domino_index]
           second_domino = dominoes[second_domino_index]

           # Check if dominoes are equivalent.
           if (first_domino[0] == second_domino[0] and first_domino[1] == second_domino[1]) or \
              (first_domino[0] == second_domino[1] and first_domino[1] == second_domino[0]):
               number_of_pairs += 1

   return number_of_pairs

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the input array of dominoes of size n. For each domino, it compares it to every other domino in the set to check for equivalence. This involves a nested loop structure where the outer loop iterates n times, and the inner loop, in the worst case, also iterates close to n times. Therefore, the number of comparisons grows proportionally to n multiplied by n, resulting in approximately n*n comparisons. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The algorithm iterates through the input dominoes and compares each domino to every other. It does not use any additional data structures like arrays, hash maps, or sets to store intermediate results or track visited pairs. The only extra memory used involves a few integer variables for indexing and counting the number of equivalent pairs, and these variables take up a constant amount of space regardless of the number of dominoes, denoted as N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key is to realize that the order within a domino pair doesn't matter, so we can treat pairs like [1, 2] and [2, 1] as identical. We can count how many of each unique domino pair we have and then use that to quickly calculate the number of equivalent pairs.

Here's how the algorithm would work step-by-step:

First, we want to consider pairs like [1, 2] and [2, 1] as the same. To do this, for each pair we see, we put the smaller number first.
Next, we need a way to count how many times we see each domino pair. We'll keep track of each unique domino pair and how many times it shows up.
Now, for each unique domino pair we found, if we saw it 'n' times, that means there are n * (n - 1) / 2 pairs of equivalent domino pairs.
Add up this calculation for each unique domino pair, and the final sum is the total number of equivalent domino pairs.

Code Implementation

def number_of_equivalent_domino_pairs(dominoes):    domino_counts = {}
    equivalent_pair_count = 0

    for domino in dominoes:
        # Ensure consistent ordering for equivalent pairs
        domino.sort()
        domino_tuple = tuple(domino)

        # Count frequency of each domino pair
        if domino_tuple in domino_counts:
            domino_counts[domino_tuple] += 1
        else:
            domino_counts[domino_tuple] = 1

    for count in domino_counts.values():
        # Calculate equivalent pairs using n * (n - 1) / 2
        equivalent_pair_count += count * (count - 1) // 2

    return equivalent_pair_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of dominoes of size 'n' once. Inside the loop, each domino pair is normalized by ensuring the smaller value comes first which takes constant time. A hash map (or similar data structure) is used to count the occurrences of each unique domino pair. Updating the count in the hash map takes approximately constant time on average. The final step iterates through the unique domino pair counts which is bounded by 'n' and applies a constant time calculation to each. Therefore, the dominant operation is the single loop through the 'n' dominoes, giving an overall time complexity of O(n).

Space Complexity

O(1) – The solution uses a hash map (or similar data structure) to count the occurrences of each unique domino pair. In the worst case, where all domino pairs are unique, the size of this hash map could grow proportionally to the number of dominoes, N. However, since each domino only contains numbers from 1 to 9, there are only 9 * 9 = 81 possible domino pairs (considering that [a, b] is the same as [b, a]). Thus, the hash map's size is bounded by a constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or Empty input array	Return 0 immediately, as there are no pairs possible.
Input array with only one domino	Return 0 because at least two dominoes are needed for a pair.
Input array with a large number of dominoes, exceeding available memory	The frequency counting approach is used which should scale well within memory limits by tracking occurrences instead of storing all combinations.
All dominoes in the input array are identical (e.g., all [1, 2])	The frequency counting approach correctly counts pairs when all dominoes are the same.
Dominos where both numbers are the same: [1, 1], [2, 2], etc.	The solution correctly accounts for such cases when calculating pair frequencies, as (i, j) is equivalent to (j, i) even when i == j.
Input contains very large numbers for domino values exceeding practical limits.	The number of equivalent domino pairs counts occurrences, so large domino values should not cause issues unless memory becomes a constraint.
Input with only one distinct type of domino pair.	The algorithm will correctly identify all the pairs of that one domino type and compute the count using the combinatorics formula.
Integer overflow when calculating the number of pairs (n*(n-1))/2 for a large number of duplicate dominoes.	Use a larger data type (e.g., long) for counting the pairs to prevent overflow during the calculation.

Null or Empty input array

How to Handle:

Return 0 immediately, as there are no pairs possible.

Input array with only one domino

How to Handle:

Return 0 because at least two dominoes are needed for a pair.

Input array with a large number of dominoes, exceeding available memory

How to Handle:

The frequency counting approach is used which should scale well within memory limits by tracking occurrences instead of storing all combinations.

All dominoes in the input array are identical (e.g., all [1, 2])

How to Handle:

The frequency counting approach correctly counts pairs when all dominoes are the same.

Dominos where both numbers are the same: [1, 1], [2, 2], etc.

How to Handle:

The solution correctly accounts for such cases when calculating pair frequencies, as (i, j) is equivalent to (j, i) even when i == j.

Input contains very large numbers for domino values exceeding practical limits.

How to Handle:

The number of equivalent domino pairs counts occurrences, so large domino values should not cause issues unless memory becomes a constraint.

Input with only one distinct type of domino pair.

How to Handle:

The algorithm will correctly identify all the pairs of that one domino type and compute the count using the combinatorics formula.

Integer overflow when calculating the number of pairs (n*(n-1))/2 for a large number of duplicate dominoes.

How to Handle:

Use a larger data type (e.g., long) for counting the pairs to prevent overflow during the calculation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers within each domino pair? Could they be negative, zero, or very large?
What is the maximum number of domino pairs that can be present in the input array?
If there are no equivalent domino pairs, should I return 0, or is there a specific error code I should return?
Does the order of the numbers within a domino matter when determining equivalence (e.g., is [1, 2] equivalent to [2, 1])?
Are there any memory constraints I should be aware of given the potential size of the input?

Brute Force Solution

Approach

We're given a set of dominoes and need to find how many pairs are equivalent. The brute force approach will simply compare each domino to every other domino to see if they're the same.

Here's how the algorithm would work step-by-step:

Take the first domino in the set.
Compare it to every other domino in the set, one at a time.
If a domino is the same as the first domino (either in the same order or with the numbers flipped), mark that we found a matching pair.
Move on to the next domino in the original set.
Again, compare it to every other domino in the set.
Keep track of how many equivalent pairs we find in total. Note, that you may want to avoid re-counting any pairs.

Code Implementation

def num_equiv_domino_pairs(dominoes):
   number_of_pairs = 0
   number_of_dominoes = len(dominoes)

   # Iterate through each domino in the list
   for first_domino_index in range(number_of_dominoes):
       for second_domino_index in range(first_domino_index + 1, number_of_dominoes):
           # Ensure we don't compare a domino to itself.

           first_domino = dominoes[first_domino_index]
           second_domino = dominoes[second_domino_index]

           # Check if dominoes are equivalent.
           if (first_domino[0] == second_domino[0] and first_domino[1] == second_domino[1]) or \
              (first_domino[0] == second_domino[1] and first_domino[1] == second_domino[0]):
               number_of_pairs += 1

   return number_of_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we want to consider pairs like [1, 2] and [2, 1] as the same. To do this, for each pair we see, we put the smaller number first.
Next, we need a way to count how many times we see each domino pair. We'll keep track of each unique domino pair and how many times it shows up.
Now, for each unique domino pair we found, if we saw it 'n' times, that means there are n * (n - 1) / 2 pairs of equivalent domino pairs.
Add up this calculation for each unique domino pair, and the final sum is the total number of equivalent domino pairs.

Code Implementation

def number_of_equivalent_domino_pairs(dominoes):    domino_counts = {}
    equivalent_pair_count = 0

    for domino in dominoes:
        # Ensure consistent ordering for equivalent pairs
        domino.sort()
        domino_tuple = tuple(domino)

        # Count frequency of each domino pair
        if domino_tuple in domino_counts:
            domino_counts[domino_tuple] += 1
        else:
            domino_counts[domino_tuple] = 1

    for count in domino_counts.values():
        # Calculate equivalent pairs using n * (n - 1) / 2
        equivalent_pair_count += count * (count - 1) // 2

    return equivalent_pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty input array	Return 0 immediately, as there are no pairs possible.
Input array with only one domino	Return 0 because at least two dominoes are needed for a pair.
Input array with a large number of dominoes, exceeding available memory	The frequency counting approach is used which should scale well within memory limits by tracking occurrences instead of storing all combinations.
All dominoes in the input array are identical (e.g., all [1, 2])	The frequency counting approach correctly counts pairs when all dominoes are the same.
Dominos where both numbers are the same: [1, 1], [2, 2], etc.	The solution correctly accounts for such cases when calculating pair frequencies, as (i, j) is equivalent to (j, i) even when i == j.
Input contains very large numbers for domino values exceeding practical limits.	The number of equivalent domino pairs counts occurrences, so large domino values should not cause issues unless memory becomes a constraint.
Input with only one distinct type of domino pair.	The algorithm will correctly identify all the pairs of that one domino type and compute the count using the combinatorics formula.
Integer overflow when calculating the number of pairs (n*(n-1))/2 for a large number of duplicate dominoes.	Use a larger data type (e.g., long) for counting the pairs to prevent overflow during the calculation.

Null or Empty input array

How to Handle:

Return 0 immediately, as there are no pairs possible.

Input array with only one domino

How to Handle:

Return 0 because at least two dominoes are needed for a pair.

Input array with a large number of dominoes, exceeding available memory

How to Handle:

The frequency counting approach is used which should scale well within memory limits by tracking occurrences instead of storing all combinations.

All dominoes in the input array are identical (e.g., all [1, 2])

How to Handle:

The frequency counting approach correctly counts pairs when all dominoes are the same.

Dominos where both numbers are the same: [1, 1], [2, 2], etc.

How to Handle:

The solution correctly accounts for such cases when calculating pair frequencies, as (i, j) is equivalent to (j, i) even when i == j.

Input contains very large numbers for domino values exceeding practical limits.

How to Handle:

The number of equivalent domino pairs counts occurrences, so large domino values should not cause issues unless memory becomes a constraint.

Input with only one distinct type of domino pair.

How to Handle:

The algorithm will correctly identify all the pairs of that one domino type and compute the count using the combinatorics formula.

Integer overflow when calculating the number of pairs (n*(n-1))/2 for a large number of duplicate dominoes.

How to Handle:

Use a larger data type (e.g., long) for counting the pairs to prevent overflow during the calculation.