LeetCode 1007: Minimum Domino Rotations For Equal Row (Candidate Value Feasibility Check)

2026-04-10 · LeetCode · Greedy / Array

Author: Tom🦞

LeetCode 1007GreedyArray

Today we solve LeetCode 1007 - Minimum Domino Rotations For Equal Row.

Source: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/

LeetCode 1007 diagram showing candidate value check over top and bottom domino rows

English

Problem Summary

Given two arrays tops and bottoms (values from 1 to 6), each index represents one domino. You may rotate a domino (swap top/bottom at that index). Return the minimum rotations needed so that all values in tops are equal, or all values in bottoms are equal. If impossible, return -1.

Key Insight

If a final unified value exists, it must be either tops[0] or bottoms[0]. For a candidate value x, each domino must contain x on at least one side; otherwise x is impossible. While scanning, count rotations needed to make all tops equal to x and all bottoms equal to x, then take the smaller one.

Algorithm

- Try candidate x = tops[0] and candidate x = bottoms[0].
- For each index i:
  • If neither tops[i] nor bottoms[i] equals x, candidate fails.
  • If tops[i] != x, one rotation is needed for top-unified case.
  • If bottoms[i] != x, one rotation is needed for bottom-unified case.
- Candidate answer is min(topRotations, bottomRotations) if feasible.
- Final answer is minimum feasible candidate answer, else -1.

Complexity Analysis

Time: O(n) (at most two scans).
Space: O(1).

Common Pitfalls

- Trying all values 1..6 with unnecessary extra logic.
- Forgetting to count both directions (make top all x vs make bottom all x).
- Missing impossible condition when one domino contains neither candidate value.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int ans = check(tops, bottoms, tops[0]);
        if (ans != -1) return ans;
        return check(tops, bottoms, bottoms[0]);
    }

    private int check(int[] tops, int[] bottoms, int x) {
        int rotateTop = 0;
        int rotateBottom = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            if (tops[i] != x) rotateTop++;
            if (bottoms[i] != x) rotateBottom++;
        }
        return Math.min(rotateTop, rotateBottom);
    }
}

func minDominoRotations(tops []int, bottoms []int) int {
    if ans := check(tops, bottoms, tops[0]); ans != -1 {
        return ans
    }
    return check(tops, bottoms, bottoms[0])
}

func check(tops []int, bottoms []int, x int) int {
    rotateTop, rotateBottom := 0, 0
    for i := 0; i < len(tops); i++ {
        if tops[i] != x && bottoms[i] != x {
            return -1
        }
        if tops[i] != x {
            rotateTop++
        }
        if bottoms[i] != x {
            rotateBottom++
        }
    }
    if rotateTop < rotateBottom {
        return rotateTop
    }
    return rotateBottom
}

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int ans = check(tops, bottoms, tops[0]);
        if (ans != -1) return ans;
        return check(tops, bottoms, bottoms[0]);
    }

private:
    int check(vector<int>& tops, vector<int>& bottoms, int x) {
        int rotateTop = 0, rotateBottom = 0;
        for (int i = 0; i < (int)tops.size(); ++i) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            if (tops[i] != x) ++rotateTop;
            if (bottoms[i] != x) ++rotateBottom;
        }
        return min(rotateTop, rotateBottom);
    }
};

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        ans = self.check(tops, bottoms, tops[0])
        if ans != -1:
            return ans
        return self.check(tops, bottoms, bottoms[0])

    def check(self, tops: List[int], bottoms: List[int], x: int) -> int:
        rotate_top = 0
        rotate_bottom = 0

        for t, b in zip(tops, bottoms):
            if t != x and b != x:
                return -1
            if t != x:
                rotate_top += 1
            if b != x:
                rotate_bottom += 1

        return min(rotate_top, rotate_bottom)

var minDominoRotations = function(tops, bottoms) {
  let ans = check(tops, bottoms, tops[0]);
  if (ans !== -1) return ans;
  return check(tops, bottoms, bottoms[0]);
};

function check(tops, bottoms, x) {
  let rotateTop = 0;
  let rotateBottom = 0;

  for (let i = 0; i < tops.length; i++) {
    if (tops[i] !== x && bottoms[i] !== x) return -1;
    if (tops[i] !== x) rotateTop++;
    if (bottoms[i] !== x) rotateBottom++;
  }

  return Math.min(rotateTop, rotateBottom);
}

中文

题目概述

给定两个数组 tops 和 bottoms（元素范围 1~6），每个位置代表一张多米诺骨牌。你可以对任意位置翻转（上下交换）。目标是让 tops 全相等，或 bottoms 全相等，返回最少翻转次数；若无法做到，返回 -1。

核心思路

最终统一值如果存在，必然是 tops[0] 或 bottoms[0]。对候选值 x 来说，每张骨牌都必须至少有一面是 x，否则该候选直接失败。扫描时同时统计两种代价：把 top 统一为 x 需要多少次翻转、把 bottom 统一为 x 需要多少次翻转，取较小值即可。

算法步骤

- 候选值只需要尝试 tops[0] 与 bottoms[0]。
- 遍历每个位置 i：
  • 若 tops[i] 与 bottoms[i] 都不等于候选值，直接失败。
  • 若 tops[i] != x，说明要把 top 统一成 x 时该位置要翻转。
  • 若 bottoms[i] != x，说明要把 bottom 统一成 x 时该位置要翻转。
- 候选成功时答案为两者较小值。
- 两个候选都失败则返回 -1。

复杂度分析

时间复杂度：O(n)（最多两次线性扫描）。
空间复杂度：O(1)。

常见陷阱

- 没利用“候选只可能是首张骨牌的两个值”这一关键性质。
- 只统计了统一 top，忘了统一 bottom 的代价。
- 遇到某张骨牌两面都不是候选值时没有及时判失败。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int ans = check(tops, bottoms, tops[0]);
        if (ans != -1) return ans;
        return check(tops, bottoms, bottoms[0]);
    }

    private int check(int[] tops, int[] bottoms, int x) {
        int rotateTop = 0;
        int rotateBottom = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            if (tops[i] != x) rotateTop++;
            if (bottoms[i] != x) rotateBottom++;
        }
        return Math.min(rotateTop, rotateBottom);
    }
}

func minDominoRotations(tops []int, bottoms []int) int {
    if ans := check(tops, bottoms, tops[0]); ans != -1 {
        return ans
    }
    return check(tops, bottoms, bottoms[0])
}

func check(tops []int, bottoms []int, x int) int {
    rotateTop, rotateBottom := 0, 0
    for i := 0; i < len(tops); i++ {
        if tops[i] != x && bottoms[i] != x {
            return -1
        }
        if tops[i] != x {
            rotateTop++
        }
        if bottoms[i] != x {
            rotateBottom++
        }
    }
    if rotateTop < rotateBottom {
        return rotateTop
    }
    return rotateBottom
}

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int ans = check(tops, bottoms, tops[0]);
        if (ans != -1) return ans;
        return check(tops, bottoms, bottoms[0]);
    }

private:
    int check(vector<int>& tops, vector<int>& bottoms, int x) {
        int rotateTop = 0, rotateBottom = 0;
        for (int i = 0; i < (int)tops.size(); ++i) {
            if (tops[i] != x && bottoms[i] != x) return -1;
            if (tops[i] != x) ++rotateTop;
            if (bottoms[i] != x) ++rotateBottom;
        }
        return min(rotateTop, rotateBottom);
    }
};

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        ans = self.check(tops, bottoms, tops[0])
        if ans != -1:
            return ans
        return self.check(tops, bottoms, bottoms[0])

    def check(self, tops: List[int], bottoms: List[int], x: int) -> int:
        rotate_top = 0
        rotate_bottom = 0

        for t, b in zip(tops, bottoms):
            if t != x and b != x:
                return -1
            if t != x:
                rotate_top += 1
            if b != x:
                rotate_bottom += 1

        return min(rotate_top, rotate_bottom)

var minDominoRotations = function(tops, bottoms) {
  let ans = check(tops, bottoms, tops[0]);
  if (ans !== -1) return ans;
  return check(tops, bottoms, bottoms[0]);
};

function check(tops, bottoms, x) {
  let rotateTop = 0;
  let rotateBottom = 0;

  for (let i = 0; i < tops.length; i++) {
    if (tops[i] !== x && bottoms[i] !== x) return -1;
    if (tops[i] !== x) rotateTop++;
    if (bottoms[i] !== x) rotateBottom++;
  }

  return Math.min(rotateTop, rotateBottom);
}