[Leetcode] 1007. Minimum Domino Rotations For Equal Row

https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/?envType=daily-question&envId=2025-05-03

initial

So I was so close but i was thinking to sort the number based on the frequency of the top and btootm list and iterating from the highest freq. But there is no mechanism and guarantee that we have t (wait actually i think it might work)

but anyway we dont have to sort on freq cuz number is guaranteed from 1 ~ 6. So for that range, we fill the count freq list for top and bot. Also if same number exists for both index, we increment the common freq list. If top and bot count - common count ==n, then we can return n - max(top,bot count).

class Solution:
    def minDominoRotations(self, tops: List[int], bot: List[int]) -> int:
        countBot=[0 for _ in range(7)]
        countTop=[0 for _ in range(7)]
        countSame=[0 for _ in range(7)]
        for i in range(1,7):
            for hola in range(len(tops)):
                if tops[hola]==i:
                    countTop[i]+=1
                if bot[hola]==i:
                    countBot[i]+=1
                if tops[hola]==i and bot[hola]==i:
                    countSame[i]+=1
        for i in range(1,7):
            if countTop[i]+countBot[i]-countSame[i]==len(tops):
                return len(tops)-max(countTop[i],countBot[i])
        return -1

sol

But we can optimise this. The hypthoesis we are putting is that we can form a valid working sol (i.e. there is indeed a number that we can form a valid uniform row). That value must also exist in the first index of our top and bot lists. Cuz if there isnt, then its an invalid case so we return -1

Using that hypothesis we dont have to check for range 1 to 6 but just check the first 2 numbers of our top and bot list

class Solution:
    def minDominoRotations(self, tops: List[int], bot: List[int]) -> int:
        n = len(tops)

        def check(target):
            rotations_top = 0
            rotations_bottom = 0
            for i in range(n):
                if tops[i] != target and bot[i] != target:
                    return float('inf')  # Impossible

                elif tops[i] != target:
                    rotations_top += 1
                elif bot[i] != target:
                    rotations_bottom += 1
            return min(rotations_top, rotations_bottom)

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

complexity

n time
1 space for both