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] <= 6In #1007 Minimum Domino Rotations For Equal Row, the goal is to determine the minimum number of rotations needed so that all values in either the top row or bottom row of dominoes become the same. Each domino contains two numbers, and a rotation swaps the top and bottom values at that position.
A key observation is that the final uniform value must be one of the numbers from the first domino. Therefore, we only need to check two candidates: tops[0] and bottoms[0]. For each candidate value, iterate through the arrays and count how many rotations are required to make all values in the top row or bottom row equal to that candidate. If at any index neither side matches the candidate, that candidate is invalid.
This greedy check allows us to evaluate the feasibility and compute the minimum rotations in a single pass. The approach efficiently avoids trying all possible values and keeps the solution linear in time.
Time Complexity: O(n) for scanning the domino arrays.
Space Complexity: O(1) since only counters are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy candidate check using first domino values | O(n) | O(1) |
Kevin Naughton Jr.
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(
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)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If a uniform value is possible across all dominoes, that value must appear in the first domino either on the top or bottom. Otherwise, the first domino itself could never match the final value. This insight reduces the search space to just two candidates.
Yes, variations of this problem have appeared in technical interviews at major tech companies. It tests greedy reasoning, observation skills, and the ability to simplify a problem by reducing candidate possibilities.
The problem mainly relies on arrays since the domino values are given as two arrays: tops and bottoms. No additional complex data structures are required. Simple counters and iteration are sufficient for an optimal solution.
The optimal approach uses a greedy observation that the final equal value must be either tops[0] or bottoms[0]. By checking both candidates and counting the rotations needed in a single pass, we can determine the minimum rotations efficiently. This results in an O(n) time and O(1) space solution.
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.