Simulate the whole process

Most problems can be solved if we can find a smart way to simulate the whole process.

Minimum Domino Rotations For Equal Row - LeetCode

A naive way is to try all kinds of possible values and swap to see whether it works.

Since 1≤A[i]≤6, we will have the complexity of O(6A+6B)=O(12N)=O(N)

class Solution:
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def helper(A, B):
            min_, max_ = min(A), max(A)
            res = float('inf')
            for v in range(min_, max_+1):
                this_res = 0
                for i, a in enumerate(A):
                    if a!=v:
                        if B[i]!=v:
                            this_res=float('inf')
                            break
                        else:
                            this_res+=1
                if this_res!=float('inf'):
                    res=min(res, this_res, len(A)-this_res)
            return res
        fin_res = min(helper(A, B), helper(B, A))
        return fin_res if fin_res!=float('inf') else -1

Actually, we can further improve the code as if we want to make A totally same, it can only have two possibilities A[0] or B[0]. It is same to B.

We can reduce the possibilities from 6 to 2. Hence, a little bit faster.

class Solution:
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def helper(A, B, values):
            res = float('inf')
            for v in values:
                this_res = 0
                for i, a in enumerate(A):
                    if a!=v:
                        if B[i]!=v:
                            this_res=float('inf')
                            break
                        else:
                            this_res+=1
                if this_res!=float('inf'):
                    res=min(res, this_res, len(A)-this_res)
            return res
        values = {A[0], B[0]}
        fin_res = min(helper(A, B, values ), helper(B, A, values))
        return fin_res if fin_res!=float('inf') else -1

[Java/C++/Python] Different Ideas - LeetCode Discuss

import functools 
class Solution:
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        s = functools.reduce(set.__and__, (set(c) for c in zip(A,B)))
        if not s:return -1
        x = s.pop()
        return min(len(A)-A.count(x), len(A)-B.count(x))