Is Number of Equivalent Domino Pairs easy or hard?

Number of Equivalent Domino Pairs is classified as an Easy problem on LeetCode. The challenge focuses on recognizing that dominoes must be normalized before counting duplicates and then applying a straightforward hash map frequency technique.

Number of Equivalent Domino Pairs Python/Java solution

Python and Java solutions typically use a dictionary or HashMap to store counts of normalized domino pairs. Each time the same pair appears again, the current frequency contributes to the total number of equivalent pairs. Both implementations achieve O(n) time complexity.

How to solve Number of Equivalent Domino Pairs in O(n)?

Normalize each domino so the smaller value comes first, then track how many times that normalized pair has appeared. When you encounter the same pair again, it forms new pairs with all previous occurrences. Add the current frequency to the result and increment the count. This produces a linear-time counting solution.

What is the best approach for Number of Equivalent Domino Pairs?

The best approach uses a hash map to count normalized domino pairs. Each domino is converted to (min(a,b), max(a,b)) so that rotations are treated as the same pair. While iterating, add the existing frequency of that pair to the result and update the count. This runs in O(n) time with O(n) space.

Is Number of Equivalent Domino Pairs asked at Google/Amazon/Meta?

Domino pair counting problems appear in interviews at companies like Amazon and Google as variations of frequency counting or hash map problems. They test understanding of normalization, pair counting, and efficient use of hash tables in linear time.

What data structure is used in Number of Equivalent Domino Pairs?

The primary data structure is a hash table that stores frequencies of normalized domino pairs. Because domino values are limited to 1 through 9, an alternative implementation uses a fixed-size array for frequency counting, which reduces memory overhead and avoids hashing.

What is the time complexity of Number of Equivalent Domino Pairs?

The optimal solution runs in O(n) time because each domino is processed exactly once and hash map or array lookups take constant time. Space complexity is O(n) for the hash map approach or O(1) when using a fixed counting array based on the domino value range.

Description Hints 2 Solution Video 25:35

1128. Number of Equivalent Domino Pairs

Easy60.7% acceptance3 companies

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

Asked at 3 companies

Amazon

Google Bloomberg

Topics

Hints open one at a time

Hint 1

For each domino j, find the number of dominoes you've already seen (dominoes i with i < j) that are equivalent.

Hint 2

You can keep track of what you've seen using a hashmap.

25:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,2],[2,1],[3,4],[5,6]]

Input

[[1,2],[1,2],[1,1],[1,2],[2,2]]

Your code is saved on this device.Solution