Number of Equivalent Domino Pairs
EasyPrompt
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: 1Example 2:
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3
Constraints:
1 <= dominoes.length <= 4 * 104dominoes[i].length == 21 <= dominoes[i][j] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of dominoes in the list to see if they are equivalent. It uses two nested loops to iterate through all pairs (i, j) where i < j.
Algorithm
- Initialize a variable
pairsto 0. - Use a nested loop to iterate through all unique pairs of indices
(i, j)wherei < j. - For each pair of dominoes
dominoes[i]anddominoes[j], check for equivalence. - Let
d1 = dominoes[i]andd2 = dominoes[j]. - The dominoes are equivalent if
(d1[0] == d2[0] && d1[1] == d2[1])or(d1[0] == d2[1] && d1[1] == d2[0]). - If they are equivalent, increment the
pairscounter. - After checking all pairs, return the final
pairscount.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We can compare every domino with every other domino that comes after it in the list.
We initialize a counter for the number of equivalent pairs to zero. The outer loop runs from the first domino to the second-to-last domino (index i from 0 to n-2). The inner loop runs from the domino immediately following i to the last domino (index j from i+1 to n-1). This ensures that we only consider each pair (i, j) once and that i is always less than j.
Inside the inner loop, we perform the equivalence check. A domino [a, b] is equivalent to [c, d] if they are identical or if one can be rotated to match the other. This translates to the condition (a == c && b == d) || (a == d && b == c). If this condition is true, we've found an equivalent pair, so we increment our counter. After the loops complete, the counter will hold the total number of such pairs.
class Solution { public int numEquivDominoPairs(int[][] dominoes) { int count = 0; int n = dominoes.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int[] d1 = dominoes[i]; int[] d2 = dominoes[j]; if ((d1[0] == d2[0] && d1[1] == d2[1]) || (d1[0] == d2[1] && d1[1] == d2[0])) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the number of dominoes. The nested loops lead to approximately N^2 / 2 comparisons, which is quadratic.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making it very memory-efficient.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
Solutions
Solution
class Solution { public int numEquivDominoPairs ( int [][] dominoes ) { int [] cnt = new int [ 100 ]; int ans = 0 ; for ( var e : dominoes ) { int x = e [ 0 ] < e [ 1 ] ? e [ 0 ] * 10 + e [ 1 ] : e [ 1 ] * 10 + e [ 0 ]; ans += cnt [ x ]++; } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.