1227. Number Of Equivalent Domino Pairs¶

Difficulty: Easy

1227. Number of Equivalent Domino Pairs

Easy

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].

Example 1:

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

Example 2:

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

Constraints:

1 <= dominoes.length <= 4 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

Solution¶

class Solution {
    static class Pair {
        int first, second;
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
        @Override
        public String toString() {
            return "(" + first + " " + second + ")";
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Pair current = (Pair)(obj);
            return current.first == first && current.second == second;
        }
        @Override
        public int hashCode() {
            return Objects.hash(first, second);
        }
    }
    public int numEquivDominoPairs(int[][] arr) {
        int n = arr.length;
        HashMap<Pair, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(new Pair(arr[i][0], arr[i][1]), map.getOrDefault(new Pair(arr[i][0], arr[i][1]), 0) + 1);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            int x = arr[i][0], y = arr[i][1];
            if (x == y) {
                count += map.getOrDefault(new Pair(x, y), 0) - 1;
                if (map.getOrDefault(new Pair(x, y), 0) > 0) map.put(new Pair(x, y), map.getOrDefault(new Pair(x, y), 0) -1);
            }        
            else {
                count += map.getOrDefault(new Pair(x, y), 0) - 1;
                count += map.getOrDefault(new Pair(y, x), 0);
                if (map.getOrDefault(new Pair(x, y), 0) > 0) map.put(new Pair(x, y), map.getOrDefault(new Pair(x, y), 0) -1);
            }
        }
        return count;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here