Minimum Domino Rotations For Equal Row

Problem Statement

LeetCode-1007: In a row of dominoes, tops[i] and bottoms[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 tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

Approach

Let’s think about what would make this possible. For all tops (or bottoms) to be the same value, that value must exist on either the top or bottom of every domino.

For this problem, we can only have at most 6 different values (1-6 on the dominoes). For any value to be a valid candidate:

• Identify which values (1-6) could potentially form a complete row.
• For each valid candidate value, calculate how many rotations would be needed.
• Return the minimum number of rotations among all candidates.

Consider the following example:

tops =    [2,1,2,4,2,2]
bottoms = [5,2,6,2,3,2]

• 1: Appears only once on top, not on all bottoms $\rightarrow$ N.A.
• 2: Appears on either top or bottom of each domino $\rightarrow$ potential candidate
• 3,4,5,6: Don’t appear in every position $\rightarrow$ N.A.

So our only candidate is 2. Now, we need to find the minimum rotations to make all tops 2 or all bottoms 2.

But wait, based on the above example, we can see that we don’t actually need to check all values from 1 to 6. Since we need a value that appears in every position (top or bottom), we only need to check the values in the first domino:

• tops[0]
• bottoms[0]

Only these two values have any chance of working (since the first domino must contribute its value).

Implementation

public int minDominoRotations(int[] tops, int[] bottoms) {
    // Only need to check the values from the first domino
    int[] candidates = {tops[0], bottoms[0]};
    int n = tops.length;
    
    for (int candidate : candidates) {
        // Check if this value can make a complete row
        boolean canFormRow = true;
        int topsRotations = 0;
        int bottomsRotations = 0;
        
        for (int i = 0; i < n; i++) {
            // If neither top nor bottom has our candidate value
            if (tops[i] != candidate && bottoms[i] != candidate) {
                canFormRow = false;
                break;
            }
            
            // Count rotations needed for both tops and bottoms
            if(candidate != tops[i]){
                topRotations++;
            }

            if(candidate != bottoms[i]){
                bottomRotations++;
            }
        }
        
        // If we can form a row with this value
        if (canFormRow) {
            return Math.min(topsRotations, bottomsRotations);
        }
    }
    
    // No solution found
    return -1;
}

Here, we are only checking the two candidates from the first domino (since one of them must be in the final solution). For each candidate:

• Verify if it can form a complete row.
• Simultaneously count the rotations needed for both the top and bottom rows.
• Returning the minimum of these two counts if a solution exists.

Complexity Analysis

• Time Complexity: O(N), where N is the number of dominoes. We only need to check each domino once.
• Space Complexity: O(1), since we are using a constant amount of space for the candidates and counters.