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] <= 6Problem Overview: You are given two arrays tops and bottoms representing a row of dominoes. Each domino can be rotated. The task is to compute the minimum number of rotations required so that all values in either the top row or bottom row become the same. If no such configuration exists, return -1.
Approach 1: One-Pass Count Method (O(n) time, O(1) space)
This approach exploits a key observation: if a solution exists, the final value must be either tops[0] or bottoms[0]. Iterate through the dominoes once and count how many rotations are required to make every value equal to the candidate. During the scan, check whether the candidate exists in at least one side of each domino. Maintain counters for rotations needed to align the top row and the bottom row separately. If at any index the candidate appears on neither side, that candidate is invalid. This is a classic greedy validation with constant memory and a single linear scan.
Approach 2: Max Frequency Element Method (O(n) time, O(1) space)
Another strategy counts how frequently each domino value appears across both rows. Since domino values range from 1 to 6, maintain small frequency arrays for tops, bottoms, and matches where both sides already contain the same value. A value can fill an entire row only if its total occurrences cover all positions after accounting for overlaps. For each value from 1 to 6, compute the minimum rotations required: either rotate bottoms to match tops or vice versa. This method relies on frequency counting and works well when reasoning about candidate values explicitly within the small fixed domain of domino numbers.
Both solutions rely on simple array traversal and constant-size counters. The greedy validation ensures that every domino can support the chosen value before counting rotations.
Recommended for interviews: The One-Pass Count Method is what interviewers typically expect. It shows you recognized the candidate-value constraint and implemented a linear greedy check with constant space. The frequency method is also valid but slightly more mechanical. Demonstrating the one-pass logic signals stronger problem insight.
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.
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.
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.
Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)
According to the problem description, we know that in order to make all values in tops or all values in bottoms the same, the value must be one of tops[0] or bottoms[0].
Therefore, we design a function f(x) to represent the minimum number of rotations required to make all values equal to x. Then the answer is min{f(tops[0]), f(bottoms[0])}.
The calculation method of function f(x) is as follows:
We use two variables cnt1 and cnt2 to count the number of occurrences of x in tops and bottoms, respectively. We subtract the maximum value of cnt1 and cnt2 from n, which is the minimum number of rotations required to make all values equal to x. Note that if there are no values equal to x in tops and bottoms, the value of f(x) is a very large number, which we represent as n+1.
The time complexity is O(n), where n is the length of the array. The space complexity is 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. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| One-Pass Count Method | O(n) | O(1) | Best general solution. Quickly validates candidate values and computes minimum rotations in a single scan. |
| Max Frequency Element Method | O(n) | O(1) | Useful when reasoning through value frequencies (1–6). Good alternative if you prefer explicit counting logic. |
Minimum Domino Rotations for Equal Row - Leetcode 1007 - Python • NeetCode • 16,303 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