Minimum Domino Rotations For Equal Row [Medium] — Greedy Check

Problem Statement

Two arrays tops and bottoms represent domino faces. With rotations (swap top/bottom of a domino), find minimum rotations to make all tops OR all bottoms equal. Return -1 if impossible.

Input: tops=[2,1,2,4,2,2], bottoms=[5,2,6,2,3,2] → Output: 2

Intuition

The target value must be tops[0] or bottoms[0] (only they can be the universal value). For each candidate, count minimum rotations needed.

Solutions

Python

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

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

C++

int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
    auto check=[&](int val){
        int rt=0,rb=0;
        for(int i=0;i<tops.size();i++){
            if(tops[i]!=val&&bottoms[i]!=val) return INT_MAX;
            else if(tops[i]!=val) rt++;
            else if(bottoms[i]!=val) rb++;
        }
        return min(rt,rb);
    };
    int ans=min(check(tops[0]),check(bottoms[0]));
    return ans==INT_MAX?-1:ans;
}

Complexity

Time: O(n)
Space: O(1)