Find minimum rotations to make all tops or all bottoms the same value.
Input: tops=[2,1,2,4,2,2], bottoms=[5,2,6,2,3,2] → Output: 2
Input: tops=[3,5,1,2,3], bottoms=[3,6,3,3,4] → Output: -1
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
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)