Leetcode

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 i-th domino.  (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile.)

We may rotate the i-th 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.

Example 2:

Input: 

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

Output: 

-1

Explanation: 

In this case, it is not possible to rotate the dominoes to make one row of values equal.

 

Note:

  1. 1 <= A[i], B[i] <= 6
  2. 2 <= A.length == B.length <= 20000

Thoughts:

  • Two possible values, A[0] and B[0]
  • For each possible value, and foreach index, if one doesn’t have while the other does add 1 to counter
  • There are two counters for each possible values, {B->A, A->B}
  • Return the best result

The speaking of domino’s top and bottom is misleading, no domino has the same value for top and bottom. Why not just say a single digit number?

 

class Solution {

    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function minDominoRotations($A, $B) {
  
        $p = [];      // Possible Values
        $p[] = $A[0]; // Either First elem if A
        $p[] = $B[0]; // Either First elem of B
        $r = [];      // List of mins 

        // Foreach Possible Values
        foreach($p as $s){
            $x = 0;   // Counter, swap B to match A's Value
            $y = 0;   // Counter, swap A to match B's Value
            $nf = false;    // For a possible value, not found both Swap A to B and B to A
            for($i = 0;$i < count($A); $i ++){
                if($s == $A[$i] && $s !== $B[$i]){
                    $y ++;
                } elseif ($s == $B[$i] && $s !== $A[$i]){
                    $x ++;
                } else if($s !== $A[$i] && $s !== $B[$i]) {
                    // If possible value not found in either array, move to next possible value.
                    $nf = true;
                    break;
                }
                
            }

            if(!$nf){
                // If found
                if($x == 0 || $y ==0){
                    // O is the best, no need to continue
                    return 0;
                }
                // Otherwise push the best counter result to array
                $r[] = min($x, $y);
            }

        }
        // When all possible values are no longer possible :(
        if(empty($r)){
            return -1;
        }
        // Otherwise return the best result
        return min($r);
    }
}