1007. Minimum Domino Rotations For Equal Row


Problem Description

In this problem, we are given two arrays, tops and bottoms, each representing the top and bottom halves of a stack of domino tiles, where each tile may have numbers from 1 to 6. We have the option to rotate any number of dominos to make either all top or all bottom numbers the same. Our goal is to find the minimum number of rotations required to achieve this uniformity of numbers on either side. If it's impossible to reach a state where all numbers are the same on any one side, we must return -1.

Imagine a row of dominoes lined up on a table, where we can see the top and bottom numbers of each tile. We can flip any domino, swapping its top and bottom numbers, trying to get all the top numbers to match or all the bottom numbers to match. The challenge is to do this in the fewest flips possible or determine if it's not possible at all.

Intuition

To solve this problem efficiently, we employ a greedy strategy. The key insight is that if a uniform number can be achieved on either the top or bottom of the dominos, that number must be the same as either the top or bottom of the first domino. This is because if the first domino does not contain the number we want to match everywhere, we can never make that number appear on both the first top and bottom by any rotation.

With this in mind, we define a function, f(x), that calculates the minimum number of rotations required to make all the values in either tops or bottoms equal to the number x. We only need to consider two cases for x: the number on the top and the number on the bottom of the first domino.

The function f(x) works by counting how many times the number x appears on the top (cnt1) and how many times on the bottom (cnt2). If the number x is not present in either side of a domino, it means we cannot make all values equal to x with rotations alone, and we return infinity (inf) to indicate that it is impossible for x.

If the number x is present, we calculate the rotations as the total number of dominos minus the maximum appearance count (max(cnt1, cnt2)). This represents the side with fewer appearances of x, which would need to be flipped to make all the numbers match x. We take the minimum value from applying function f(x) to both tops[0] and bottoms[0] to find the overall minimum rotations needed.

This approach is greedy because it seeks a local optimization—focusing on aligning all numbers to match either tops[0] or bottoms[0], to give a global solution which is the minimum number of rotations required. If neither number can be aligned, the function recognizes this by returning infinity, and thus the overall solution returns -1.

Solution Approach

The solution implements a simple yet clever approach utilizing a helper function that encapsulates the core logic required to solve the problem.

Let's walk through the steps:

  1. We have a helper function f(x) which takes x as a parameter. This function is responsible for determining the minimum number of rotations needed to make all values in tops or all values in bottoms equal to x.

  2. Inside f(x), we initiate two counters, cnt1 and cnt2, which count the occurrences of x in tops and bottoms arrays respectively. These counters are important as they help to evaluate the current state with respect to our target value x.

  3. A loop runs over both tops and bottoms simultaneously using zip(tops, bottoms) which pairs the top and bottom values of each domino. For each pair (a, b):

    • If x is not found in either a or b, it implies that no rotations can make the ith domino's top or bottom value x. Hence, we return inf which denotes an impossible situation for x.

    • If x is found, we increment cnt1 if a (top value) equals x, and similarly, we increment cnt2 if b (bottom value) equals x.

  4. After iterating over all dominos, the minimum rotations needed is calculated by taking the length of the tops array (which is the total number of dominos) and subtracting the larger of cnt1 or cnt2. This is because to make all numbers equal to x, we simply need to rotate the dominos which currently do not have x on the desired side (tops or bottoms). The side with a larger count of x will need fewer rotations since more dominos are already showing x.

  5. Our main function minDominoRotations now calls f(x) for tops[0] and bottoms[0] and calculates the minimum between these two results. If we get inf, it means rotating won't help us achieve a uniform side, hence we return -1.

  6. Otherwise, we return the minimum of the two values which represents the minimum number of rotations required for making all tops or all bottoms values equal.

This solution uses the greedy algorithmic paradigm where we take the local optimum (minimum rotations for tops[0] or bottoms[0]) to reach a global solution. Essential to this approach are the conditional checks and value counts which allow us to decide quickly the feasibility and cost (number of rotations) for each potential solution.

Additionally, by using Python's zip function to iterate over tops and bottoms simultaneously and its expressive syntax, the implementation remains clean, intuitive, and efficient.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider small arrays for tops and bottoms for an illustrative example:

Suppose tops = [2, 1, 2, 4, 2] and bottoms = [5, 2, 2, 2, 2]. We want to make all numbers in either the top or bottom uniform with the minimum number of rotations.

  • Firstly, we choose x to be tops[0], which is 2.

  • Applying function f(x):

    • We initialize cnt1 and cnt2 both to zero, which will count the occurrences of 2 in tops and bottoms respectively.
    • As we iterate:
      • For the first domino, tops[0] is 2 so we increment cnt1 to 1.
      • For the second domino, bottoms[1] is 2, so we increment cnt2 to 1.
      • The third domino has 2 on both tops and bottoms, so we increment both cnt1 and cnt2.
      • The fourth domino does not have 2 on the top, but it is on the bottom, so we increment cnt2.
      • The fifth domino has 2 on the top, so we increment cnt1.
    • After completing the iteration, cnt1 is 4 (since tops has the number 2 in four positions) and cnt2 is 4 as well (as bottoms also has the number 2 in four positions).
    • The minimum number of rotations f(2) will be the total number of dominos (5) minus the maximum occurrences of 2 (4), which gives us 1. We can achieve this by flipping the fourth domino.
  • Secondly, we choose x to be bottoms[0], which is 5.

  • Applying function f(x) with 5:

    • We find that 5 does not appear in tops at all and only appears once in bottoms. This means we would have to flip every domino except the first one to get 5 on the top everywhere. This gives us a count of 4 flips.

When we compare the results, flipping to get all 2's requires only 1 rotation, while flipping to get all 5's requires 4 rotations. Therefore, the minimum number of rotations required is 1, and the target number is 2.

Hence, minDominoRotations would return 1, which indicates that we should flip the fourth domino for all dominos to show the number 2 on either tops or bottoms. Since both tops and bottoms have the number 2 on four out of five positions already, the target number 2 is the optimal choice for achieving uniformity with the minimum rotations possible.

Python Solution

1from typing import List
2
3class Solution:
4    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
5        # Helper function that tries to make all the dominoes show x on top.
6        # It returns the minimum rotations needed, or infinity if it's not possible.
7        def check_value(x: int) -> int:
8            rotations_top = rotations_bottom = 0
9          
10            # Compare each pair of top and bottom values.
11            for top_value, bottom_value in zip(tops, bottoms):
12                # If the value x is not in either the top or bottom, return infinity
13                # since it's impossible to make all dominoes show x.
14                if x not in (top_value, bottom_value):
15                    return float('inf')
16              
17                # Count how many times value x appears on the top and bottom.
18                rotations_top += top_value == x
19                rotations_bottom += bottom_value == x
20          
21            # Return the minimum rotations needed, which is the total number of dominoes
22            # minus the maximum appearance of the value x on either side.
23            return len(tops) - max(rotations_top, rotations_bottom)
24
25        # Try making all dominoes show the first value of tops or bottoms.
26        # The min function will choose the smallest result from the two calls,
27        # which represents the minimum rotations to achieve the goal.
28        min_rotations = min(check_value(tops[0]), check_value(bottoms[0]))
29      
30        # If min_rotations is infinity, it means it's not possible to make all
31        # dominoes show the same number. Otherwise, return the minimum rotations.
32        return -1 if min_rotations == float('inf') else min_rotations
33

Java Solution

1class Solution {
2    private int arrayLength;
3    private int[] tops;
4    private int[] bottoms;
5
6    /**
7     * Finds the minimum number of rotations to have all the values in either top or bottom equal.
8     *
9     * @param tops    - array representing the top values of each domino.
10     * @param bottoms - array representing the bottom values of each domino.
11     * @return minimum number of rotations, or -1 if it is not possible.
12     */
13    public int minDominoRotations(int[] tops, int[] bottoms) {
14        // Set the global variables for easy access in the helper function.
15        arrayLength = tops.length;
16        this.tops = tops;
17        this.bottoms = bottoms;
18
19        // Check for the possibility of all dominos having the first top value or the first bottom value.
20        int rotations = Math.min(findRotationsForValue(tops[0]), findRotationsForValue(bottoms[0]));
21
22        // If the number of rotations is greater than the array length, it means it's impossible to achieve the goal.
23        return rotations > arrayLength ? -1 : rotations;
24    }
25
26    /**
27     * Helper function to calculate the rotations needed to make all the values of tops or bottoms equal to x.
28     *
29     * @param value - the value to match across all tops or bottoms.
30     * @return number of rotations needed or a value greater than n if not possible.
31     */
32    private int findRotationsForValue(int value) {
33        int countTops = 0, countBottoms = 0;
34
35        // Traverse through all dominos.
36        for (int i = 0; i < arrayLength; ++i) {
37            // If the current domino does not have the desired value on either side, the configuration is not possible.
38            if (tops[i] != value && bottoms[i] != value) {
39                return arrayLength + 1;
40            }
41
42            // Increment count of occurrence of value in tops and bottoms.
43            if (tops[i] == value) {
44                countTops++;
45            }
46            if (bottoms[i] == value) {
47                countBottoms++;
48            }
49        }
50
51        // The minimum rotations is the length of the array minus
52        // the maximum count of the value in either tops or bottoms.
53        return arrayLength - Math.max(countTops, countBottoms);
54    }
55}
56

C++ Solution

1class Solution {
2public:
3    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
4        int size = tops.size();
5
6        // Helper function to calculate the minimum rotations needed to make all dominoes show number 'x' on top
7        // If it's not possible to make all the numbers 'x', the function returns more than 'size' which is an invalid number of rotations
8        auto countMinRotations = [&](int x) {
9            int topCount = 0, bottomCount = 0;
10            for (int i = 0; i < size; ++i) {
11                // If neither the top nor the bottom of the i-th domino is 'x', it's not possible to make all numbers 'x'
12                if (tops[i] != x && bottoms[i] != x) {
13                    return size + 1;
14                }
15                // Count how many tops are already 'x'
16                topCount += tops[i] == x;
17                // Count how many bottoms are already 'x'
18                bottomCount += bottoms[i] == x;
19            }
20            // You want to preserve the side which already has the most 'x's and rotate the other side
21            // Hence you need 'size' - max(topCount, bottomCount) rotations
22            return size - max(topCount, bottomCount);
23        };
24
25        // Compute the minimum rotations for the first number on the top and bottom to make the entire row uniform
26        int minRotations = min(countMinRotations(tops[0]), countMinRotations(bottoms[0]));
27
28        // If the computed rotations is greater than 'size', it's not possible to make the row uniform, returns -1
29        return minRotations > size ? -1 : minRotations;
30    }
31};
32

Typescript Solution

1function minDominoRotations(tops: number[], bottoms: number[]): number {
2    const length = tops.length;
3
4    // Function that tries to make all dominos to show number x on the top
5    const calculateRotationsForNumber = (targetNumber: number): number => {
6        let topCount = 0;      // Count of targetNumber in the 'tops' array
7        let bottomCount = 0;   // Count of targetNumber in the 'bottoms' array
8
9        // Iterate over the domino pieces
10        for (let i = 0; i < length; ++i) {
11            // If the current top and bottom do not contain the target number, return invalid result
12            if (tops[i] !== targetNumber && bottoms[i] !== targetNumber) {
13                return length + 1;
14            }
15            // Count occurrences of targetNumber in tops
16            if (tops[i] === targetNumber) {
17                topCount++;
18            }
19            // Count occurrences of targetNumber in bottoms
20            if (bottoms[i] === targetNumber) {
21                bottomCount++;
22            }
23        }
24        // Return minimum rotations needed by subtracting the max occurrences from the total length
25        return length - Math.max(topCount, bottomCount);
26    };
27
28    // Calculate the minimum rotations needed for the first elements of tops and bottoms
29    const rotations = Math.min(
30        calculateRotationsForNumber(tops[0]),
31        calculateRotationsForNumber(bottoms[0])
32    );
33
34    // If rotations are greater than length, that means we cannot make all values in one side equal; return -1
35    return rotations > length ? -1 : rotations;
36}
37

Time and Space Complexity

The time complexity of the code provided is O(n), where n is the length of the arrays tops and bottoms. This is because the function f(x) goes through all the elements in tops and bottoms once, using a single loop with zip(tops, bottoms), to count the occurrences. The function f(x) is called at most twice, once for tops[0] and once for bottoms[0], regardless of the size of the input. Therefore, the total number of operations is proportional to the size of the arrays, thus the O(n) time complexity.

The space complexity is O(1). This is because the extra space used by the function does not depend on the size of the input arrays. The variables cnt1, cnt2, and ans use a constant amount of space, and no additional data structures that grow with the input size are used.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫