Number of Equivalent Domino Pairs - Practice Coding Problems

Number of Equivalent Domino Pairs - Problem

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either:

(a == c and b == d), or
(a == d and b == c)

That is, one domino can be rotated to be equal to another domino.

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

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: [1,2] and [2,1] are equivalent (one can be rotated to match the other), so there's 1 equivalent pair

Example 2 — Multiple Pairs

$ Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]

› Output: 3

💡 Note: Three [1,2] dominoes form 3 pairs: (0,1), (0,3), (1,3). Other dominoes don't have matches.

Example 3 — No Equivalent Pairs

$ Input: dominoes = [[1,1],[2,2],[1,3]]

› Output: 0

💡 Note: No two dominoes are equivalent, so there are 0 pairs

Constraints

1 ≤ dominoes.length ≤ 4 × 10⁴
dominoes[i].length == 2
1 ≤ dominoes[i][j] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Array of dominoes where each domino has two values

Process

Find dominoes that are equivalent (same values, possibly rotated)

Output

Count of equivalent pairs where i < j

Key Takeaway

🎯 Key Insight: Normalize dominoes by sorting values to handle rotation, then count frequencies and calculate pairs using n*(n-1)/2 formula

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to normalize dominoes by sorting their values to handle rotation, then count frequencies. The optimal approach uses a hash map to count equivalent dominoes in O(n) time. For n identical dominoes, there are n*(n-1)/2 pairs. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Count	O(n)	O(n)	Normalize dominoes and count frequencies using hash map
Brute Force	O(n²)	O(1)	Compare every pair of dominoes directly

Hash Map Frequency Count — Algorithm Steps

Step 1: Normalize each domino by sorting its values
Step 2: Count frequency of each normalized domino using hash map
Step 3: For each frequency n > 1, add n*(n-1)/2 to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Normalize

Convert each domino to standard form [min, max]

Count Frequencies

Use hash map to count occurrences of each normalized domino

Calculate Pairs

For frequency n, add n*(n-1)/2 pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DOMINOES 40000

struct DominoCount {
    int a, b;
    int count;
};

int solution(int dominoes[][2], int n) {
    struct DominoCount normalized[MAX_DOMINOES];
    int unique = 0;
    
    for (int i = 0; i < n; i++) {
        int a = dominoes[i][0], b = dominoes[i][1];
        // Normalize
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        
        // Find in normalized array
        int found = -1;
        for (int j = 0; j < unique; j++) {
            if (normalized[j].a == a && normalized[j].b == b) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            normalized[unique].a = a;
            normalized[unique].b = b;
            normalized[unique].count = 1;
            unique++;
        } else {
            normalized[found].count++;
        }
    }
    
    int count = 0;
    for (int i = 0; i < unique; i++) {
        int f = normalized[i].count;
        if (f > 1) {
            count += f * (f - 1) / 2;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int dominoes[1000][2];
    int n = 0;
    
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            dominoes[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            dominoes[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    int result = solution(dominoes, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through dominoes array to count frequencies

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n unique normalized dominoes

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler