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 <vector>
2#include <algorithm>
3using namespace std;
4
5int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
6 auto check = [&](int x) {
7 int rotations_a = 0, rotations_b = 0;
8 for (int i = 0; i < tops.size(); i++) {
9 if (tops[i] != x && bottoms[i] != x) return INT_MAX;
10 else if (tops[i] != x) rotations_a++;
11 else if (bottoms[i] != x) rotations_b++;
12 }
13 return min(rotations_a, rotations_b);
14 };
15
16 int rotations = check(tops[0]);
17 rotations = min(rotations, check(bottoms[0]));
18 return rotations == INT_MAX ? -1 : rotations;
19}This C++ solution employs a lambda function to check the minimum rotations possible for two target numbers: the first numbers of each row.
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
Count the maximum appearances by any number from both top and bottom rows. Aim to make this number dominate the row by counting feasible rotations.