1007. Minimum Domino Rotations For Equal Row

/**

 * In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the ith domino.  (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile).

 * 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 are the same, or all the values in B are the same.

 * If it cannot be done, return -1.

 * Example 1:

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

 * Output: 2

 * Explanation:

 * The first figure represents the dominoes as given by A and B: before we do any rotations.

 * If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2,

 * as indicated by the second figure.

 */

See the solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/MinDominoRotations.java

Observation: The question is asking for minimum number of rotations to make all numbers in first or second row to be same. If you take an element from first and second row at any index, you can count the minimum number of rotations needed to make any of the two arrays same for each of the two elements. The minimum of the two will be your answer. It seems initially non intuitive that you can pick any of the indexes but think about it a bit, for the two arrays to have the same elements at all the indexes, you must be able to pick any of the indexes.

Logic:

1. Take any index in either of rows, for explanation use first index, you can count how many swaps will be needed to make the elements in first and second row same as the element at that index.
   1. Taking the minimum of swaps needed in first or second row, will give you the minimum number of swaps needed to make either of rows have the same element.
2. It is possible that the element in the second row at same index as we chose before (first index) is different from the previously chosen element.
   1. In this case we can repeat the calculation in 1a for this element
3. It is also possible that both 1a and 2a don’t return valid answers
4. In case both 1a and 2a have valid answers, chose the minimum of the two

You can draw out various array structures on board to validate this logic.

Here is the code:

public int minDominoRotations(int[] arrA, int[] arrB) {
    if (arrA.length == 0) {
        return 0;
    }
    //if a solution is found by choosing the first element in arrayA then return
    //else try with first element in arrayB
    int rotA = validate(arrA, arrB, arrA[0]);
    if (rotA != -1 || arrA[0] == arrB[0]) return rotA;
    return validate(arrA, arrB, arrB[0]);
}

int validate(int[] arrA, int[] arrB, int val) {
    int countA = 0, countB = 0;
    for (int i = 0; i < arrA.length; i++) {
        if (arrA[i] != val && arrB[i] != val) {
            return -1;
        }
        if (arrA[i] != val) countA++;
        if (arrB[i] != val) countB++;
    }
    return Math.min(countA, countB);
}