LeetCode 1007: Minimum Domino Rotations For Equal Row

Problem Restatement

We have n dominoes arranged in a row.

For domino i, tops[i] is the value on the top face and bottoms[i] is the value on the bottom face.

In one rotation, we can swap the top and bottom of any domino.

We need to return the minimum number of rotations so that either all tops are equal or all bottoms are equal.

If it is impossible, return -1.

The official constraints state that 2 <= tops.length == bottoms.length <= 2 * 10^4 and 1 <= tops[i], bottoms[i] <= 6.

Input and Output

Function shape:

def minDominoRotations(tops: list[int], bottoms: list[int]) -> int:
    ...

Examples

Example 1:

tops =    [2, 1, 2, 4, 2, 2]
bottoms = [5, 2, 6, 2, 3, 2]

Target value 2 appears in each column as either top or bottom.

Rotations needed to make all tops 2: rotate columns 1, 3 → 2 rotations.

To make every top value equal to 2, rotate the columns where the top is not 2 but the bottom is 2: columns 1 and 3. That takes 2 rotations.

To make every bottom value equal to 2, more rotations are needed. The minimum is therefore 2.

Answer:

2

Example 2:

tops =    [3, 5, 1, 2, 3]
bottoms = [3, 6, 3, 3, 4]

No value appears in every column (either top or bottom).

Answer:

-1

Key Insight

The target value must appear in every domino (either top or bottom).

The only possible target values are tops[0] or bottoms[0], because the first domino must participate and contribute either its top or bottom to the uniform row.

For each candidate value v:

• Count how many tops need to be rotated to make all tops v.
• Count how many bottoms need to be rotated to make all bottoms v.
• If the candidate is impossible (some domino has neither top nor bottom equal to v), skip it.

Algorithm

Define a helper function check(v):

1. For each domino i:
   • If neither tops[i] nor bottoms[i] equals v, return -1.
   • If tops[i] != v, increment the rotation count for tops.
   • If bottoms[i] != v, increment the rotation count for bottoms.
2. Return the minimum of the two rotation counts.

Call check(tops[0]) and check(bottoms[0]).

Return the minimum non-negative result.

Correctness

If there is a solution, then some value v must appear in every domino. That v must appear in the first domino as either tops[0] or bottoms[0]. So trying only these two candidates is exhaustive.

For a given candidate v, the optimal number of rotations is the minimum between making all tops equal to v and making all bottoms equal to v.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def minDominoRotations(self, tops: list[int], bottoms: list[int]) -> int:
        def check(v: int) -> int:
            rot_top = 0
            rot_bot = 0
            for t, b in zip(tops, bottoms):
                if t != v and b != v:
                    return float("inf")
                if t != v:
                    rot_top += 1
                if b != v:
                    rot_bot += 1
            return min(rot_top, rot_bot)

        result = min(check(tops[0]), check(bottoms[0]))
        return result if result != float("inf") else -1

Code Explanation

The helper check(v) tries to make all values equal to v:

if t != v and b != v:
    return float("inf")

If a domino has neither face equal to v, this candidate is impossible.

Otherwise count rotations needed for tops and bottoms separately:

if t != v:
    rot_top += 1
if b != v:
    rot_bot += 1

Return the better of the two:

return min(rot_top, rot_bot)

Try both candidates and return the minimum:

result = min(check(tops[0]), check(bottoms[0]))
return result if result != float("inf") else -1

Testing

def run_tests():
    s = Solution()

    assert s.minDominoRotations([2, 1, 2, 4, 2, 2], [5, 2, 6, 2, 3, 2]) == 2
    assert s.minDominoRotations([3, 5, 1, 2, 3], [3, 6, 3, 3, 4]) == -1
    assert s.minDominoRotations([1, 1, 1], [2, 3, 4]) == 0
    assert s.minDominoRotations([1, 2, 1], [2, 1, 2]) == 1

    print("all tests passed")

run_tests()