LeetCode 1007 - Minimum Domino Rotations For Equal Row

LeetCode Problem 1007

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us two arrays, tops and bottoms, representing a sequence of dominoes. Each domino has two values, one on the top half and one on the bottom half. For the ith domino, the top value is tops[i] and the bottom value is bottoms[i].

We are allowed to rotate any domino individually. Rotating a domino swaps its top and bottom values. The goal is to determine the minimum number of rotations required so that either:

• every value in the tops row becomes the same, or
• every value in the bottoms row becomes the same.

If it is impossible to make either row uniform, we return -1.

The key detail is that we are not trying to make both rows equal simultaneously. We only need one row to contain identical values.

The constraints are important:

• The length of the arrays can be as large as 2 * 10^4
• Each domino value is between 1 and 6

The small value range is a strong hint that the problem may have a compact greedy or counting-based solution. A brute-force approach that tries many rotation combinations would quickly become infeasible because each domino has two possible states, leading to exponential growth.

Several edge cases are worth identifying early:

• The arrays may already contain a uniform row, requiring 0 rotations.
• Some dominoes may already contain the target value on both sides.
• It may be impossible because at least one domino lacks the required target value entirely.
• Multiple target values may appear possible, but only one yields the minimum number of rotations.
• The smallest valid input size is 2, so we should ensure no assumptions rely on larger arrays.

The problem guarantees that both arrays have equal length and contain only integers from 1 to 6.

Approaches

Brute Force Approach

A straightforward brute-force solution would try every possible target value from 1 through 6. For each target, we would check whether it is possible to make all top values equal to that target or all bottom values equal to that target.

For every domino:

• If neither side contains the target value, the attempt fails immediately.
• Otherwise, we count how many rotations are needed.

This approach is correct because there are only six possible values that could become the final uniform value. By exhaustively checking all of them, we guarantee that we find the minimum valid rotation count.

Even though this is called "brute force", it is actually efficient enough because the value range is tiny. However, we can optimize further using an important observation.

Key Insight

If a solution exists, then the final uniform value must be either:

• tops[0], or
• bottoms[0]

Why?

Consider the first domino. In any valid final configuration, the chosen uniform value must appear somewhere on this domino. Since the first domino only contains tops[0] and bottoms[0], no other value can possibly become the final uniform value.

This observation dramatically reduces the search space from six possible candidates to at most two candidates.

For each candidate value, we compute:

• rotations needed to make the top row uniform
• rotations needed to make the bottom row uniform

Then we take the minimum valid result.

This gives a clean greedy solution with linear time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(6n)	O(1)	Try every possible domino value from 1 to 6
Optimal	O(n)	O(1)	Only check candidates from the first domino

Algorithm Walkthrough

1. Select two possible candidate values:

• tops[0]
• bottoms[0]

Any valid final value must appear on the first domino, so these are the only candidates worth checking. 2. Create a helper function that evaluates one candidate value.

This function determines:

• how many rotations are needed to make all top values equal to the candidate
• how many rotations are needed to make all bottom values equal to the candidate

3. Iterate through every domino.

For each index i:

• If neither tops[i] nor bottoms[i] equals the candidate, then this candidate is impossible.

• Otherwise:

• if tops[i] is not the candidate, we would need one rotation to place the candidate on top

• if bottoms[i] is not the candidate, we would need one rotation to place the candidate on bottom

4. After processing all dominoes:

• the minimum rotations for this candidate is:

min(top_rotations, bottom_rotations) 5. Evaluate both candidates from the first domino. 6. Return the minimum valid result:

• if both candidates fail, return -1
• otherwise return the smaller rotation count

Why it works

The correctness depends on a simple invariant:

For a value x to become the final uniform value, every domino must contain x on at least one side.

Since the first domino only contains tops[0] and bottoms[0], any valid solution must use one of those two values. Checking both candidates guarantees completeness. For each candidate, the rotation counts are computed greedily and independently for every domino, which is optimal because each domino decision is local and does not affect others.

Python Solution

from typing import List

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def rotations_needed(target: int) -> int:
            top_rotations = 0
            bottom_rotations = 0

            for top, bottom in zip(tops, bottoms):
                if top != target and bottom != target:
                    return float('inf')

                if top != target:
                    top_rotations += 1

                if bottom != target:
                    bottom_rotations += 1

            return min(top_rotations, bottom_rotations)

        candidate1 = tops[0]
        candidate2 = bottoms[0]

        result = min(
            rotations_needed(candidate1),
            rotations_needed(candidate2)
        )

        return -1 if result == float('inf') else result

The implementation starts by defining a helper function named rotations_needed. This function checks whether a given target value can make either row uniform.

Two counters are maintained:

• top_rotations counts how many swaps are required to make the top row equal to the target.
• bottom_rotations counts how many swaps are required to make the bottom row equal to the target.

For each domino:

• If neither side contains the target, the candidate immediately becomes impossible.
• If the top side is not equal to the target, a rotation would be required to place the target on top.
• Similarly, if the bottom side is not equal to the target, a rotation would be required to place the target on bottom.

After scanning all dominoes, we return the smaller of the two rotation counts because the problem only requires one row to become uniform.

The main function only checks the two valid candidates from the first domino. Finally, if both candidates fail, we return -1.

Go Solution

package main

import "math"

func minDominoRotations(tops []int, bottoms []int) int {
	rotationsNeeded := func(target int) int {
		topRotations := 0
		bottomRotations := 0

		for i := 0; i < len(tops); i++ {
			top := tops[i]
			bottom := bottoms[i]

			if top != target && bottom != target {
				return math.MaxInt32
			}

			if top != target {
				topRotations++
			}

			if bottom != target {
				bottomRotations++
			}
		}

		if topRotations < bottomRotations {
			return topRotations
		}

		return bottomRotations
	}

	candidate1 := tops[0]
	candidate2 := bottoms[0]

	result1 := rotationsNeeded(candidate1)
	result2 := rotationsNeeded(candidate2)

	result := result1
	if result2 < result {
		result = result2
	}

	if result == math.MaxInt32 {
		return -1
	}

	return result
}

The Go implementation follows the same logic as the Python version. Since Go does not have float('inf'), we use math.MaxInt32 as a sentinel value representing an impossible configuration.

Slices are used directly without additional allocations, keeping the space complexity constant. Integer overflow is not a concern because the maximum number of rotations is bounded by 2 * 10^4.

Worked Examples

Example 1

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

The candidates are:

• 2
• 5

We first test candidate 2.

Index	Top	Bottom	Action	Top Rotations	Bottom Rotations
0	2	5	Top already correct	0	1
1	1	2	Rotate to top	1	1
2	2	6	Top already correct	1	2
3	4	2	Rotate to top	2	2
4	2	3	Top already correct	2	3
5	2	2	Already correct both ways	2	3

Final result for candidate 2:

min(2, 3) = 2

Now test candidate 5.

Index	Top	Bottom	Result
0	2	5	Valid
1	1	2	Impossible

Candidate 5 fails immediately.

Final answer:

2

Example 2

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

Candidates:

• 3
• 3

We only effectively test 3.

Index	Top	Bottom	Result
0	3	3	Valid
1	5	6	Impossible

Since neither side of domino 1 contains 3, it is impossible to make all dominoes equal to 3.

No valid candidate exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each domino is processed at most twice
Space	O(1)	Only a few counters and variables are used

The algorithm performs a linear scan for each candidate value. Since there are at most two candidates, the total work is proportional to 2n, which simplifies to O(n). No auxiliary data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.minDominoRotations(
    [2,1,2,4,2,2],
    [5,2,6,2,3,2]
) == 2  # Example 1

assert sol.minDominoRotations(
    [3,5,1,2,3],
    [3,6,3,3,4]
) == -1  # Example 2

assert sol.minDominoRotations(
    [1,1,1,1],
    [2,2,2,2]
) == 0  # Already uniform top row

assert sol.minDominoRotations(
    [2,2,2,2],
    [2,2,2,2]
) == 0  # Both rows already uniform

assert sol.minDominoRotations(
    [1,2],
    [2,1]
) == 1  # Minimum size input

assert sol.minDominoRotations(
    [1,2,1,1,1,2,2,2],
    [2,1,2,2,2,2,2,2]
) == 1  # Only one rotation needed

assert sol.minDominoRotations(
    [1,2,3,4,5,6],
    [6,5,4,3,2,1]
) == -1  # No valid target

assert sol.minDominoRotations(
    [6,6,6,6],
    [1,2,3,4]
) == 0  # Uniform without rotations

assert sol.minDominoRotations(
    [1,1,2,1],
    [2,2,1,2]
) == 1  # One rotation required

assert sol.minDominoRotations(
    [2,1,2,2,2],
    [2,2,2,1,2]
) == 1  # Mixed configuration

Test	Why
Example 1	Validates standard successful case
Example 2	Validates impossible configuration
Already uniform top row	Ensures zero rotations handled correctly
Both rows uniform	Confirms redundant rotations are avoided
Minimum size input	Verifies handling of smallest valid arrays
One rotation needed	Tests near-uniform configuration
No valid target	Ensures impossible states return -1
Uniform without rotations	Confirms greedy counting logic
One rotation required	Tests partial mismatch handling
Mixed configuration	Validates counting across multiple swaps

Edge Cases

One important edge case occurs when the rows are already uniform. For example:

tops = [2,2,2]
bottoms = [1,1,1]

A buggy implementation might still perform unnecessary rotations or incorrectly count swaps. This implementation correctly detects that no rotations are required because the top row already matches the candidate value everywhere.

Another important case is when a domino does not contain the candidate value on either side. For example:

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

If we try to make every value equal to 1, the second domino blocks the solution because neither side contains 1. The implementation handles this immediately with the condition:

if top != target and bottom != target:

This guarantees impossible candidates fail early.

A third edge case involves dominoes where both sides already equal the target value. For example:

tops = [2,2,2]
bottoms = [2,2,2]

In this scenario, rotating changes nothing and should not increase the rotation count. The implementation naturally handles this because neither rotation counter increments when both sides already match the target.

A final subtle case is when both candidates from the first domino are identical. For example:

tops = [3,1,2]
bottoms = [3,3,3]

Both candidates become 3. The implementation still works correctly because evaluating the same candidate twice does not affect correctness, only a negligible constant factor in runtime.