Number of Equivalent Domino Pairs

Problem Statement

LeetCode-1128: Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either both are same or one can be rotated to be equal to the other. $$(a==candb==d),OR(a==dandb==c)$$

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Approach

This problem is about finding equivalent domino pairs in a list of dominoes where two dominoes are considered equivalent if they have the same values (possibly in reversed order).

For each domino [a,b], we can create a standardized key by ensuring $a\le b$. After counting all dominoes, we need to calculate how many pairs can be formed when the frequency of a specific domino is greater than 1.

Consider the following example: [[1,2],[2,1],[3,4],[5,6]]

1. Normalize each domino
   • [1,2] is already normalized since 1 < 2
   • [2,1] normalizes to [1,2]
   • [3,4] is already normalized
   • [5,6] is already normalized
2. Count frequency:
   • [1,2]: 2 occurrences
   • [3,4]: 1 occurrence
   • [5,6]: 1 occurrence
3. Calculate pairs
   1. For [1,2] with frequency 2, we can form C(2,2) = 1 pair
   2. Others have frequency 1, so 0 pairs

Additionally, based on the constraint 1 <= dominoes[i][j] <= 9, we can use a fixed-size array to count the occurrences of each domino. This will help us avoid using a dictionary and make the solution more efficient.

Implementation

public int numEquivDominoPairs(int[][] dominoes) {
    int ans = 0;
    int[] freq = new int[100];

    for(int[] pair : dominoes){
        // normalize the dominos
        // so that the smaller number is always first
        // e.g. [1,2] and [2,1] both become 12
        // [3,4] becomes 34
        // this way we can use the same index for both the flavors
        int val = pair[0] < pair[1] ? 
                    pair[0]*10 + pair[1] :
                    pair[1]*10 + pair[0];

        ans+= freq[val];                      
        freq[val]++;
    }

    return ans;
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of dominoes. We iterate through the list once to count the frequencies and then calculate the pairs.
• Space Complexity: O(1), since the frequency array has a fixed size of 100, which is independent of the input size.