LeetCode 1128 - Number of Equivalent Domino Pairs

The problem is asking us to count all pairs of dominoes in a list that are equivalent, where two dominoes [a, b] and [c, d] are considered equivalent if one is a rotation of the other, meaning either (a == c and b == d) or (a == d and b == c).

leetcodeeasyarrayhash-tablecounting

LeetCode Problem 1128

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem is asking us to count all pairs of dominoes in a list that are equivalent, where two dominoes [a, b] and [c, d] are considered equivalent if one is a rotation of the other, meaning either (a == c and b == d) or (a == d and b == c). In other words, the order of the numbers does not matter-[1,2] is equivalent to [2,1].

The input is a list of dominoes, where each domino is represented as a list of two integers between 1 and 9. The output is a single integer, representing the number of pairs (i, j) with i < j such that the dominoes at indices i and j are equivalent. The constraints allow for up to 40,000 dominoes, so a solution with O(n²) complexity would be too slow.

Important edge cases include dominoes that appear multiple times, dominoes with identical numbers like [1,1], and ensuring we do not double-count pairs.

Approaches

A brute-force approach would compare every pair of dominoes. For each domino i, we would iterate over all dominoes j > i and check if they are equivalent. This guarantees correctness because we explicitly check every pair, but it has O(n²) time complexity, which is impractical for large inputs like n = 40,000.

The optimal approach leverages the key observation that each domino can be normalized into a canonical form. By always storing dominoes in sorted order (smaller number first), we ensure that [1,2] and [2,1] both become [1,2]. Then we can count how many times each canonical form occurs using a hash map. If a particular form occurs k times, the number of pairs for that form is k * (k - 1) / 2. This reduces the problem to O(n) time and O(n) space complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare all pairs explicitly
Optimal O(n) O(n) Use a hash map to count canonical forms and compute pairs

Algorithm Walkthrough

  1. Initialize an empty hash map (count_map) to keep track of how many times each canonical domino appears.
  2. Initialize a variable total_pairs to 0, which will accumulate the final count.
  3. Iterate through each domino in the input list. For each domino, sort the two numbers to form a canonical key.
  4. If the key exists in count_map, it means we have seen this domino before. Increment total_pairs by the current count of this key because each previous occurrence forms a new pair with the current domino.
  5. Increment the count of this canonical key in count_map.
  6. After processing all dominoes, return total_pairs.

Why it works: Each domino is reduced to a unique canonical representation regardless of rotation. Counting previous occurrences for each domino ensures that all valid pairs are counted exactly once, satisfying the requirement i < j.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        count_map = defaultdict(int)
        total_pairs = 0
        
        for domino in dominoes:
            key = tuple(sorted(domino))
            total_pairs += count_map[key]
            count_map[key] += 1
        
        return total_pairs

The implementation first creates a defaultdict to count each canonical domino form. For each domino, it sorts the numbers to handle rotations and checks how many times this form has appeared so far. Each prior occurrence contributes one new pair. Finally, it returns the total number of pairs.

Go Solution

func numEquivDominoPairs(dominoes [][]int) int {
    countMap := make(map[[2]int]int)
    totalPairs := 0
    
    for _, domino := range dominoes {
        key := [2]int{domino[0], domino[1]}
        if domino[0] > domino[1] {
            key = [2]int{domino[1], domino[0]}
        }
        totalPairs += countMap[key]
        countMap[key]++
    }
    
    return totalPairs
}

In Go, we use a map with array keys [2]int to store canonical dominoes. Sorting is done manually with a conditional swap. Each domino contributes to totalPairs based on the number of previous occurrences of its canonical form. Go handles arrays as map keys natively, so this works efficiently.

Worked Examples

Example 1: dominoes = [[1,2],[2,1],[3,4],[5,6]]

Domino Canonical Key count_map total_pairs
[1,2] (1,2) {(1,2): 1} 0
[2,1] (1,2) {(1,2): 2} 1
[3,4] (3,4) {(1,2): 2, (3,4):1} 1
[5,6] (5,6) {(1,2):2, (3,4):1, (5,6):1} 1

Output: 1

Example 2: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]

Domino Canonical Key count_map total_pairs
[1,2] (1,2) {(1,2):1} 0
[1,2] (1,2) {(1,2):2} 1
[1,1] (1,1) {(1,2):2,(1,1):1} 1
[1,2] (1,2) {(1,2):3,(1,1):1} 3
[2,2] (2,2) {(1,2):3,(1,1):1,(2,2):1} 3

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each domino is processed once, and sorting a pair is O(1)
Space O(n) Hash map stores counts of up to n unique dominoes

The O(n) time arises because we only iterate through the list once and dictionary operations are O(1). Space is proportional to the number of unique dominoes.

Test Cases

# Provided examples
assert Solution().numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6]]) == 1  # rotated pair
assert Solution().numEquivDominoPairs([[1,2],[1,2],[1,1],[1,2],[2,2]]) == 3  # multiple duplicates

# Edge and boundary cases
assert Solution().numEquivDominoPairs([[1,1]]) == 0  # single domino, no pairs
assert Solution().numEquivDominoPairs([[1,2],[2,1],[1,2],[2,1]]) == 6  # all equivalent
assert Solution().numEquivDominoPairs([[9,9],[9,9],[9,9],[9,9]]) == 6  # identical dominoes
assert Solution().numEquivDominoPairs([[1,2],[3,4],[5,6],[7,8]]) == 0  # all unique
assert Solution().numEquivDominoPairs([[2,1],[1,2],[1,2],[2,1],[1,1]]) == 6  # mixed duplicates
Test Why
[[1,2],[2,1],[3,4],[5,6]] Basic rotation check
[[1,2],[1,2],[1,1],[1,2],[2,2]] Multiple duplicates
[[1,1]] Single element, no pairs
[[1,2],[2,1],[1,2],[2,1]] All equivalent, maximal pairs
[[9,9],[9,9],[9,9],[9,9]] Identical dominoes, maximal pairs
[[1,2],[3,4],[5,6],[7,8]] All unique, no pairs
[[2,1],[1,2],[1,2],[2,1],[1,1]] Mixed duplicates and unique

Edge Cases

One edge case is when there is only a single domino. Since there are no other dominoes to pair with, the function must correctly return 0. Our solution handles this because the loop never finds a previous count.

Another edge case is when all dominoes are identical or rotations of each other. The algorithm must correctly count all pairs without double-counting. By incrementing the total pairs by the current count of the canonical form before incrementing the count, we ensure all valid pairs are included exactly once.

A third edge case is when dominoes contain numbers in descending order, like [2,1]. The canonical key conversion using