Minimum Domino Rotations For Equal Row: Greedy Candidate Check

You have two rows of dominoes, represented by arrays tops and bottoms, each of length n. In one move, you can rotate a single domino, swapping its top and bottom values. Return the minimum number of rotations so that all values in tops are the same, or all values in bottoms are the same. If no valid arrangement exists, return -1.

This is LeetCode 1007: Minimum Domino Rotations For Equal Row, a medium problem that tests your ability to identify candidate values and count the minimum swaps needed using a greedy approach. The trick is recognizing that only two values can possibly work, and checking each one takes linear time.

Why this problem matters

This problem is a clean example of greedy candidate elimination. Instead of trying all six possible domino face values (1 through 6), you observe that the answer must appear in the very first domino. That single observation cuts your search space from six candidates down to at most two. From there, you just count rotations and take the minimum.

The pattern of narrowing your candidate set using a structural constraint appears in many other problems. Majority Element uses Boyer-Moore voting to maintain a single candidate. Gas Station resets its candidate start index when the running sum goes negative. Here, the first domino constrains which values are even worth checking. Learning to spot these constraints early is one of the most valuable greedy skills you can develop.

The key insight

If every domino in the final arrangement shows the same value on top (or on bottom), then that value must appear in every single domino, either on the top face or the bottom face. Since domino 0 must also contain this value, the target is either tops[0] or bottoms[0]. No other value can possibly work.

This means the algorithm is:

1. Let a = tops[0] and b = bottoms[0]. These are the only two candidates.
2. For each candidate, scan all dominoes. If any domino has the candidate on neither face, that candidate is impossible.
3. If the candidate is valid, count how many rotations are needed to put it in every top position, and how many to put it in every bottom position. Take the smaller count.
4. Return the minimum across both candidates. If neither candidate works, return -1.

The solution

def minDominoRotations(tops, bottoms):
    def check(target):
        rotations_top = 0
        rotations_bot = 0
        for i in range(len(tops)):
            if tops[i] != target and bottoms[i] != target:
                return float('inf')
            elif tops[i] != target:
                rotations_top += 1
            elif bottoms[i] != target:
                rotations_bot += 1
        return min(rotations_top, rotations_bot)

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

The check function does all the work. Given a target value, it walks through every domino and counts how many rotations you would need to make every top equal to the target (rotations_top) and how many to make every bottom equal to the target (rotations_bot). If any domino has the target on neither face, it returns infinity to signal failure.

The outer function calls check for both candidates (tops[0] and bottoms[0]), takes the minimum, and converts infinity to -1.

Visual walkthrough

Notice that in step 2, every domino has at least one face with value 2. That confirms 2 is a valid candidate. Steps 3 and 4 count the rotations for each direction, and step 5 picks the minimum. The entire process is a single pass per candidate.

Complexity analysis

Time: You check at most two candidate values. For each candidate, you scan all n dominoes once. That gives you O(2n), which simplifies to O(n).

Space: You only use a few integer counters. No extra arrays, no hash maps. O(1).

This is optimal. You must look at every domino at least once to know whether a valid arrangement exists, so O(n) is a lower bound. And you do not need any auxiliary storage beyond the counters.

The building blocks

1. Candidate value identification

The pattern of using structural constraints to limit which values are worth checking:

candidates = [sequence[0]]
for candidate in candidates:
    if is_valid(candidate, sequence):
        return compute_answer(candidate)
return -1

In this problem, the first domino constrains the candidates to at most two values. In Majority Element, the voting algorithm maintains one candidate at a time. In Two Sum, you check whether the complement of each element exists in the map. The core idea is the same: do not search blindly over all possibilities when the problem structure tells you exactly where to look.

2. Counting minimum rotations

The pattern of scanning a sequence and counting the minimum operations needed to achieve a target configuration:

cost_option_a = 0
cost_option_b = 0
for i in range(n):
    if cannot_achieve_target(i):
        return infinity
    elif needs_operation_for_a(i):
        cost_option_a += 1
    elif needs_operation_for_b(i):
        cost_option_b += 1
return min(cost_option_a, cost_option_b)

You track costs for both options (all tops vs. all bottoms) simultaneously in one pass. This avoids scanning the array twice and keeps the logic clean. The same pattern works whenever you need to compare two strategies and pick the cheaper one.

Edge cases

Before submitting, make sure your solution handles these:

• All tops already the same value tops = [2,2,2], bottoms = [1,3,4]: zero rotations needed. The check function returns 0 because rotations_top never increments.
• No valid rotation possible tops = [1,2,3], bottoms = [4,5,6]: neither tops[0]=1 nor bottoms[0]=4 appears in every domino. Both calls to check return infinity. Return -1.
• Single domino tops = [1], bottoms = [2]: the answer is always 0. A single domino trivially satisfies "all values in tops are the same."
• tops[0] equals bottoms[0] tops = [3,3,5], bottoms = [3,5,3]: both candidates are 3. The function checks the same value twice, which is harmless. Returns 1 rotation.
• Every domino is identical tops = [4,4,4], bottoms = [4,4,4]: zero rotations, since both rows already match.
• Target only on bottom faces tops = [1,3,5], bottoms = [2,2,2]: checking candidate tops[0]=1 fails (domino 1 has neither 1 on top nor bottom). Checking bottoms[0]=2 succeeds with 0 bottom rotations (already all 2s on bottom). Returns 0.

From understanding to recall

You have read the greedy solution and the candidate elimination logic makes sense. Two candidates, one pass each, take the minimum. But will you remember the details when you see this problem in an interview?

The subtle parts matter: recognizing that only tops[0] and bottoms[0] are candidates, tracking both rotation directions simultaneously, and using infinity as a sentinel for impossible candidates. These are easy to forget if you have only read the solution once.

Spaced repetition fixes this. You write the check function from scratch at increasing intervals until the pattern is automatic. After a few rounds, you see "make a row uniform with swaps" and the candidate elimination approach flows out without hesitation.

The greedy candidate check is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Majority Element - Candidate-based approach (Boyer-Moore)
• Gas Station - Greedy with single-pass candidate selection
• Lemonade Change - Greedy decision-making at each step

CodeBricks breaks the minimum domino rotations LeetCode problem into its candidate identification and rotation counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy candidate elimination question shows up in your interview, you do not think about it. You just write it.