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)
1class Solution {
2 public int minDominoRotations(int[] tops, int[] bottoms) {
3 int check(int val, int[] A, int[] B) {
4 int rotations_a = 0, rotations_b = 0;
5 for (int i = 0; i < A.length; i++) {
6 if (A[i] != val && B[i] != val) return Integer.MAX_VALUE;
7 else if (A[i] != val) rotations_a++;
8 else if (B[i] != val) rotations_b++;
9 }
10 return Math.min(rotations_a, rotations_b);
11 }
12
13 int minRotations = Math.min(check(tops[0], tops, bottoms), check(bottoms[0], tops, bottoms));
14 return minRotations == Integer.MAX_VALUE ? -1 : minRotations;
15 }
16}In Java, we use a helper function check() to iterate through tops and bottoms arrays, to check how many rotations are needed to have the same number throughout either array.
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)
1This JavaScript solution explores both numbers from the first domino and seeks to make one of them dominate by counting necessary rotations and confirming possibility directly.