Sponsored
Sponsored
This approach is based on selecting a target number to either dominate the top or bottom row and counting the minimum rotations needed.
We first choose a target which could dominate the row: either tops[0] or bottoms[0]. Then we iterate over each domino, using an additional check to verify if that target can fully dominate a row. If we face a domino where neither side contains the target, it's not possible for that target to dominate the row.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)
1def minDominoRotations(tops: List[int], bottoms: List[int]) -> int:
2 def check(x):
3 rotations_a = rotations_b = 0
4 for i in range(len(tops)):
5 if tops[i] != x and bottoms[i] != x:
6 return float('inf')
7 elif tops[i] != x:
8 rotations_a += 1
9 elif bottoms[i] != x:
10 rotations_b += 1
11 return min(rotations_a, rotations_b)
12
13 rotations = min(check(tops[0]), check(bottoms[0]))
14 return -1 if rotations == float('inf') else rotationsThis Python solution involves defining a check() function to determine the minimum number of rotations for a candidate number. The candidate numbers are taken from the initial values of the tops and bottoms lists.
To solve the problem using this approach, we evaluate the elements with the most appearance that could be converted to make a row uniform. This involves utilizing frequency maps to identify potential candidates quickly and checking their feasibility.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)
1 public int MinDominoRotations(int[] tops, int[] bottoms) {
int maxFreq = tops[0];
int rotations_t, rotations_b;
for (int candidate = 0; candidate < 2; ++candidate) {
int val = candidate == 0 ? tops[0] : bottoms[0];
rotations_t = rotations_b = 0;
for (int i = 0; i < tops.Length; ++i) {
if (tops[i] != val && bottoms[i] != val) {
rotations_t = rotations_b = int.MaxValue;
break;
} else if (tops[i] != val) rotations_t++;
else if (bottoms[i] != val) rotations_b++;
}
int rotations = Math.Min(rotations_t, rotations_b);
if (rotations != int.MaxValue) return rotations;
}
return -1;
}
}This C# solution assesses the need for rotations using initial values in the rows, checking their dominance possibility by checking equivalency and necessary rotates count.