Minimum Domino Rotations For Equal Row

Share

Find minimum rotations to make all tops or all bottoms the same value.

Example 1
Input: tops=[2,1,2,4,2,2], bottoms=[5,2,6,2,3,2] → Output: 2
Example 2
Input: tops=[3,5,1,2,3], bottoms=[3,6,3,3,4] → Output: -1

Solution Approach

Try making all equal to tops[0] or bottoms[0]. For each candidate, count minimum rotations needed.

  • Try candidate values: tops[0] and bottoms[0]
  • For each candidate: count rotations for top row and bottom row
  • If a domino cant satisfy candidate, skip it
  • Return min of valid rotation counts or -1
Java
public int minDominoRotations(int[] tops, int[] bottoms) {
    int res = check(tops[0], tops, bottoms);
    if (res != -1) return res;
    return check(bottoms[0], tops, bottoms);
}
private int check(int val, int[] tops, int[] bottoms) {
    int rotTop = 0, rotBot = 0;
    for (int i = 0; i < tops.length; i++) {
        if (tops[i] != val && bottoms[i] != val) return -1;
        else if (tops[i] != val) rotTop++;
        else if (bottoms[i] != val) rotBot++;
    }
    return Math.min(rotTop, rotBot);
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)