Fewest flips to make a domino row match: only the first domino's two values can work, so try each and keep the cheaper side.
▼The problem
LeetCode 1007 (Medium). tops[i] and bottoms[i] are the top and bottom halves of domino i (values 1 to 6). A rotation swaps the two halves of one domino. Return the minimum number of rotations that makes every value in tops equal, or every value in bottoms equal; if it cannot be done, return -1.
Examples (LeetCode's): tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] → 2 (rotate dominoes 1 and 3: every top is 2) and tops = [3,5,1,2,3], bottoms = [3,6,3,3,4] → -1 (no value is on every domino).
The solution
def min_domino_rotations(tops, bottoms):
def cost(x):
top = bottom = 0
for a, b in zip(tops, bottoms):
if a != x and b != x:
return float('inf')
if a != x: top += 1
if b != x: bottom += 1
return min(top, bottom)
best = min(cost(tops[0]), cost(bottoms[0]))
return -1 if best == float('inf') else bestTranscript
Minimum Domino Rotations for Equal Row. Each domino has a top and a bottom number, and a rotation swaps them. Return the fewest rotations that make every top equal, or every bottom equal, or minus one.
Here, flipping dominoes one and three puts a two on every top: two rotations. In the second example, no number is on every domino: minus one.
The slow way: try every face from one to six, for both rows: twelve passes. Trying every set of flips is worse: two to the n.
The key idea: the winner must be on every domino, including domino zero, so only its two faces can win. For each candidate, walk the row once. A domino with neither half rules it out. Otherwise, count flips to put it on top, and flips to put it on the bottom; keep the smaller.
In code, cost walks the pairs, gives up on a domino without x, and counts top and bottom flips. Try both faces of domino zero, and return the best, or minus one.
Walking example one: candidates two and five. For two: domino zero needs a bottom flip, one a top flip, two a bottom flip, three a top flip, four a bottom flip, and five shows two on both. Two top flips beat three bottom flips. For five, domino one has neither half: out. The answer is two.
At most two passes over n dominoes: O of n time, and O of one space.
Read domino zero, walk the row, keep the cheaper side. That's Minimum Domino Rotations.