algoadvance

Leetcode 1128. Number of Equivalent Domino Pairs

Problem Statement:

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if:

1. ( a == c ) and ( b == d ), or
2. ( a == d ) and ( b == c )

i.e., one is simply a rotation of the other.

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

Clarifying Questions:

1. Input Size: What is the range of the input size?
   • The input list of dominoes can be fairly large, up to (10^4) domino pairs.
2. Domino Values: What are the potential values for a and b in the dominoes?
   • Each value in the dominoes ranges from 1 to 9.
3. Order of Pairs: Does the order of values in dominoes[i] matter?
   • Yes, but since the problem considers equivalent dominoes to be rotations, [1,2] and [2,1] are considered equivalent.

Strategy:

1. Normalize Each Domino: For each domino [a, b], treat it as [min(a, b), max(a, b)] to create a normalized form.

2. Count Dominoes: Use a hashmap to count occurrences of each normalized domino.

3. Calculate Pairs: The number of ways to pick 2 out of n same items is given by the combination formula C(n, 2) which is n * (n - 1) / 2. Use this formula to calculate the number of equivalent pairs for each count in the hashmap.

With these steps, we can ensure an efficient solution.

Code:

import java.util.HashMap;
import java.util.Map;

public class DominosEquivalentPairs {
    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int numPairs = 0;

        for (int[] domino : dominoes) {
            int key = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];
            countMap.put(key, countMap.getOrDefault(key, 0) + 1);
        }

        for (int count : countMap.values()) {
            if (count > 1) {
                numPairs += count * (count - 1) / 2;
            }
        }

        return numPairs;
    }

    public static void main(String[] args) {
        DominosEquivalentPairs sol = new DominosEquivalentPairs();
        int[][] dominoes = \ use example from above
        System.out.println(sol.numEquivDominoPairs(dominoes)); // Output: 1
    }
}

Time Complexity:

• The time complexity of this solution is (O(n)), where (n) is the number of dominos. We make a single pass over the array to populate the map and another pass over the map to compute the result.
• Space complexity is (O(d)), where (d) is the number of distinct domino pairs. Since each pair is represented as an integer between 11 and 99, the maximum number of distinct pairs is manageable.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?