Minimum Domino Rotations For Equal Row

main.md

Question

Approach

When approaching this problem, I realized that only the first domino's top and bottom values could potentially be the unified value across the entire row. So I focused on checking if all dominoes can be rotated such that either tops or bottoms becomes full of just tops[0] or bottoms[0]. For each candidate, I counted how many rotations are needed to achieve this — both by rotating tops to match the candidate or bottoms to match the candidate. If either configuration works, I returned the minimum number of rotations. If not, I returned -1.

Implementation

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def check(x):
            rotations_top = rotations_bottom = 0
            for i in range(len(tops)):
                if tops[i] != x and bottoms[i] != x:
                    return float('inf')
                elif tops[i] != x:
                    rotations_top += 1
                elif bottoms[i] != x:
                    rotations_bottom += 1
            return min(rotations_top, rotations_bottom)

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

Complexities

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