We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Domino Rotations For Equal Row

Difficulty: Medium

Problem Description

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the i-th domino. We may rotate the i-th 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.

Key Insights

  • The goal is to make all values in either the tops or bottoms the same.
  • A valid target number must appear in either the tops or bottoms array frequently enough to allow for rotations.
  • We need to check for both potential target values (the first element of tops and bottoms) and calculate the number of rotations required for each.

Space and Time Complexity

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

Solution

To solve this problem, we can use a greedy approach. We can check for the two possible target values: the first element of the tops array and the first element of the bottoms array. For each target value, we will count how many rotations are needed to make all elements in one of the rows equal to that target value. If neither target value can create a uniform row, we return -1.

  1. Iterate through the tops and bottoms arrays.
  2. Count how many times the target appears and how many rotations are needed to achieve that.
  3. Return the minimum rotations needed for either target; if neither is valid, return -1.

Code Solutions

def minDominoRotations(tops, bottoms):
    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')  # Impossible to make x the same
            elif tops[i] != x:
                rotations_top += 1
            elif bottoms[i] != x:
                rotations_bottom += 1
        return min(rotations_top, rotations_bottom)

    result = check(tops[0])
    if result == float('inf'):
        result = check(bottoms[0])
    
    return result if result != float('inf') else -1
← Back to All Questions