1128. Number of Equivalent Domino Pairs

EasyView on LeetCode

Array Hash Table Counting

Time: O(n)

Space: O(n)

Problem Overview

A domino [a,b] is equivalent to [b,a].

Intuition

A domino [a,b] is equivalent to [b,a]. Normalize each domino to (min, max) so [2,1] and [1,2] share a key. Count pairs of indices with the same normalized domino using combinations: for frequency f, add f×(f−1)/2.

Algorithm

1For each domino [a,b]: key = (min(a,b), max(a,b)) or min*10+max when values are 1–9.
2Increment frequency map for each key.
3For each frequency f: add f * (f - 1) / 2 to the answer.
4Return total equivalent pairs.

Example Walkthrough

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

1.[1,2] and [2,1] normalize to (1,2) — one pair.
2.(3,4) and (5,6) each alone — no pairs.

Output: 1

Common Pitfalls

•Normalize before counting — order of endpoints does not matter.
•Use long for answer if domino count is large.
•Key encoding min*10+max works when values ≤ 9.

1128.cs

// Approach: Normalize each domino to (min, max) and count frequencies; pairs = n*(n-1)/2 for each group.
// Time: O(n) Space: O(n)

public class Solution
{
    public int NumEquivDominoPairs(int[][] dominoes)
    {
        Dictionary<string, int> dominoCounts = new Dictionary<string, int>();
        int count = 0;

        foreach (var domino in dominoes)
        {
            int a = domino[0];
            int b = domino[1];
            string key = $"{Math.Min(a, b)},{Math.Max(a, b)}";

            if (dominoCounts.ContainsKey(key))
                dominoCounts[key]++;
            else
                dominoCounts[key] = 1;
        }

        foreach (var kvp in dominoCounts)
        {
            int n = kvp.Value;
            if (n >= 2)
                count += n * (n - 1) / 2;
        }

        return count;
    }
}

Was this solution helpful?