Leetcode: Minimum Domino Rotations for Equal Row

This question was Google's most asked Leetcode Question for a long time now and it is as follows: 

In a row of dominos, A[i] and B[i] represent the top and bottom half of the ith domino. We may rotate the ith domino so that A[i] and B[i] swap values. Return the minimum number of rotations so that all the values in A and B are the same. If it cannot be done, return -1. 

Here are the examples:

Input: A = [2, 1, 2, 4, 2, 2], B = [5, 2, 6, 2, 3, 2]

Output = 2

Explanation: If we rotate the second and fourth dominos, we can make sure that every value in the first row is equal to 2. 

A = [3, 5, 1, 2, 3], B = [3, 6, 3, 3, 4]

Ouput = -1

Explanation:

It is not possible to rotate the dominos to make one of the row values equal.

Here was my solution. Unfortunately, this didn't pass. 

class Solution {

    public int minDominoRotations(int[] A, int[] B) {

        int result = 0;

        

        HashMap<Integer, Integer> set = new HashMap<Integer, Integer>();

        for(int i = 0; i < A.length; i++){

            int getNum = 0;

            if(set.get(i) != null) {

                getNum = set.get(A[i]);

            }

            set.put(A[i], ++getNum);

        }

        

        int mostCommonElement = -1;

        for(int i = 0; i < A.length; i++){

            int getNum = set.get(A[i]);

            if(getNum > set.get(mostCommonElement)) {

                mostCommonElement = i;

            }

        }

        

        for(int i = 0; i < A.length; i++) {

            if(A[i] != mostCommonElement && B[i] != mostCommonElement) {

                return -1; 

            } else if (B[i] == mostCommonElement && A[i] != mostCommonElement) {

                result++;

            }

            

        }

        

        return result;

        

    }

}

As of Late February 2020, this is the most asked question at Google.

The limiting factor is that we have 4 different possibilities. The top left value we can try to make all the dominoes match that. The next thing we can do we can try to make every single value in A match B[0] or we can we can have every value in B match A[0] or make every single value in B match B[0]. And these are the 4 possibilities.

Once we realize this, this problem becomes a lot more simplified, and it's really not that hard as a result to try to simulate all of these possibilities.

To kind of sketch out this possibilities, the minimum number of swaps is equal to the minimum of many different possibilities. We can try to match A[0] or match B[0] for A and B. 

To kind of sketch out these 4 possiblities, the minimum number of swaps is Math.min of the 2 different possibilities, or numSwaps, trying to make A and B both adhere to A0. Or we can try A and B to attempt to match B[0]. That's 2 things that we can compare, the swaps that takes to match all of A with A[0] and all of B with B[0] and we can have Math.min of all the swaps and the number of swaps. 

Or we can try to make everything in B match B[0] or make everything in A match A[0]. 

Now we write the helper function to determine the number of swaps it will take called the numSwaps, and this function will correspondingly return an integer. We want to walk through the dominoes and see if it's possible to make swaps accordingly to see if there's actually a possibility to make some number of swaps. If the target at A or B doesn't match, then swapping wouldn't help and it's impossible. Else if A[i] doesn't equal the target but B[i] equals the target, just increment the swaps, and then return the number of swaps for the function and it's pretty simple from there. It is basically a brute force simulation from there. 

So, in hindsight, this is O(n) where n is the number of dominoes that we're given. 

Here is the following code with the corresponding comments: 

class Solution {

    public int minDominoRotations(int[] A, int[] B) {

        //try 4 cases: Make A value A[0], Make A value B[0], Make B Value A[0], 

        //Make B Value B[0]

        int minSwaps = Math.min(numSwaps(A[0], A, B), numSwaps(B[0], A, B));

        minSwaps = Math.min(minSwaps, numSwaps(A[0], B, A));

        minSwaps = Math.min(minSwaps, numSwaps(B[0], B, A));

        return minSwaps == Integer.MAX_VALUE ? -1 : minSwaps;

    }

    public int numSwaps(int target, int[] A, int[] B) {

        int numSwaps = 0;

        for(int i = 0; i < A.length; i++) {

            //Cannot find target A[0]

            if(A[i] != target && B[i] != target) {

                return Integer.MAX_VALUE;

            } else if(A[i] != target) {

                //we increment if B has the target and A doesn't. 

                numSwaps++;

            }

        }

        //return the number of swaps

        return numSwaps;

    } 

}