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
This approach counts maximum common elements in both arrays and uses a basic frequency counting technique for rotation calculation.