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)
1#include <stdbool.h>
2
3int minDominoRotations(int* tops, int topsSize, int* bottoms, int bottomsSize) {
4 int myMin(int a, int b) {
5 return a < b ? a : b;
6 }
7
8 bool canConvert(int targetValue) {
9 int topRotations = 0, bottomRotations = 0;
10 for (int i = 0; i < topsSize; i++) {
11 if (tops[i] != targetValue && bottoms[i] != targetValue) {
12 return false;
13 } else if (tops[i] != targetValue) {
14 topRotations++;
15 } else if (bottoms[i] != targetValue) {
16 bottomRotations++;
17 }
18 }
19 return myMin(topRotations, bottomRotations);
20 }
21
22 int target1 = tops[0];
23 int target2 = bottoms[0];
24 int result1 = canConvert(target1) ? canConvert(target1) : -1;
25 int result2 = canConvert(target2) ? canConvert(target2) : -1;
26
27 if (result1 == -1) return result2;
28 if (result2 == -1) return result1;
29 return myMin(result1, result2);
30}We try rotating to make all dominoes` number either one of the first elements from tops or bottoms. We count the rotations for both top and bottom for each target. If any domino can't be converted to the target value at any time, the approach exits early.
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)
1class
This approach counts maximum common elements in both arrays and uses a basic frequency counting technique for rotation calculation.