In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.
Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.
If it cannot be done, return -1.
Example 1:
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] Output: 2 Explanation: The first figure represents the dominoes as given by tops and bottoms: before we do any rotations. If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:
Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4] Output: -1 Explanation: In this case, it is not possible to rotate the dominoes to make one row of values equal.
Constraints:
2 <= tops.length <= 2 * 104bottoms.length == tops.length1 <= tops[i], bottoms[i] <= 6This 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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| One-Pass Count Method | Time Complexity: O(n), where n is the number of dominoes. |
| Max Frequency Element Method | Time Complexity: O(n), where n is the number of dominoes. |
Minimum Domino Rotations for Equal Row • Kevin Naughton Jr. • 43,530 views views
Watch 9 more video solutions →Practice Minimum Domino Rotations For Equal Row with our built-in code editor and test cases.
Practice on FleetCode