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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Domino Rotations For Equal Row

Number: 1049

Difficulty: Medium

Paid? No

Companies: Microsoft, Google

Problem Description

Given two arrays, tops and bottoms, where each index represents a domino with a top and bottom number, determine the minimum number of rotations needed to make all the values in either the tops or bottoms array equal. A rotation swaps the numbers on the domino at that index. If it isn't possible to make one row consist of all the same number, return -1.

Key Insights

  • Only values present in the first domino (tops[0] and bottoms[0]) can potentially become the uniform value for the row.
  • Check both candidate numbers independently.
  • For each candidate, count the required rotations to make either the top row or bottom row uniform.
  • If a domino does not have the candidate number on either side, then that candidate fails.
  • The solution requires a single pass through the arrays, providing O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the list of dominoes just once for each candidate. Space Complexity: O(1) - The algorithm uses a constant amount of additional space.

Solution

The algorithm checks both candidates (from tops[0] and bottoms[0]). For each candidate, it iterates through all dominoes, counting:

  • The number of rotations needed to make the tops all equal to the candidate (count rotations when the top element is not the candidate).
  • The number of rotations needed to make the bottoms all equal to the candidate (count rotations when the bottom element is not the candidate). If a domino has neither top nor bottom equal to the candidate, then it's impossible to use that candidate and we break early. After evaluating both candidates, we choose the candidate (if any) with the minimum number of rotations.

Code Solutions

# Python solution for Minimum Domino Rotations For Equal Row

def minDominoRotations(tops, bottoms):
    def check(target):
        rotations_top = rotations_bottom = 0
        for i in range(len(tops)):
            # If neither side has the candidate, it's impossible
            if tops[i] != target and bottoms[i] != target:
                return float('inf')
            # Count a rotation if the top value is not candidate
            elif tops[i] != target:
                rotations_top += 1
            # Count a rotation if the bottom value is not candidate
            elif bottoms[i] != target:
                rotations_bottom += 1
        return min(rotations_top, rotations_bottom)
    
    # The candidate numbers are the first domino's top and bottom elements
    candidate1 = tops[0]
    candidate2 = bottoms[0]
    
    # Check rotations for candidate1
    result = check(candidate1)
    if candidate1 != candidate2:
        # If two candidates are different, check candidate2 as well
        result = min(result, check(candidate2))
    
    return result if result != float('inf') else -1

# Example usage:
tops = [2,1,2,4,2,2]
bottoms = [5,2,6,2,3,2]
print(minDominoRotations(tops, bottoms))  # Output: 2
← Back to All Questions