Number of Equivalent Domino Pairs

easy array hash map counting

Problem

Given a list of dominoes, where each domino is a pair [a, b], return the number of pairs of indices (i, j) with i < j such that dominoes[i] is equivalent to dominoes[j]. Two dominoes are equivalent if one can be rotated to match the other — that is, [a, b] equals [c, d] when (a == c and b == d) or (a == d and b == c).

Inputdominoes = [[1,2],[2,1],[3,4],[5,6]]

Output1

[1,2] and [2,1] are equivalent (one is the rotation of the other), giving exactly one valid pair.

dominoes (pairs, e.g. 1-2, 2-1, 3-4)

def num_equiv_domino_pairs(dominoes):
    seen = {}
    total = 0
    for a, b in dominoes:
        key = (a, b) if a <= b else (b, a)
        total += seen.get(key, 0)
        seen[key] = seen.get(key, 0) + 1
    return total

function numEquivDominoPairs(dominoes) {
  const seen = new Map();
  let total = 0;
  for (const [a, b] of dominoes) {
    const key = a <= b ? a + "," + b : b + "," + a;
    total += seen.get(key) || 0;
    seen.set(key, (seen.get(key) || 0) + 1);
  }
  return total;
}

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> seen = new HashMap<>();
        int total = 0;
        for (int[] d : dominoes) {
            int key = d[0] <= d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
            total += seen.getOrDefault(key, 0);
            seen.put(key, seen.getOrDefault(key, 0) + 1);
        }
        return total;
    }
}

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

Explanation

Two dominoes are equivalent if one is the rotation of the other, so [1,2] and [2,1] should be treated as the same tile. The trick is to normalize each domino into a single canonical key by always putting the smaller number first.

We scan the dominoes once and keep a hash map seen of key → how many times we have met that shape so far. For the current tile, every earlier tile with the same key forms a valid pair with it, so we add seen[key] to the running total before bumping the count.

Adding the prior count is the neat part: it counts all (i, j) pairs with i < j without ever comparing pairs directly.

Example: [[1,2],[2,1],[3,4],[5,6]]. Tile [1,2] → key 1,2, seen 0, store it. Tile [2,1] normalizes to the same 1,2, which was seen once → add 1. The others are unique → add 0. Total = 1.

Because each tile is handled in constant time, the whole count is one linear pass.

Time: O(n) Space: O(n)