Problem Description

You have a row of dominoes where each domino has a top number and a bottom number (both ranging from 1 to 6). The dominoes are represented by two arrays: tops[i] represents the top number of the i-th domino, and bottoms[i] represents the bottom number of the i-th domino.

You can rotate any domino, which means swapping its top and bottom values. For example, if a domino has 2 on top and 5 on bottom, after rotating it will have 5 on top and 2 on bottom.

Your goal is to find the minimum number of rotations needed to make either:

• All values in the tops array the same, OR
• All values in the bottoms array the same

If it's impossible to achieve either condition, return -1.

For example, if you have dominoes with tops = [2,1,2,4,2,2] and bottoms = [5,2,6,2,3,2], you could rotate some dominoes to make all top values equal to 2 or all bottom values equal to 2.

The key insight is that if a solution exists, the target value must appear in every domino (either on top or bottom). This means the target value must be either tops[0] or bottoms[0], since these are the only values guaranteed to be present in at least the first domino.

Intuition

Let's think about what value could possibly be the target that appears on all tops or all bottoms after rotations.

For any value to appear on all positions (either all tops or all bottoms), that value must be present in every single domino - either on its top face or bottom face. If even one domino doesn't have the target value on either face, it's impossible to make that value appear in the required position through rotation.

This leads us to a crucial observation: the target value must appear in the first domino. Why? Because if the target value doesn't appear in the first domino (neither on top nor bottom), then we can never place that value in the first position, making it impossible to have all positions with the same value.

Since the first domino only has two values - tops[0] and bottoms[0] - these are the only two possible candidates for our target value. Any other value from 1 to 6 that doesn't appear in the first domino cannot be our answer.

Once we identify that only tops[0] and bottoms[0] are viable candidates, we need to check each one:

1. For each candidate value x, verify if it appears in every domino (either top or bottom)
2. If it does appear in every domino, count how many dominoes already have x on top and how many have x on bottom
3. To minimize rotations, we choose to make all values equal to x in the position (top or bottom) where x appears more frequently
4. The number of rotations needed would be n - max(count_in_tops, count_in_bottoms)

If neither tops[0] nor bottoms[0] can be placed in all positions, the task is impossible and we return -1.

Learn more about Greedy patterns.

Solution Approach

The solution implements a greedy approach using a helper function f(x) that calculates the minimum rotations needed to make all values equal to x.

Helper Function f(x):

The function takes a target value x and determines how many rotations are needed to make either all tops or all bottoms equal to x.

1. Initialize two counters: cnt1 and cnt2 to track occurrences of x in tops and bottoms respectively

2. Iterate through each domino pair (a, b) where a = tops[i] and b = bottoms[i]

3. For each domino:

   • If x is not present in either a or b, return infinity (inf) since it's impossible to place x in this position
   • If a == x, increment cnt1 (counting how many dominoes already have x on top)
   • If b == x, increment cnt2 (counting how many dominoes already have x on bottom)

4. After checking all dominoes, calculate the minimum rotations:

   • We can either make all tops equal to x or all bottoms equal to x
   • If we want all tops to be x, we need n - cnt1 rotations (rotate dominoes that don't have x on top)
   • If we want all bottoms to be x, we need n - cnt2 rotations (rotate dominoes that don't have x on bottom)
   • Return len(tops) - max(cnt1, cnt2) to get the minimum rotations needed

Main Algorithm:

1. Call f(tops[0]) to check if we can make all values equal to tops[0]
2. Call f(bottoms[0]) to check if we can make all values equal to bottoms[0]
3. Take the minimum of these two results: ans = min(f(tops[0]), f(bottoms[0]))
4. If ans == inf, it means neither value can be placed in all positions, so return -1
5. Otherwise, return ans as the minimum number of rotations

The time complexity is O(n) where n is the number of dominoes, as we iterate through the array at most twice (once for each candidate value). The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example with tops = [2,1,2,4] and bottoms = [5,2,6,2].

Step 1: Identify candidates The only possible target values are from the first domino:

• tops[0] = 2
• bottoms[0] = 5

Step 2: Check if we can make all values equal to 2

Call f(2):

• Domino 0: (top=2, bottom=5) → 2 is present (on top), cnt1=1, cnt2=0
• Domino 1: (top=1, bottom=2) → 2 is present (on bottom), cnt1=1, cnt2=1
• Domino 2: (top=2, bottom=6) → 2 is present (on top), cnt1=2, cnt2=1
• Domino 3: (top=4, bottom=2) → 2 is present (on bottom), cnt1=2, cnt2=2

All dominoes contain 2, so it's possible!

• To make all tops = 2: need 4 - 2 = 2 rotations (rotate dominoes 1 and 3)
• To make all bottoms = 2: need 4 - 2 = 2 rotations (rotate dominoes 0 and 2)
• Minimum rotations for value 2: 4 - max(2,2) = 2

Step 3: Check if we can make all values equal to 5

Call f(5):

• Domino 0: (top=2, bottom=5) → 5 is present (on bottom), cnt1=0, cnt2=1
• Domino 1: (top=1, bottom=2) → 5 is NOT present → return inf

Since 5 doesn't appear in domino 1, it's impossible to make all values equal to 5.

Step 4: Calculate final answer

• ans = min(f(2), f(5)) = min(2, inf) = 2
• Since ans ≠ inf, return 2

The minimum number of rotations needed is 2. We can either:

• Rotate dominoes 1 and 3 to make all tops = 2: [2,2,2,2]
• Or rotate dominoes 0 and 2 to make all bottoms = 2: [2,2,2,2]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the arrays tops and bottoms.

The algorithm calls the helper function f(x) at most twice - once with tops[0] and once with bottoms[0]. Each call to f(x) iterates through all elements using zip(tops, bottoms), which takes O(n) time. Within each iteration, the operations (checking if x is in (a, b), incrementing counters, and comparisons) all take O(1) time. Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The helper function f(x) uses two counter variables (cnt1 and cnt2), and the main function uses one variable ans to store the result. The zip function creates an iterator that doesn't store all pairs in memory at once. All these variables occupy constant space regardless of the input size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Double Counting When Both Values Are the Same

The Problem: When a domino has the same value on both top and bottom (e.g., tops[i] = bottoms[i] = 3), the current counting logic increments both top_count and bottom_count. This leads to incorrect calculation of minimum rotations.

Example:

tops = [3, 5, 3]
bottoms = [3, 3, 5]

For target value 3:

• Position 0: Both are 3, so top_count = 1, bottom_count = 1
• Position 1: Only bottom is 3, so top_count = 1, bottom_count = 2
• Position 2: Only top is 3, so top_count = 2, bottom_count = 2

The function returns 3 - max(2, 2) = 1, but actually no rotations are needed since we can already have all bottoms as 3.

The Solution: When counting, we should handle the case where both values are the same specially:

def calculate_min_rotations(target_value: int) -> int:
    top_count = 0
    bottom_count = 0
  
    for top_val, bottom_val in zip(tops, bottoms):
        if target_value not in (top_val, bottom_val):
            return float('inf')
      
        # Handle the case where both values are the same
        if top_val == bottom_val == target_value:
            # This domino contributes to both rows without rotation
            continue
        elif top_val == target_value:
            top_count += 1
        elif bottom_val == target_value:
            bottom_count += 1
  
    # Calculate rotations needed for each scenario
    n = len(tops)
    # To make all tops equal to target_value
    rotations_for_tops = bottom_count
    # To make all bottoms equal to target_value
    rotations_for_bottoms = top_count
  
    return min(rotations_for_tops, rotations_for_bottoms)

Pitfall 2: Not Understanding the Rotation Logic

The Problem: The formula len(tops) - max(top_count, bottom_count) can be confusing and may lead to misunderstanding of what rotation actually means.

Clearer Alternative: Instead of thinking about maximizing counts, think directly about the rotations needed:

def calculate_min_rotations(target_value: int) -> int:
    rotations_to_top = 0    # Rotations to make all tops = target_value
    rotations_to_bottom = 0 # Rotations to make all bottoms = target_value
  
    for top_val, bottom_val in zip(tops, bottoms):
        if target_value not in (top_val, bottom_val):
            return float('inf')
      
        # Count rotations needed for each strategy
        if top_val != target_value:
            rotations_to_top += 1  # Need to rotate this domino to get target on top
        if bottom_val != target_value:
            rotations_to_bottom += 1  # Need to rotate this domino to get target on bottom
  
    return min(rotations_to_top, rotations_to_bottom)

This approach is more intuitive: directly count how many dominoes need rotation for each strategy, then return the minimum.