Minimum Domino Rotations For Equal Row [Medium] — Candidate Reduction + Greedy

Problem Statement#

You are given two arrays tops and bottoms, each of length n, representing the top and bottom faces of n dominoes laid in a row. In one rotation you may swap the top and bottom faces of any single domino (swapping is always the entire domino — you cannot pick a single face independently).

Return the minimum number of rotations needed so that all values in tops are the same, or all values in bottoms are the same. If it is impossible, return -1.

Constraints:

• 2 <= tops.length == bottoms.length <= 2 * 10^4
• 1 <= tops[i], bottoms[i] <= 6

Example 1:

tops    = [2, 1, 2, 4, 2, 2]
bottoms = [5, 2, 6, 2, 3, 2]
 
Output: 2
Explanation: Rotate domino 1 (top=1 → 2) and domino 4 (top=4 → 2)
             so tops becomes [2, 2, 2, 2, 2, 2]. Two rotations.

Example 2:

tops    = [3, 5, 1, 2, 3]
bottoms = [3, 6, 3, 3, 4]
 
Output: -1
Explanation: No single value can appear on all tops or all bottoms.

Why This Problem Matters#

LeetCode 1007 sits at an intersection that interviewers love: it looks easy enough that candidates rush to code, but the correct solution requires a non-obvious observation that reduces the search space from six candidates to at most two. Candidates who miss that observation end up writing six separate passes — technically correct but visibly unpolished. Candidates who spot it write a tight, O(n) single-pass solution that reads like a proof.

The problem is a favorite at Amazon and Google precisely because it rewards structured thinking over brute force. In an interview setting, the interviewer is not primarily watching whether your code compiles — they are watching whether you pause, reason about the constraints, and then announce "the answer must come from tops[0] or bottoms[0]" before writing a single line. That moment of insight is what separates a hire from a no-hire on this problem.

Beyond interview preparation, the underlying technique — using the first element of a collection to anchor the universe of valid answers, then verifying in a single scan — appears in calendar scheduling, constraint propagation in SAT solvers, and database query optimization. Any time you need to find a global property consistent across all elements of a large sequence, this "anchor on the first element" pattern is the first tool to reach for.

The greedy nature of the problem is also worth noting. At each domino you make the locally optimal choice: if the target value is on top, you do not rotate; if it is on the bottom only, you rotate; if it is on neither, the target is impossible. There is no backtracking, no dynamic programming, no need to consider future dominoes when deciding what to do at domino i. This is textbook greedy — optimal substructure with no conflicting choices.

The Candidate Reduction Insight#

This is the core of the entire problem and deserves its own section.

Question: What value could possibly appear on every domino?

Each domino has two faces, so the candidate set for a "universal" value is {tops[0], bottoms[0], tops[1], bottoms[1], ..., tops[n-1], bottoms[n-1]}. With face values from 1 to 6 and n up to 20,000, that sounds like many possibilities. But think about domino 0 specifically.

Claim: Any value that can unify the row must appear on domino 0 (either face).

Proof by contradiction: Suppose some value v can unify the row — meaning v appears on every domino. Then in particular, v must appear on domino 0. So v equals either tops[0] or bottoms[0]. No other value is possible.

This reduces the candidates from an arbitrary set to exactly two values: tops[0] and bottoms[0]. If tops[0] == bottoms[0], there is effectively one candidate (but the algorithm handles that correctly anyway — you just check the same value twice and take the same result).

Why is this so powerful? Instead of running six separate checks (one per possible face value 1-6), you run at most two. Each check is O(n), so the total time is O(n) rather than O(6n) — same asymptotic complexity, but the reduction also proves correctness: if neither tops[0] nor bottoms[0] can unify the row, no value can, and you return -1.

The check(target) Function#

For a given target, you walk every domino and ask: "Can I make this domino show target?"

• If tops[i] == target and bottoms[i] == target: no rotation needed. Both faces already show the target. Either position works; count neither.
• If tops[i] == target and bottoms[i] != target: the top is already correct, so no rotation needed to put target on top. But you would need a rotation to put target on bottom. So rot_top += 0, rot_bot += 1.
• If tops[i] != target and bottoms[i] == target: the bottom is correct, so no rotation needed to put target on bottom. But you need a rotation to put target on top. So rot_top += 1, rot_bot += 0.
• If tops[i] != target and bottoms[i] != target: this domino cannot show target at all. The target is impossible. Return infinity (or a sentinel value).

After walking all n dominoes, the minimum rotations for this target is min(rot_top, rot_bot) — the cheaper of putting target uniformly on top vs. uniformly on bottom.

The final answer is min(check(tops[0]), check(bottoms[0])). If both return infinity, return -1.

Visual Dry Run#

Let us trace the full algorithm on Example 1 step by step.

tops    = [2, 1, 2, 4, 2, 2]
bottoms = [5, 2, 6, 2, 3, 2]
indices =  0  1  2  3  4  5
 
Candidates: tops[0] = 2,  bottoms[0] = 5

Pass 1: check(target = 2)#

We track rot_top (rotations to make all tops = 2) and rot_bot (rotations to make all bottoms = 2).

i=0:  tops[0]=2, bottoms[0]=5
      top == target: no rotation needed for top row
      bot != target: need rotation for bottom row
      rot_top=0, rot_bot=1
 
i=1:  tops[1]=1, bottoms[1]=2
      top != target: need rotation for top row
      bot == target: no rotation needed for bottom row
      rot_top=1, rot_bot=1
 
i=2:  tops[2]=2, bottoms[2]=6
      top == target: no rotation needed for top row
      bot != target: need rotation for bottom row
      rot_top=1, rot_bot=2
 
i=3:  tops[3]=4, bottoms[3]=2
      top != target: need rotation for top row
      bot == target: no rotation needed for bottom row
      rot_top=2, rot_bot=2
 
i=4:  tops[4]=2, bottoms[4]=3
      top == target: no rotation needed for top row
      bot != target: need rotation for bottom row
      rot_top=2, rot_bot=3
 
i=5:  tops[5]=2, bottoms[5]=2
      top == target AND bot == target: no rotation needed either way
      rot_top=2, rot_bot=3
 
Result for target=2: min(rot_top=2, rot_bot=3) = 2

Pass 2: check(target = 5)#

i=0:  tops[0]=2, bottoms[0]=5
      top != target: need rotation for top row   → rot_top=1
      bot == target: no rotation for bottom row   → rot_bot=0
 
i=1:  tops[1]=1, bottoms[1]=2
      top != 5, bot != 5  → IMPOSSIBLE for target=5
      return infinity

Final answer#

min(check(2), check(5)) = min(2, infinity) = 2
 
Answer: 2  ✓

Tracing Example 2 (impossible case)#

tops    = [3, 5, 1, 2, 3]
bottoms = [3, 6, 3, 3, 4]
 
Candidates: tops[0]=3, bottoms[0]=3  (same value — one effective candidate)
 
check(target = 3):
  i=0: top=3, bot=3 → both match, rot_top=0, rot_bot=0
  i=1: top=5, bot=6 → neither is 3 → return infinity
 
check(target = 3) again (bottoms[0] is also 3): same result, infinity
 
min(infinity, infinity) = infinity → return -1  ✓

Common Mistakes#

Mistake 1: Checking All Six Values Instead of Two#

The most common brute-force instinct is to loop over possible target values {1, 2, 3, 4, 5, 6} and check each one. This is correct but misses the key insight. In an interview, writing this approach signals that you are not reasoning about constraints — you are applying brute force. The interviewer will likely prompt you: "Can you reduce the candidates?" If you cannot articulate why only tops[0] and bottoms[0] matter, you leave points on the table. Always justify the candidate reduction before coding.

Mistake 2: Not Handling the Case Where Both Faces Show the Target#

When tops[i] == target and bottoms[i] == target, neither rot_top nor rot_bot should be incremented — the domino already satisfies both conditions. A common bug is to write elif tops[i] != target: rot_top += 1 and elif bottoms[i] != target: rot_bot += 1 using elif incorrectly, causing this double-match case to be skipped without incrementing (which is correct) but then breaking the control flow when only one face matches. Use explicit if/elif/elif/else or inline the logic carefully.

Mistake 3: Returning Early from check Without Considering Both Candidates#

Some candidates write check to return -1 when the target is impossible, then call ans = check(tops[0]) and immediately return if it is not -1, skipping check(bottoms[0]). This is wrong. Consider tops = [1, 2], bottoms = [2, 1]. check(1) finds domino 1 has top=2, bot=1 — it needs a rotation for the top row. check(2) similarly finds domino 0 needs a rotation. Both candidates are valid with 1 rotation each. You must evaluate both and take the minimum. Never short-circuit to the first non-impossible result.

Mistake 4: Confusing rot_top and rot_bot Semantics#

rot_top is the number of rotations needed to make all tops equal to target. A rotation is needed at position i when tops[i] != target (you have to flip the domino to bring target from the bottom to the top). rot_bot is the number of rotations needed to make all bottoms equal to target — needed when bottoms[i] != target. Getting these semantics backwards leads to counting the complement (the non-rotations) instead of the rotations.

Mistake 5: Integer Overflow or Wrong Sentinel Value#

In Python this is not an issue since integers are arbitrary precision. In JavaScript, using Infinity as the sentinel is clean. The mistake is using n + 1 as the sentinel value (a finite number greater than any valid answer) and then forgetting to check for it properly when computing the final min. Always use a clearly distinct sentinel like Infinity / float('inf') so the impossibility check is unambiguous.

Solutions#

Python#

from typing import List
 
class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
 
        def check(target: int) -> int:
            """
            Returns the minimum rotations to make all tops == target
            OR all bottoms == target, for this specific target value.
            Returns float('inf') if target cannot appear on every domino.
            """
            # rot_top: rotations needed to put target on ALL top faces
            # rot_bot: rotations needed to put target on ALL bottom faces
            rot_top = 0
            rot_bot = 0
 
            for t, b in zip(tops, bottoms):
                if t != target and b != target:
                    # This domino has target on neither face — impossible
                    return float('inf')
                elif t != target:
                    # Target is only on the bottom; must rotate to put it on top
                    rot_top += 1
                elif b != target:
                    # Target is only on the top; must rotate to put it on bottom
                    rot_bot += 1
                # else: both faces show target — no rotation needed for either goal
 
            # Return the cheaper of the two goals
            return min(rot_top, rot_bot)
 
        # KEY INSIGHT: the unifying value must appear on domino 0.
        # So we only need to check tops[0] and bottoms[0] as candidates.
        candidate_a = tops[0]
        candidate_b = bottoms[0]
 
        # Evaluate both candidates and take the overall minimum
        ans = min(check(candidate_a), check(candidate_b))
 
        # If both candidates returned infinity, no value can unify the row
        return -1 if ans == float('inf') else ans

JavaScript#

/**
 * @param {number[]} tops
 * @param {number[]} bottoms
 * @return {number}
 */
var minDominoRotations = function(tops, bottoms) {
    const n = tops.length;
 
    /**
     * Returns the minimum rotations to make all tops == target
     * OR all bottoms == target.
     * Returns Infinity if target cannot appear on every domino.
     *
     * @param {number} target - the value we want to unify the row with
     * @returns {number}
     */
    function check(target) {
        // rotTop: rotations to put target on every top face
        // rotBot: rotations to put target on every bottom face
        let rotTop = 0;
        let rotBot = 0;
 
        for (let i = 0; i < n; i++) {
            const t = tops[i];
            const b = bottoms[i];
 
            if (t !== target && b !== target) {
                // Neither face shows target — this target is impossible
                return Infinity;
            } else if (t !== target) {
                // Target is on bottom only; rotate to bring it to the top
                rotTop++;
            } else if (b !== target) {
                // Target is on top only; rotate to bring it to the bottom
                rotBot++;
            }
            // Both faces show target: no rotation needed for either goal
        }
 
        // Cheaper of: making all tops = target vs. making all bottoms = target
        return Math.min(rotTop, rotBot);
    }
 
    // KEY INSIGHT: the answer value must appear on domino 0.
    // Only tops[0] and bottoms[0] are valid candidates.
    const candidateA = tops[0];
    const candidateB = bottoms[0];
 
    // Evaluate both candidates and pick the global minimum
    const ans = Math.min(check(candidateA), check(candidateB));
 
    // Infinity means both candidates failed — the row cannot be unified
    return ans === Infinity ? -1 : ans;
};

Complexity Analysis#

Why not O(6n)? Checking all six face values would be O(6n), which simplifies to O(n) asymptotically but is three times more work in practice and — more importantly — reveals a lack of insight to the interviewer. The candidate-reduction observation makes the algorithm cleaner and faster by a constant factor that matters.

Space: The only extra memory used is rot_top, rot_bot, and the loop variables. There is no hash map, no auxiliary array, no recursion stack. This is genuinely O(1) space.

Edge cases with no extra cost: When tops[0] == bottoms[0], we call check twice with the same argument and get the same result both times. The minimum of two identical values is that value, so correctness is preserved. This does not require a special case.

Follow-up Questions#

These are real questions that FAANG interviewers ask after the base solution is accepted. Prepare answers to all of them.

Follow-up 1: What if dominoes have more than two faces — say, dice (six faces)?#

With dice, each "domino" is a cube with six faces. You can rotate it into any of six orientations. The candidate reduction still applies: the unifying value must appear on die 0. But now instead of two candidates (top/bottom of the first domino), you have up to six candidates (each face of die 0). For each candidate, walk all dice and check whether the target face exists on that die. If it does, you need to decide: does rotating into the target-on-top orientation require a rotation? This generalizes cleanly — the core algorithm remains O(candidates * n) and the candidate set grows from 2 to at most 6.

Follow-up 2: What if you want the minimum rotations to make all tops AND all bottoms equal (simultaneously)?#

Now the constraint is tighter: every domino must show the same value on top and the same value on the bottom. This requires every domino to be either a double (both faces the same) or to have exactly the two required values (one on each face). The algorithm becomes: for each candidate pair (top_val, bot_val), count how many dominoes need rotation. But the candidate pairs are again constrained by domino 0 — the pair must be a permutation of {tops[0], bottoms[0]}. At most two ordered pairs to check.

Follow-up 3: What if the input is a stream — dominoes arrive one by one?#

In the streaming setting, you cannot look at tops[0] and bottoms[0] upfront to pick candidates, because when you see domino 0 you do not yet know whether the target will be tops[0] or bottoms[0] (or neither — though that cannot happen). The approach is: upon seeing domino 0, initialize two candidate states — one tracking tops[0] and one tracking bottoms[0]. For each subsequent domino, update both candidate states independently, eliminating a candidate if it becomes impossible. This is the standard "maintain a set of active candidates and prune on each observation" pattern used in streaming constraint satisfaction.

Follow-up 4: Can you solve this in one pass instead of two?#

Yes. Instead of calling check(tops[0]) and then check(bottoms[0]) sequentially, you can interleave the two passes in a single loop. Maintain four counters — rot_top_a, rot_bot_a for candidate A, and rot_top_b, rot_bot_b for candidate B — and a boolean flag for each indicating whether the candidate is still viable. On each iteration, update both candidates simultaneously. This halves the constant factor. Time is still O(n) and space is still O(1), but you only traverse the arrays once. In cache-sensitive environments with large n, the single-pass variant is meaningfully faster due to better cache locality.

Follow-up 5: What if you want to minimize total cost where each rotation has a non-uniform cost?#

Suppose rotating domino i costs cost[i] instead of a uniform 1. Now you cannot simply count rotations — you need to sum costs. The structure of the algorithm remains the same: check each candidate, and for each domino that needs to be rotated (top or bottom, depending on which goal you are pursuing), add cost[i] instead of 1. The greedy correctness is unchanged because at each domino you are still making an irrevocable binary choice (rotate or not), and both choices are independent across dominoes.

This Pattern Solves#

The general pattern: when you need a value consistent across all elements of a sequence, anchor on the first element to enumerate candidates, then verify each candidate in a linear scan. This reduces an open-ended search over all possible values to a fixed, small set of candidates — a form of constraint propagation that turns quadratic brute force into linear elegance.

Key Takeaways#

• The winning value must appear on every domino (either top or bottom), so it must appear on the first domino. At most 2 candidates: tops[0] and bottoms[0].
• For each candidate value, scan all dominoes: if neither top nor bottom equals the candidate, return -1 (impossible). Otherwise count rotations needed to unify tops or bottoms.
• The minimum of min(rotations_top, rotations_bottom) for each valid candidate is the answer; take the min across both candidates.
• O(n) time, O(1) space — two linear scans total.
• If the same value appears in both tops[0] and bottoms[0] (a double domino), it still counts as one candidate since both faces are the same value.
• Return -1 only after exhausting both candidates — not inside the inner loop on first failure.
• This "anchor on first element to enumerate candidates" pattern appears in Majority Element (LC 169, Boyer-Moore voting) and Find the Duplicate (LC 287).