Jobs

Interviews

Discussions

Minimum Domino Rotations For Equal Row

#492 Most AskedMedium

Minimum Domino Rotations For Equal Row #492 Most Asked

Medium

Microsoft

17 views

Topics:

Arrays

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

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.

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 * 10⁴
bottoms.length == tops.length
1 <= tops[i], bottoms[i] <= 6

Try coding it in LeetCode

Minimum Domino Rotations For Equal Row

#492 Most AskedMedium

Minimum Domino Rotations For Equal Row #492 Most Asked

Medium

Microsoft

17 views

Topics:

Arrays

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

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.

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 * 10⁴
bottoms.length == tops.length
1 <= tops[i], bottoms[i] <= 6

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the dominoes arrays A and B? Can they be negative or zero?
If it's impossible to make all values in either row equal, what should I return?
Can the input arrays A and B be empty or null? If so, what should I return?
Are the lengths of arrays A and B guaranteed to be the same?
If multiple domino values could lead to a minimum number of rotations, is any of those minimums acceptable?

Brute Force Solution

Approach

The brute force way to solve this domino problem is to check every possible value from 1 to 6 and see if we can make either the top or bottom row have all the same value. We'll count how many flips it takes for each possibility and pick the smallest one.

Here's how the algorithm would work step-by-step:

First, pick a target number between 1 and 6 (inclusive). This is the number we want to make all the domino faces match.
Next, try to make the top row have all of the target number. Go through the dominoes one by one.
If the top face of a domino doesn't match the target number, check if the bottom face does.
If the bottom face does match, we need to 'flip' the domino so the target number is on top. Count this flip.
If neither the top nor the bottom face matches the target number, it's impossible to make the top row all the target number. Stop and mark this attempt as a failure.
If we make it through all the dominoes, count the total number of flips we did.
Now, repeat the process, but this time try to make the bottom row have all the target numbers. Count the flips needed, just like before.
Do steps 2 through 7 for each number from 1 to 6.
Finally, after checking all numbers for both the top and bottom rows, pick the solution that required the fewest flips. If we never found a solution, it's impossible to make either row the same, so we'll say it can't be done.

Code Implementation

def minimum_domino_rotations(tops, bottoms):    number_of_dominoes = len(tops)
    minimum_rotations = float('inf')

    for target_number in range(1, 7):
        # Attempt to make the top row all the target number
        rotations_to_top = 0
        possible = True
        for index in range(number_of_dominoes):
            if tops[index] != target_number:
                if bottoms[index] == target_number:
                    rotations_to_top += 1
                else:
                    possible = False
                    break

        # Update minimum rotations if a solution was found
        if possible:
            minimum_rotations = min(minimum_rotations, rotations_to_top)

        # Attempt to make the bottom row all the target number
        rotations_to_bottom = 0
        possible = True
        for index in range(number_of_dominoes):
            if bottoms[index] != target_number:
                if tops[index] == target_number:
                    rotations_to_bottom += 1
                else:
                    possible = False
                    break

        # Update minimum rotations if a solution was found
        if possible:
            minimum_rotations = min(minimum_rotations, rotations_to_bottom)

    # If no solution was found, return -1
    if minimum_rotations == float('inf'):
        return -1
    else:
        return minimum_rotations

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through potential target values (1 to 6), which is a constant time operation. For each target value, it iterates through the n dominoes in array A and then the n dominoes in array B to count the minimum number of swaps to make the rows homogenous with the target value. Thus, each target value results in O(n) operations and since there are a constant number of target values to try, the total complexity remains O(n).

Space Complexity

O(1) – The provided algorithm iterates through potential target values (1 to 6) and counts flips. It primarily uses a few integer variables to store the target number, flip counts for top and bottom rows, and a flag to indicate if a solution is impossible. The number of variables used does not depend on the size of the input arrays A and B (number of dominoes). Therefore, the auxiliary space used remains constant regardless of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

The fastest way to solve this is to realize we only care if one of the numbers from the first domino can potentially make an entire row the same. We count how many rotations it takes to make either of those numbers fill a row, and the smaller rotation count is the answer.

Here's how the algorithm would work step-by-step:

Look at the numbers on the first domino.
For the first number, count how many dominoes need to be rotated to make the top row all that number.
If it's impossible to make the top row all that number, mark it as impossible.
For the first number, count how many dominoes need to be rotated to make the bottom row all that number.
If it's impossible to make the bottom row all that number, mark it as impossible.
Repeat the counting process for the second number on the first domino, checking rotations for both the top and bottom rows.
Compare the four rotation counts (top/bottom for each number). The smallest non-impossible count is the answer.

Code Implementation

def minDominoRotations(tops, bottoms): 
    first_domino_top_value = tops[0]
    first_domino_bottom_value = bottoms[0]
    number_of_dominoes = len(tops)

    def calculate_rotations(target_value, target_row):
        rotations_needed = 0
        for i in range(number_of_dominoes):
            if target_row == 'tops':
                if tops[i] != target_value:
                    if bottoms[i] == target_value:
                        rotations_needed += 1
                    else:
                        return float('inf')
            else:
                if bottoms[i] != target_value:
                    if tops[i] == target_value:
                        rotations_needed += 1
                    else:
                        return float('inf')
        return rotations_needed

    #Calculate rotations needed for the top row to match first domino top value
    top_rotations_for_first_top = calculate_rotations(first_domino_top_value, 'tops')

    #Calculate rotations needed for the bottom row to match first domino top value
    bottom_rotations_for_first_top = calculate_rotations(first_domino_top_value, 'bottoms')

    #Calculate rotations needed for the top row to match first domino bottom value
    top_rotations_for_first_bottom = calculate_rotations(first_domino_bottom_value, 'tops')

    #Calculate rotations needed for the bottom row to match first domino bottom value
    bottom_rotations_for_first_bottom = calculate_rotations(first_domino_bottom_value, 'bottoms')

    minimum_rotations = min(top_rotations_for_first_top, 
                            bottom_rotations_for_first_top, 
                            top_rotations_for_first_bottom, 
                            bottom_rotations_for_first_bottom)

    # If it's impossible return -1
    if minimum_rotations == float('inf'):
        return -1

    return minimum_rotations

Big(O) Analysis

Time Complexity

O(n) – The algorithm examines the first domino and then iterates through the dominoes array up to four times (twice for each value on the first domino), each time counting rotations needed to make either the top or bottom row uniform. Each of these iterations involves traversing the entire dominoes array once, which takes O(n) time. Since there are a fixed number of traversals (at most four), the overall time complexity is O(n).

Space Complexity

O(1) – The described algorithm primarily uses a few counter variables to keep track of rotation counts for each number and row. These counters store a single integer value regardless of the number of dominoes (N). Therefore, the auxiliary space used is constant, independent of the input size N, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty input arrays A or B	Return -1 immediately since no rotations are possible.
Arrays A and B have different lengths	Return -1 since a common row cannot be achieved.
Arrays A and B have a single element	Return 0 if the single elements are equal, and -1 otherwise.
All elements in both A and B are the same	Return 0 since no rotations are needed.
No number appears in all of A or all of B	Return -1, indicating no solution is possible.
Arrays A and B are identical, but no number is the same throughout	This should correctly result in -1 being returned.
Arrays A and B have very large size (performance consideration)	Ensure the algorithm iterates the array only a constant number of times (O(n) time complexity).
Integer overflow if counting rotations with very large array sizes	The number of rotations will never exceed the array size; thus, integer overflow is not a concern.

Empty input arrays A or B

How to Handle:

Return -1 immediately since no rotations are possible.

Arrays A and B have different lengths

How to Handle:

Return -1 since a common row cannot be achieved.

Arrays A and B have a single element

How to Handle:

Return 0 if the single elements are equal, and -1 otherwise.

All elements in both A and B are the same

How to Handle:

Return 0 since no rotations are needed.

No number appears in all of A or all of B

How to Handle:

Return -1, indicating no solution is possible.

Arrays A and B are identical, but no number is the same throughout

How to Handle:

This should correctly result in -1 being returned.

Arrays A and B have very large size (performance consideration)

How to Handle:

Ensure the algorithm iterates the array only a constant number of times (O(n) time complexity).

Integer overflow if counting rotations with very large array sizes

How to Handle:

The number of rotations will never exceed the array size; thus, integer overflow is not a concern.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the dominoes arrays A and B? Can they be negative or zero?
If it's impossible to make all values in either row equal, what should I return?
Can the input arrays A and B be empty or null? If so, what should I return?
Are the lengths of arrays A and B guaranteed to be the same?
If multiple domino values could lead to a minimum number of rotations, is any of those minimums acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pick a target number between 1 and 6 (inclusive). This is the number we want to make all the domino faces match.
Next, try to make the top row have all of the target number. Go through the dominoes one by one.
If the top face of a domino doesn't match the target number, check if the bottom face does.
If the bottom face does match, we need to 'flip' the domino so the target number is on top. Count this flip.
If neither the top nor the bottom face matches the target number, it's impossible to make the top row all the target number. Stop and mark this attempt as a failure.
If we make it through all the dominoes, count the total number of flips we did.
Now, repeat the process, but this time try to make the bottom row have all the target numbers. Count the flips needed, just like before.
Do steps 2 through 7 for each number from 1 to 6.
Finally, after checking all numbers for both the top and bottom rows, pick the solution that required the fewest flips. If we never found a solution, it's impossible to make either row the same, so we'll say it can't be done.

Code Implementation

def minimum_domino_rotations(tops, bottoms):    number_of_dominoes = len(tops)
    minimum_rotations = float('inf')

    for target_number in range(1, 7):
        # Attempt to make the top row all the target number
        rotations_to_top = 0
        possible = True
        for index in range(number_of_dominoes):
            if tops[index] != target_number:
                if bottoms[index] == target_number:
                    rotations_to_top += 1
                else:
                    possible = False
                    break

        # Update minimum rotations if a solution was found
        if possible:
            minimum_rotations = min(minimum_rotations, rotations_to_top)

        # Attempt to make the bottom row all the target number
        rotations_to_bottom = 0
        possible = True
        for index in range(number_of_dominoes):
            if bottoms[index] != target_number:
                if tops[index] == target_number:
                    rotations_to_bottom += 1
                else:
                    possible = False
                    break

        # Update minimum rotations if a solution was found
        if possible:
            minimum_rotations = min(minimum_rotations, rotations_to_bottom)

    # If no solution was found, return -1
    if minimum_rotations == float('inf'):
        return -1
    else:
        return minimum_rotations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the numbers on the first domino.
For the first number, count how many dominoes need to be rotated to make the top row all that number.
If it's impossible to make the top row all that number, mark it as impossible.
For the first number, count how many dominoes need to be rotated to make the bottom row all that number.
If it's impossible to make the bottom row all that number, mark it as impossible.
Repeat the counting process for the second number on the first domino, checking rotations for both the top and bottom rows.
Compare the four rotation counts (top/bottom for each number). The smallest non-impossible count is the answer.

Code Implementation

def minDominoRotations(tops, bottoms): 
    first_domino_top_value = tops[0]
    first_domino_bottom_value = bottoms[0]
    number_of_dominoes = len(tops)

    def calculate_rotations(target_value, target_row):
        rotations_needed = 0
        for i in range(number_of_dominoes):
            if target_row == 'tops':
                if tops[i] != target_value:
                    if bottoms[i] == target_value:
                        rotations_needed += 1
                    else:
                        return float('inf')
            else:
                if bottoms[i] != target_value:
                    if tops[i] == target_value:
                        rotations_needed += 1
                    else:
                        return float('inf')
        return rotations_needed

    #Calculate rotations needed for the top row to match first domino top value
    top_rotations_for_first_top = calculate_rotations(first_domino_top_value, 'tops')

    #Calculate rotations needed for the bottom row to match first domino top value
    bottom_rotations_for_first_top = calculate_rotations(first_domino_top_value, 'bottoms')

    #Calculate rotations needed for the top row to match first domino bottom value
    top_rotations_for_first_bottom = calculate_rotations(first_domino_bottom_value, 'tops')

    #Calculate rotations needed for the bottom row to match first domino bottom value
    bottom_rotations_for_first_bottom = calculate_rotations(first_domino_bottom_value, 'bottoms')

    minimum_rotations = min(top_rotations_for_first_top, 
                            bottom_rotations_for_first_top, 
                            top_rotations_for_first_bottom, 
                            bottom_rotations_for_first_bottom)

    # If it's impossible return -1
    if minimum_rotations == float('inf'):
        return -1

    return minimum_rotations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input arrays A or B	Return -1 immediately since no rotations are possible.
Arrays A and B have different lengths	Return -1 since a common row cannot be achieved.
Arrays A and B have a single element	Return 0 if the single elements are equal, and -1 otherwise.
All elements in both A and B are the same	Return 0 since no rotations are needed.
No number appears in all of A or all of B	Return -1, indicating no solution is possible.
Arrays A and B are identical, but no number is the same throughout	This should correctly result in -1 being returned.
Arrays A and B have very large size (performance consideration)	Ensure the algorithm iterates the array only a constant number of times (O(n) time complexity).
Integer overflow if counting rotations with very large array sizes	The number of rotations will never exceed the array size; thus, integer overflow is not a concern.

Empty input arrays A or B

How to Handle:

Return -1 immediately since no rotations are possible.

Arrays A and B have different lengths

How to Handle:

Return -1 since a common row cannot be achieved.

Arrays A and B have a single element

How to Handle:

Return 0 if the single elements are equal, and -1 otherwise.

All elements in both A and B are the same

How to Handle:

Return 0 since no rotations are needed.

No number appears in all of A or all of B

How to Handle:

Return -1, indicating no solution is possible.

Arrays A and B are identical, but no number is the same throughout

How to Handle:

This should correctly result in -1 being returned.

Arrays A and B have very large size (performance consideration)

How to Handle:

Ensure the algorithm iterates the array only a constant number of times (O(n) time complexity).

Integer overflow if counting rotations with very large array sizes

How to Handle:

The number of rotations will never exceed the array size; thus, integer overflow is not a concern.

0/1114 Microsoft questions completed

0/1114 completed