Minimum Domino Rotations For Equal Row — Problem & Solution
Minimum Domino Rotations For Equal Row solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Domino Rotations For Equal Row is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A row of dominoes is laid out left to right. Domino i shows tops[i] on its top half and bottoms[i] on its bottom half; every half shows a number from 1 to 6.
A rotation flips one domino so its top and bottom values trade places.
Return the minimum number of rotations after which all top values are equal, or all bottom values are equal. If neither can be achieved, return -1.
Example 1
Input: tops = [3,1,3,3], bottoms = [1,3,4,5]
Output: 1
Explanation: Rotating domino 1 makes the top row `[3,3,3,3]`.
Example 2
Input: tops = [2,5,1], bottoms = [6,2,4]
Output: -1
Explanation: No single value appears on every domino.
Example 3
Input: tops = [4,4], bottoms = [4,4]
Output: 0
Constraints
2 <= tops.length <= 2 * 10^4bottoms.length == tops.length1 <= tops[i], bottoms[i] <= 6
Hints for Minimum Domino Rotations For Equal Row
Hint 1
If a whole row ends up showing value
x, thenxmust appear on every domino, in particular on domino 0.Hint 2
So only two candidates matter:
tops[0]andbottoms[0].Hint 3
For a candidate
x, fail if some domino showsxon neither half; otherwise the cost for the top row is the number of dominoes whose top is notx, and similarly for the bottom row.
How to solve Minimum Domino Rotations For Equal Row
The common value must appear on the first domino, so there are at most two candidates, and each is checked in one linear pass.
Approach
- For each candidate
xin{tops[0], bottoms[0]}: - Walk the dominoes. If neither half shows
x, the candidate fails. - Otherwise count
rotTop(dominoes whose top is notx— they must be flipped to fill the top row) androtBottom(likewise for the bottom). - The candidate costs
min(rotTop, rotBottom). Return the best over the candidates, or-1if both fail.
Why it works
A domino showing x on one half can always be oriented to put x in the target row, at a cost of one rotation exactly when x is currently on the other side. Choosing the row whose current mismatches are fewer is optimal for that x, and any feasible x must come from domino 0.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A domino showing
xon both halves never needs a rotation — count mismatches, not matches on the other side. - Check both rows: making the bottom row uniform may be cheaper than the top.
- Trying all six values also works; restricting to domino 0's values is just a shortcut.
Reference solution
Python
from typing import List
def minDominoRotations(tops: List[int], bottoms: List[int]) -> int:
def cost(x):
rot_top = rot_bottom = 0
for t, b in zip(tops, bottoms):
if t != x and b != x:
return -1
if t != x:
rot_top += 1
if b != x:
rot_bottom += 1
return min(rot_top, rot_bottom)
best = -1
for x in (tops[0], bottoms[0]):
c = cost(x)
if c != -1 and (best == -1 or c < best):
best = c
return bestJava
private static int dominoCost(int[] tops, int[] bottoms, int x) {
int rotTop = 0, rotBottom = 0;
for (int i = 0; i < tops.length; i++) {
if (tops[i] != x && bottoms[i] != x) return -1;
if (tops[i] != x) rotTop++;
if (bottoms[i] != x) rotBottom++;
}
return Math.min(rotTop, rotBottom);
}
public static int minDominoRotations(int[] tops, int[] bottoms) {
int a = dominoCost(tops, bottoms, tops[0]);
int b = dominoCost(tops, bottoms, bottoms[0]);
if (a == -1) return b;
if (b == -1) return a;
return Math.min(a, b);
}C++
int dominoCost1007(vector<int>& tops, vector<int>& bottoms, int x) {
int rotTop = 0, rotBottom = 0;
for (size_t i = 0; i < tops.size(); i++) {
if (tops[i] != x && bottoms[i] != x) return -1;
if (tops[i] != x) rotTop++;
if (bottoms[i] != x) rotBottom++;
}
return min(rotTop, rotBottom);
}
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
int a = dominoCost1007(tops, bottoms, tops[0]);
int b = dominoCost1007(tops, bottoms, bottoms[0]);
if (a == -1) return b;
if (b == -1) return a;
return min(a, b);
}JavaScript
var minDominoRotations = function(tops, bottoms) {
var cost = function(x) {
var rotTop = 0, rotBottom = 0;
for (var i = 0; i < tops.length; i++) {
if (tops[i] !== x && bottoms[i] !== x) return -1;
if (tops[i] !== x) rotTop++;
if (bottoms[i] !== x) rotBottom++;
}
return Math.min(rotTop, rotBottom);
};
var a = cost(tops[0]), b = cost(bottoms[0]);
if (a === -1) return b;
if (b === -1) return a;
return Math.min(a, b);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms