Number of Equivalent Domino Pairs

Easy
286.

Number of Equivalent Domino Pairs

Number of Equivalent Domino Pairs is an easy coding problem on arrays, hash table and counting, asked in Amazon and Adobe interviews.

Two dominoes [a, b] and [c, d] are equivalent if a == c and b == d, or if a == d and b == c — a domino may be rotated.

Given a list dominoes, return the number of pairs (i, j) with i < j where the two dominoes are equivalent.

Example 1

Input
dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output
1
Explanation
[1,2] and [2,1] are the same domino rotated.

Example 2

Input
dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output
3
Explanation
The three [1,2] dominoes give 3-choose-2 = 3 pairs.

Example 3

Input
dominoes = [[1,1]]
Output
0

Constraints

  • 1 <= dominoes.length <= 30
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} dominoes
 * @return {number}
 */
var numEquivDominoPairs = function(dominoes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Equivalent Domino Pairs — Problem & Solution

Number of Equivalent Domino Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Equivalent Domino Pairs is an easy coding problem on arrays, hash table and counting, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two dominoes [a, b] and [c, d] are equivalent if a == c and b == d, or if a == d and b == c — a domino may be rotated.

Given a list dominoes, return the number of pairs (i, j) with i < j where the two dominoes are equivalent.

Example 1

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1
Explanation: [1,2] and [2,1] are the same domino rotated.

Example 2

Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3
Explanation: The three [1,2] dominoes give 3-choose-2 = 3 pairs.

Example 3

Input: dominoes = [[1,1]]
Output: 0

Constraints

  • 1 <= dominoes.length <= 30
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9

Hints for Number of Equivalent Domino Pairs

  1. Hint 1

    Rotation means [a, b] and [b, a] must hash to the same key — normalise by putting the smaller value first.

  2. Hint 2

    min * 10 + max packs the normalised pair into a single integer key.

  3. Hint 3

    Count as you scan: each new domino pairs with every equivalent one already seen.

How to solve Number of Equivalent Domino Pairs

Normalise each domino with the smaller value first so rotations share a key, then count pairs as you scan: each new domino pairs with every equivalent one already seen.

Approach

  1. Compute key = min·10 + max.
  2. Add count[key] to the total, then increment count[key].

Why it works

Equivalence classes collapse to a single key, and summing the running count for each occurrence yields c(c-1)/2 pairs per class.

Complexity

  • Time — O(n)
  • Space — O(1) — at most 100 keys

Pitfalls

  • Values are ≤ 9, which is what makes the 10·a + b packing collision-free.

Reference solution

Python

def numEquivDominoPairs(dominoes) -> int:
    count = {}
    total = 0
    for a, b in dominoes:
        key = a * 10 + b if a < b else b * 10 + a
        total += count.get(key, 0)
        count[key] = count.get(key, 0) + 1
    return total

Java

public static int numEquivDominoPairs(int[][] dominoes) {
    int[] count = new int[100];
    int total = 0;
    for (int[] d : dominoes) {
        int key = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
        total += count[key];
        count[key]++;
    }
    return total;
}

C++

int numEquivDominoPairs(vector<vector<int>>& dominoes) {
    int count[100] = {0};
    int total = 0;
    for (vector<int>& d : dominoes) {
        int key = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
        total += count[key];
        count[key]++;
    }
    return total;
}

JavaScript

var numEquivDominoPairs = function(dominoes) {
    const count = new Map();
    let total = 0;
    for (let i = 0; i < dominoes.length; i++) {
        const a = dominoes[i][0], b = dominoes[i][1];
        const key = a < b ? a * 10 + b : b * 10 + a;
        total += count.get(key) || 0;
        count.set(key, (count.get(key) || 0) + 1);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets