Watch 10 video solutions for Minimum Domino Rotations For Equal Row, a medium level problem involving Array, Greedy. This walkthrough by NeetCode has 16,303 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |