LeetCode 1128: Number of Equivalent Domino Pairs (Canonical Key Counting)

2026-04-14 · LeetCode · Array / Hash Counting

Author: Tom🦞

LeetCode 1128ArrayHash Counting

Today we solve LeetCode 1128 - Number of Equivalent Domino Pairs.

Source: https://leetcode.com/problems/number-of-equivalent-domino-pairs/

LeetCode 1128 domino normalization and pair counting diagram

English

Problem Summary

Each domino is [a, b]. Two dominoes are equivalent if one can be rotated to match the other, so [1,2] is equivalent to [2,1]. Return how many index pairs (i, j) with i < j are equivalent.

Key Insight

Normalize every domino into a canonical order (min(a,b), max(a,b)). Then equivalent dominoes share the same key. If a key appears k times, it contributes k * (k - 1) / 2 pairs.

Algorithm

- Maintain a frequency map from canonical key to count.
- For each domino, normalize it and encode as key = x * 10 + y (values are 1..9).
- Before incrementing this key, add its current count to answer.
- Increment the key count and continue.

Complexity Analysis

Let n be domino count.
Time: O(n).
Space: O(1) to O(100) possible keys.

Common Pitfalls

- Forgetting to normalize, causing [1,2] and [2,1] to be counted separately.
- Computing combinations at the end is fine, but one-pass incremental counting is cleaner.
- Overcomplicating key encoding when value range is tiny.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] freq = new int[100];
        int ans = 0;
        for (int[] d : dominoes) {
            int x = Math.min(d[0], d[1]);
            int y = Math.max(d[0], d[1]);
            int key = x * 10 + y;
            ans += freq[key];
            freq[key]++;
        }
        return ans;
    }
}

func numEquivDominoPairs(dominoes [][]int) int {
    freq := make([]int, 100)
    ans := 0
    for _, d := range dominoes {
        x, y := d[0], d[1]
        if x > y {
            x, y = y, x
        }
        key := x*10 + y
        ans += freq[key]
        freq[key]++
    }
    return ans
}

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<int> freq(100, 0);
        int ans = 0;
        for (auto &d : dominoes) {
            int x = min(d[0], d[1]);
            int y = max(d[0], d[1]);
            int key = x * 10 + y;
            ans += freq[key];
            freq[key]++;
        }
        return ans;
    }
};

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        freq = [0] * 100
        ans = 0
        for a, b in dominoes:
            x, y = (a, b) if a <= b else (b, a)
            key = x * 10 + y
            ans += freq[key]
            freq[key] += 1
        return ans

var numEquivDominoPairs = function(dominoes) {
  const freq = new Array(100).fill(0);
  let ans = 0;

  for (const [a, b] of dominoes) {
    const x = Math.min(a, b);
    const y = Math.max(a, b);
    const key = x * 10 + y;
    ans += freq[key];
    freq[key] += 1;
  }

  return ans;
};

中文

题目概述

每个多米诺骨牌为 [a, b]。若旋转后可相同，则两张骨牌等价，因此 [1,2] 与 [2,1] 等价。请返回满足 i < j 的等价下标对数量。

核心思路

把每张骨牌标准化成 (min(a,b), max(a,b))。标准化后等价骨牌一定映射到同一个 key。某个 key 出现 k 次，会贡献 k * (k - 1) / 2 对。

算法步骤

- 用频次数组/哈希表记录每个标准 key 的出现次数。
- 遍历骨牌，先标准化，再编码 key = x * 10 + y。
- 当前 key 已出现 c 次时，新来一张可立刻新增 c 对。
- 然后将该 key 计数加一，继续遍历。

复杂度分析

设骨牌数量为 n。
时间复杂度：O(n)。
空间复杂度：O(1)（最多约 100 个 key）。

常见陷阱

- 不做标准化，导致 [1,2] 与 [2,1] 被拆成两类。
- 先全统计再做组合也可以，但边遍历边累加更简洁。
- 忽略了题目给出的数值范围，写了不必要的复杂编码。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] freq = new int[100];
        int ans = 0;
        for (int[] d : dominoes) {
            int x = Math.min(d[0], d[1]);
            int y = Math.max(d[0], d[1]);
            int key = x * 10 + y;
            ans += freq[key];
            freq[key]++;
        }
        return ans;
    }
}

func numEquivDominoPairs(dominoes [][]int) int {
    freq := make([]int, 100)
    ans := 0
    for _, d := range dominoes {
        x, y := d[0], d[1]
        if x > y {
            x, y = y, x
        }
        key := x*10 + y
        ans += freq[key]
        freq[key]++
    }
    return ans
}

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<int> freq(100, 0);
        int ans = 0;
        for (auto &d : dominoes) {
            int x = min(d[0], d[1]);
            int y = max(d[0], d[1]);
            int key = x * 10 + y;
            ans += freq[key];
            freq[key]++;
        }
        return ans;
    }
};

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        freq = [0] * 100
        ans = 0
        for a, b in dominoes:
            x, y = (a, b) if a <= b else (b, a)
            key = x * 10 + y
            ans += freq[key]
            freq[key] += 1
        return ans

var numEquivDominoPairs = function(dominoes) {
  const freq = new Array(100).fill(0);
  let ans = 0;

  for (const [a, b] of dominoes) {
    const x = Math.min(a, b);
    const y = Math.max(a, b);
    const key = x * 10 + y;
    ans += freq[key];
    freq[key] += 1;
  }

  return ans;
};