Number of Equivalent Domino Pairs LeetCode solution in Java

1
class Solution {
2
  /**
3
   * Algorithm 1. Brute force cannot be used because of the set size. 2. Traverse the dominos and
4
   * group & count them by min-max value. As pieces can be from 1 to 9, means their groups will be
5
   * from 11 to 99. eg: [1,2] will be the same as [2,1]. Their value is 10 * (min(1,2)) + max(1,2)
6
   * => 10 * 1 + 2 = 12. so pieces[12]++; 3. After finishing traversing, iterate over the counted
7
   * pieces and if the count is > 1, calculate the combinations of X by 2. 4. The formula is n!/ (k!
8
   * * (n-k)!) As n! can be very large, use the short version of it; (n * (n-1)) / 2. EG n= 40 Eg:
9
   * 40! simplify this(divide by 38!) 39 * 40 -------- --------- 2! * (38!) 2 5. Return the total
10
   * result
11
   */
12
  public int numEquivDominoPairs(int[][] dominoes) {
13
    int[] pieces = new int[100];
14
    for (int[] domino : dominoes) {
15
      pieces[10 * Math.min(domino[0], domino[1]) + Math.max(domino[0], domino[1])]++;
16
    }
17
    int pairs = 0;
18
    for (int i = 11; i <= 99; i++) {
19
      if (pieces[i] > 1) {
20
        pairs += getCombinations(pieces[i]);
21
      }
22
    }
23

24
    return pairs;
25
  }
26

27
  private int getCombinations(int n) {
28
    return (n * (n - 1)) / 2;
29
  }
30
}