How do you solve Number of Equivalent Domino Pairs on LeetCode?

Number of Equivalent Domino Pairs (LeetCode #1128) can be solved using Brute Force. The optimal approach is Brute Force with O(n²) time complexity and O(1) space complexity. Key insight: The brute force approach checks every possible pair of dominoes to see if they are equivalent. This is straightforward but inefficient, as it involves nested loops to compare each domino with every other domino.

What algorithm or data structure is used to solve Number of Equivalent Domino Pairs?

Number of Equivalent Domino Pairs uses the following concepts: Array, Hash Table, Counting. The recommended patterns to study are: .

#1128

Number of Equivalent Domino Pairs

Easy

ArrayHash TableCounting

LeetCode ↗

Approaches

💡

Intuition

Time O(n²)Space O(1)

The brute force approach checks every possible pair of dominoes to see if they are equivalent. This is straightforward but inefficient, as it involves nested loops to compare each domino with every other domino.

⚙️

Algorithm

5 steps

1Step 1: Initialize a counter to zero for counting equivalent pairs.
2Step 2: Use two nested loops to iterate through all pairs of dominoes.
3Step 3: For each pair, check if they are equivalent by comparing their values in both possible orders.
4Step 4: If they are equivalent, increment the counter.
5Step 5: Return the counter after checking all pairs.

solution.py14 lines

1# Full working Python code
2
3def numEquivDominoPairs(dominoes):
4    count = 0
5    n = len(dominoes)
6    for i in range(n):
7        for j in range(i + 1, n):
8            if (dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]) or \
9               (dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]):
10                count += 1
11    return count
12
13# Example usage
14print(numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6]]))

ℹ

Complexity note: The time complexity is O(n²) because we are using two nested loops to compare each domino with every other domino. The space complexity is O(1) since we are only using a few variables for counting.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.