{x}
blog image

Minimum Domino Rotations For Equal Row

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

 

Example 1:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

 

Constraints:

  • 2 <= tops.length <= 2 * 104
  • bottoms.length == tops.length
  • 1 <= tops[i], bottoms[i] <= 6

Solution Explanation: Minimum Domino Rotations For Equal Row

This problem asks for the minimum number of rotations needed to make either the top row or the bottom row of dominoes have all the same value.

Approach:

The core idea is to leverage a greedy approach. We observe that if it's possible to make all elements in either row the same, that value must be either tops[0] or bottoms[0]. This is because any other value would require changing at least one element from the first domino.

We define a helper function f(x) which calculates the minimum rotations needed to make all elements equal to x. This is done by iterating through the dominoes. For each domino:

  1. Check Feasibility: If neither the top (tops[i]) nor the bottom (bottoms[i]) is equal to x, it's impossible to achieve the goal with x, so we return a large value (n+1 where n is the length of the arrays to signal impossibility).

  2. Count Rotations: Otherwise, we increment cnt1 if tops[i] == x, and cnt2 if bottoms[i] == x. This counts how many dominoes already have x on top and bottom respectively.

After iterating, n - max(cnt1, cnt2) represents the minimum rotations. We take the maximum because we prioritize rotating the domino to have x on top if there are more x values already on top.

Finally, we return the minimum of f(tops[0]) and f(bottoms[0]), or -1 if both return n+1 (meaning neither tops[0] nor bottoms[0] works).

Time Complexity: O(n), where n is the length of the tops and bottoms arrays. We iterate through the arrays a constant number of times.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python):

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def f(x: int) -> int:
            cnt1 = cnt2 = 0
            for a, b in zip(tops, bottoms):
                if x not in (a, b):
                    return float('inf')  # Indicate impossibility
                cnt1 += a == x
                cnt2 += b == x
            return len(tops) - max(cnt1, cnt2)
 
        ans = min(f(tops[0]), f(bottoms[0]))
        return -1 if ans == float('inf') else ans

Other Languages (brief overview):

The implementations in Java, C++, Go, and TypeScript follow the same logic. They differ primarily in syntax and how they handle infinity (e.g., using Integer.MAX_VALUE in Java, n + 1 in C++ and Go, or a large number in TypeScript). The core algorithmic steps remain identical.