Code Implementation

class Solution:
    def minDominoRotations(self, tops, bottoms):
        def check(x):
            rotations_top = rotations_bottom = 0
            for i in range(len(tops)):
                if tops[i] != x and bottoms[i] != x:
                    return -1
                elif tops[i] != x:
                    rotations_top += 1
                elif bottoms[i] != x:
                    rotations_bottom += 1
            return min(rotations_top, rotations_bottom)
        
        rotations = check(tops[0])
        if rotations != -1:
            return rotations
        else:
            return check(bottoms[0])
    

class Solution {
public:
    int check(int x, vector<int>& tops, vector<int>& bottoms) {
        int rotations_top = 0, rotations_bottom = 0;
        for (int i = 0; i < tops.size(); ++i) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            else if (tops[i] != x) rotations_top++;
            else if (bottoms[i] != x) rotations_bottom++;
        }
        return min(rotations_top, rotations_bottom);
    }
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int rotations = check(tops[0], tops, bottoms);
        if (rotations != -1) return rotations;
        else return check(bottoms[0], tops, bottoms);
    }
};
    

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int rotations = check(tops[0], tops, bottoms);
        if (rotations != -1) return rotations;
        else return check(bottoms[0], tops, bottoms);
    }
    private int check(int x, int[] tops, int[] bottoms) {
        int rotationsTop = 0, rotationsBottom = 0;
        for (int i = 0; i < tops.length; ++i) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            else if (tops[i] != x) rotationsTop++;
            else if (bottoms[i] != x) rotationsBottom++;
        }
        return Math.min(rotationsTop, rotationsBottom);
    }
}
    

var minDominoRotations = function(tops, bottoms) {
    function check(x) {
        let rotationsTop = 0, rotationsBottom = 0;
        for (let i = 0; i < tops.length; i++) {
            if (tops[i] !== x && bottoms[i] !== x) return -1;
            else if (tops[i] !== x) rotationsTop++;
            else if (bottoms[i] !== x) rotationsBottom++;
        }
        return Math.min(rotationsTop, rotationsBottom);
    }
    let rotations = check(tops[0]);
    if (rotations !== -1) return rotations;
    return check(bottoms[0]);
};
    

Problem Description

You are given two integer arrays, tops and bottoms, each of length n. These arrays represent the numbers on the top and bottom halves of n dominoes, respectively. You can rotate any domino, swapping its top and bottom values.

The goal is to determine the minimum number of rotations needed so that all values in either the tops array or the bottoms array are the same. If it is not possible to achieve this, return -1.

Constraints:

• Each domino can be rotated independently.
• You may not use the same domino more than once in a rotation.
• There is at most one valid solution.
• Input arrays have the same length and contain only integers from 1 to 6.

Thought Process

At first glance, it seems we might need to try all possible numbers (1 through 6) and check if we can make all dominoes show that number on either the top or bottom. A brute-force approach would check every possible value and count the minimum rotations required.

However, upon closer inspection, we realize that only the numbers present in the first domino (either tops[0] or bottoms[0]) can possibly be the unified value. This is because every domino must have the target number on at least one of its sides. If any domino lacks the candidate number on both sides, it's impossible to achieve uniformity with that number.

This insight shifts us from checking all numbers (brute-force) to checking at most two candidates, greatly reducing unnecessary computation.

Solution Approach

• We only need to consider two possible target values: tops[0] and bottoms[0]. If it's possible to make all dominoes show one of these values on either side, then that is our answer.
• For each candidate value (x):
  1. Iterate through all dominoes.
  2. For each domino, if neither the top nor the bottom is x, it's impossible to use x as the target—return -1.
  3. If the top is not x but the bottom is, we would need to rotate this domino so x comes to the top.
  4. If the bottom is not x but the top is, we would need to rotate this domino so x comes to the bottom.
  5. Count the number of rotations needed for both top and bottom to achieve uniformity.
  6. The minimum of these two counts is the answer for this candidate.
• Try both tops[0] and bottoms[0] as candidates. If both fail, return -1.
• This approach is efficient because it checks only two candidates and iterates through the dominoes at most twice.

Example Walkthrough

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

1. Try making all values in tops or bottoms equal to tops[0] = 2:
   • Domino 0: already has 2 on top, no rotation needed.
   • Domino 1: top is 1, bottom is 2. Need to rotate so 2 is on top.
   • Domino 2: top is 2, no rotation needed.
   • Domino 3: top is 4, bottom is 2. Need to rotate.
   • Domino 4: top is 2, no rotation needed.
   • Domino 5: top is 2, no rotation needed.

   Rotations needed to make all tops 2: 2 (domino 1 and 3). Rotations needed to make all bottoms 2: 1 (domino 0).

2. Try bottoms[0] = 5:
   • Domino 1: top is 1, bottom is 2. No 5 present. So, impossible.

   So, the answer is 2 (minimum rotations to make all tops or all bottoms 2).

Time and Space Complexity

• Brute-force approach: O(6n), since we could check all 6 possible numbers and for each, iterate through all dominoes. But this is unnecessary.
• Optimized approach: O(n), since we only check at most two candidates (tops[0] and bottoms[0]), and for each, scan through the dominoes once.
• Space Complexity: O(1), since we use only a few counters and variables, regardless of input size.

Summary

The key insight is that only the numbers present in the first domino can possibly be made uniform across the entire row. By checking only these candidates and counting the minimal rotations needed for each, we achieve an efficient O(n) solution. This avoids unnecessary computation and demonstrates the power of narrowing the problem space based on problem constraints.

The solution is elegant because it leverages a simple observation to reduce complexity, uses clear logic, and is easy to implement in any mainstream programming language.