Number of Equivalent Domino Pairs: Counting with Normalization

LeetCode #1128 Number of Equivalent Domino Pairs is one of those easy problems that teaches you a building block far more useful than the problem itself. The core idea, normalizing inputs so that equivalent things share the same key, shows up in dozens of harder problems.

The problem

Given a list of dominoes where dominoes[i] = [a, b], two dominoes [a, b] and [c, d] are equivalent if either (a == c and b == d) or (a == d and b == c). In other words, one domino can be rotated to match the other.

Return the number of pairs (i, j) where 0 <= i < j and dominoes[i] is equivalent to dominoes[j].

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

The answer is 4. The equivalent pairs are: (0,1), (0,4), (1,4), and (2,5).

The question boils down to: how do you efficiently count pairs of dominoes that are the same after accounting for rotation?

The brute force approach

The most obvious way: compare every pair of dominoes directly. For each pair (i, j), check if they match in either orientation.

def num_equiv_domino_pairs(dominoes: list[list[int]]) -> int:
    count = 0
    for i in range(len(dominoes)):
        for j in range(i + 1, len(dominoes)):
            a, b = dominoes[i]
            c, d = dominoes[j]
            if (a == c and b == d) or (a == d and b == c):
                count += 1
    return count

This works but runs in O(n^2) time. For up to 40,000 dominoes (the constraint), that is up to 800 million comparisons. Way too slow.

The key insight: normalize then count

Here is the trick. If you normalize each domino so that the smaller number always comes first, then equivalent dominoes produce the exact same key. [1,2] becomes (1,2). [2,1] also becomes (1,2). Now you just need to count how many dominoes share each key.

Once you know that k dominoes share a key, the number of pairs among them is k * (k - 1) / 2. That is the combination formula for "choose 2 from k."

But there is an even cleaner way. As you scan through the dominoes, for each one you check how many dominoes with the same key you have already seen. That count is exactly the number of new pairs this domino creates. Then you increment the count for that key.

The code

from collections import defaultdict

def num_equiv_domino_pairs(dominoes: list[list[int]]) -> int:
    counts = defaultdict(int)
    pairs = 0
    for a, b in dominoes:
        key = (min(a, b), max(a, b))
        pairs += counts[key]
        counts[key] += 1
    return pairs

Let's walk through what each line does:

• counts = defaultdict(int) creates a hash map where missing keys default to 0. This tracks how many dominoes we have seen so far for each normalized key.
• key = (min(a, b), max(a, b)) normalizes the domino. The smaller value goes first. This ensures [1,2] and [2,1] produce the same key (1,2).
• pairs += counts[key] adds the number of previously seen dominoes with this key. Each of those forms a new pair with the current domino.
• counts[key] += 1 records that we have seen one more domino with this key.

One pass. One hash map. Done.

Visual walkthrough

Let's trace through [[1,2],[2,1],[3,4],[5,6],[1,2],[3,4]] step by step. Watch how the count map builds up and how pairs accumulate.

That is the entire algorithm. At each step, the number of new pairs equals the current count for that key. The running total gives us the answer.

Complexity analysis

The hash map approach is the clear winner. Each domino is processed in O(1) time: one min/max normalization, one hash map lookup, and one increment. The total is O(n) time and O(n) space for the count map.

In practice, the space is bounded by the number of distinct normalized keys. Since domino values range from 1 to 9, there are at most 45 distinct keys (9 pairs where a == b, plus 36 pairs where a != b, divided by 2 for normalization). So the space is effectively O(1) for this problem, though the O(n) analysis is more general.

The building blocks

This problem breaks down into two reusable pieces that show up across many other problems:

1. Key normalization

The act of transforming different representations of the same thing into a single canonical form. [1,2] and [2,1] look different, but they represent the same domino. Sorting the pair (or using min/max) produces a unique key that captures this equivalence.

This concept appears beyond dominoes. In Group Anagrams, you sort the characters of each word to produce a canonical key. In graph problems, you might normalize edge representations so that (u, v) and (v, u) map to the same key. The core idea is always the same: find a transformation that maps equivalent inputs to identical outputs.

2. Incremental pair counting

Instead of computing all pairs at the end, you count pairs as you go. When you encounter the k-th domino with a given key, it forms pairs with all k-1 dominoes you have already seen. So you add k-1 to your running total, then increment the count. This avoids needing to store the actual dominoes, just the counts.

This incremental counting pattern appears in problems like counting pairs of equal elements, pairs of songs with durations divisible by 60, and other "count the pairs" problems. The template is always:

for item in collection:
    key = normalize(item)
    pairs += counts[key]
    counts[key] += 1

3. Hash map frequency counting

The fundamental pattern of walking through a collection and tracking how many times each element (or key) appears. This is the same pattern behind Contains Duplicate, Valid Anagram, and dozens of other problems. The only difference here is that you normalize before counting.

Edge cases

A few things to watch for:

• All dominoes identical. If every domino is [1,1], the answer is n * (n - 1) / 2. The algorithm handles this naturally since every domino maps to the same key.
• No equivalent pairs. If every domino is unique, the answer is 0. Each key has count 1, so no pairs are added.
• Single domino. With only one domino, there are no pairs. The loop runs once, finds count 0, and returns 0.
• Values equal on both sides. [3,3] normalizes to (3,3). No special case needed since min(3,3) == max(3,3) == 3.

From understanding to recall

Number of Equivalent Domino Pairs feels almost trivial once you see the normalization trick. "Obviously you sort the pair and use it as a hash map key." But the building block here is not specific to dominoes. It is the "normalize then count" pattern, and that pattern shows up in problems where the equivalence relationship is much less obvious.

The next time you see a problem that asks "count pairs of equivalent things," you want the normalize-and-count template to fire automatically. Not as something you re-derive, but as a pattern you recognize and apply in seconds.

Spaced repetition makes that happen. You practice the normalization step and the incremental counting step as separate building blocks, typing them from scratch at increasing intervals. After a few cycles, the moment you see "equivalent pairs," you already know the approach.

Related posts

• Contains Duplicate - The simplest hash set counting problem. Same "have I seen this before?" check, without the normalization step.
• Group Anagrams - Uses the same canonicalization idea (sort characters to produce a key) but groups elements instead of counting pairs.
• Valid Anagram - Another equivalence problem where normalization (frequency counting) determines if two inputs are "the same."