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)
1public class Solution {
2 public int MinDominoRotations(int[] tops, int[] bottoms) {
3 int Check(int x) {
4 int rotations_a = 0, rotations_b = 0;
5 for (int i = 0; i < tops.Length; ++i) {
6 if (tops[i] != x && bottoms[i] != x) return int.MaxValue;
7 else if (tops[i] != x) rotations_a++;
8 else if (bottoms[i] != x) rotations_b++;
9 }
10 return Math.Min(rotations_a, rotations_b);
11 }
12
13 int rotations = Math.Min(Check(tops[0]), Check(bottoms[0]));
14 return rotations == int.MaxValue ? -1 : rotations;
15 }
16}This C# solution uses a helper method Check inside the main method, which checks for each prospective dominant value, calculating rotations needed and returns the minimum or -1 if impossible.
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.